Esta es mi primera pregunta en el sitio StackExchange de Matemáticas, así que por favor dígame si no he respetado alguna convención en este post.
Ok, entonces si tengo un gráfico $G$ , con digamos $6$ vértices y $7$ Aristas, ¿cómo puedo determinar cuántos árboles de expansión posibles hay?
Sé que esta es probablemente una pregunta muy simple, pero soy muy nuevo en la Teoría de Grafos.
Gracias. Jack Hunt
Una de mis formas favoritas de contar árboles de extensión es el teorema de la contracción-eliminación. Para cualquier gráfico $G$ el número de árboles de distribución $\tau(G)$ de $G$ es igual a $\tau(G-e) + \tau(G / e)$ , donde $e$ es cualquier arista de $G$ y donde $G-e$ es la supresión de $e$ de $G$ y $G/e$ es la contracción de $e$ en $G$ . De este modo, se obtiene una forma recursiva de calcular el número de árboles de distribución de un grafo.
Otra regla es que, si se tiene un gráfico con un vértice de corte (un vértice cuya eliminación separaría el gráfico), se puede calcular el número de árboles de distribución a cada lado del vértice de corte y multiplicarlo.
Hay algunos ejemplos más de reglas, para grafos completos, grafos bipartitos completos y otros en la sección 5.2 aquí http://www.student.dtu.dk/~dawi/01227/01227-GraphTheory.pdf . También contiene un apéndice (D) de grafos pequeños y su número de árboles de extensión, que resulta útil si se utiliza el teorema de la contracción-eliminación.
Estos apuntes de teoría de grafos son geniales. Pero, ¿sabes qué paquetes y fuentes se utilizaron en látex, para generar el PDF?
Sí, soy uno de los dos autores (David). He subido los principales archivos LaTeX (y el capítulo sobre los árboles de extensión) aquí: dropbox.com/s/j1amlwqjk1x13cc/graphnotes.zip Básicamente, se trata de una plantilla de Memorias algo personalizada, y todas las figuras están hechas con TikZ.
Para los futuros lectores: para los gráficos más grandes, el teorema de Kirchoff como se responde a continuación, y también como se describe en el pdf vinculado es una forma súper rápida de calcular el recuento del árbol de expansión. Es posible que tengas que utilizar una versión del cálculo del determinante que devuelva el logaritmo para evitar el desbordamiento.
El Teorema de la matriz-árbol te da una fórmula para el número de árboles de expansión. Por supuesto, hay que saber algo más que el número de vértices y el número de aristas; después de todo, hay grafos con 6 vértices, 7 aristas y ningún árbol de distribución.
No hay una fórmula sencilla para el número de árboles de extensión de un grafo (conectado) que sea sólo en términos del número de vértices y aristas. Sin embargo, si se puede calcular el polinomio de Tutte del grafo y luego evaluarlo en el punto $(1,1)$ que es igual al número de árboles de expansión.
Sí, lo hay. Si es un grafo completo, y debe serlo, el número de árboles de distribución es $n^{n-2}$ donde $n$ es el número de nodos. Por ejemplo, un gráfico completo con $5$ los nodos deben producir $5^3$ árboles de distribución y un grafo completo con $4$ los nodos deben producir $4^2$ No conozco ningún gráfico completo con $6$ nodos y $7$ bordes. ¿Existe un gráfico de este tipo? John Oke
Un grafo completo es un grafo en el que cada par de vértices está unido por una arista, por lo que el número de aristas de un grafo completo es $\frac{n(n-1)}{2}$ . Esto da, que el número de aristas en EL gráfico completo en 6 vértices es 15.
Como menciona @utdiscant, hay un gráfico completo en $n$ vértices. La fórmula de Cayley, que es el hecho mencionado aquí, se puede deducir del Teorema del Árbol Matriz que menciona Gerry, pero hay otras pruebas más combinatorias, por ejemplo, la de Joyal que se puede encontrar aquí. math.stackexchange.com/a/93421/21585
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿Te refieres a que tienes un único gráfico fijo que casualmente tiene seis vértices y siete aristas, o quieres sumar sobre todos los gráficos con seis vértices y siete aristas? En el primer caso, dependerá de la configuración particular de las aristas, así que tendrás que dar más información. Además, ¿tus grafos están etiquetados o sin etiquetar?
0 votos
@AustinMohr Hola, lo siento, como he dicho, primer post. Sí, estoy tratando de encontrar la cantidad de árboles de extensión para un gráfico fijo y etiquetado.