Ya hice una pregunta sobre los caminos. Esta vez es sobre árboles. Conociendo la matriz adyacente, ¿es posible calcular (¿con permutaciones?) el número de árboles posibles que se pueden generar a partir de un vértice elegido?
Respuesta
¿Demasiados anuncios?
Si se conoce la matriz de adyacencia de un grafo, se puede construir la matriz de adyacencia de un grafo. Matriz laplaciana, y utilizar el Teorema de la matriz-árbol para determinar el número total de árboles de expansión distintos en el grafo. Dado que cada árbol de expansión contiene todos los vértices del grafo, cualquier árbol de expansión puede "generarse" a partir de cualquier vértice.
Si desea que se enumeren todos los árboles, puede utilizar las instrucciones que figuran en la parte inferior de la página página wiki bajo el subtítulo "Enumeración explícita de árboles de expansión", pero ese método requiere una cantidad significativa de manipulación algebraica. Del mismo modo, si se trata de dígrafos, existen diferentes construcciones de la función Laplaciano que puede utilizar para adaptar mejor sus resultados.
