Saltar al contenido
Omnikalc

Calculadora del número de árboles generadores

Introduce el número de vértices de un grafo completo, los tamaños de las dos partes de un grafo bipartito completo y el número de radios de una rueda para obtener el número de árboles generadores de cada uno.

Actualizado el
Tus datos

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Valor fuera de rango

Resultados

Árboles generadores del grafo completo

1296

Árboles generadores del grafo bipartito completo

432

Árboles generadores de la rueda

320

Árboles generadores del ciclo del mismo borde
6
Longitud del código de Prüfer del grafo completo
4
Aristas de cada árbol generador del grafo completo
5
Árboles generadores como porcentaje de todos los subconjuntos de aristas del mismo tamaño
43,1568 %

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.

Preguntas frecuentes

¿Qué es la fórmula de Cayley?

La fórmula de Cayley dice que el grafo completo de n vértices etiquetados tiene exactamente n^(n−2) árboles generadores. Para n = 4 hay 16 árboles etiquetados, para n = 5 hay 125 y para n = 6 hay 1296. La enunció Cayley en 1889, y Prüfer dio una demostración con una biyección entre árboles y sucesiones de longitud n − 2.

¿Cómo se cuentan los árboles generadores de un grafo bipartito?

Para el grafo bipartito completo K(m, n), el número de árboles generadores es m^(n−1) × n^(m−1). Para K(3, 4), es 3³ × 4² = 432. Para m = 1, es una estrella con un único árbol generador, que es el propio grafo.

¿Y la rueda?

Una rueda de w radios tiene w + 1 vértices: un centro unido a todos los vértices de un ciclo de w vértices. Su número de árboles generadores es L(2w) − 2, donde L es el número de Lucas. Para w = 6, es L(12) − 2 = 322 − 2 = 320. La sucesión para w ≥ 3 empieza por 16, 45, 121, 320.

¿Por qué se cuentan los árboles generadores?

Los árboles generadores describen las formas de conectar todos los nodos de una red con el menor número de enlaces. El número mide la robustez del diseño de una red, interviene en los cálculos de fiabilidad y en el análisis de redes eléctricas, y el teorema del árbol matricial de Kirchhoff los cuenta para cualquier grafo a partir del determinante del laplaciano.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.