La calculadora del número de árboles generadores da el número de árboles generadores de un grafo completo con la fórmula de Cayley, de un grafo bipartito completo, de una rueda y de un ciclo, con la longitud del código de Prüfer y el número de aristas de un árbol.
Cómo se hace el cálculo
- Introduce los vértices del grafo completo.
- Introduce los tamaños de las dos partes del grafo bipartito y los radios de la rueda.
- Lee el número de árboles generadores de cada grafo.
Ejemplo
El grafo completo de 6 vértices tiene 1296 árboles generadores, cada uno con 5 aristas y un código de Prüfer de longitud 4. El grafo bipartito completo K(3, 4) tiene 432. Una rueda de 6 radios tiene 320, y su ciclo de borde tiene 6.
Por qué es útil
La calculadora ayuda a estudiantes de teoría de grafos y de matemática discreta, a diseñadores de redes y a aficionados a los acertijos que quieren contar las formas de conectar un conjunto de nodos con el mínimo de enlaces, comprobar la fórmula de Cayley en casos pequeños, o comparar la riqueza de distintas formas de red. Es un tema habitual en las asignaturas de Matemática discreta y de Algoritmos de los grados de Matemáticas e Informática.
Qué conviene saber
Los recuentos se refieren a vértices etiquetados, de modo que dos árboles que solo difieren en el nombre de los vértices se cuentan por separado. Los números crecen deprisa con el número de vértices, así que la calculadora limita los tamaños. Usa el teorema de Kirchhoff para los grafos que no están en estas familias. La fórmula de la rueda utiliza el número de Lucas redondeado a partir del número áureo, lo que es exacto para los tamaños permitidos. El porcentaje mostrado se compara con todos los subconjuntos de aristas del tamaño adecuado. Para una comprobación rápida, un grafo completo de 3 vértices tiene 3 árboles generadores, y un camino o una estrella con cualquier número de vértices tiene exactamente uno.
Herramientas relacionadas
La calculadora del grafo de Turán trata los grafos extremales, la de combinaciones cuenta los subconjuntos, la del binomio da los coeficientes y la de Fibonacci remite a los números de Lucas.