El cálculo de número total de árboles de expansión que contienen un conjunto particular de bordes

Question

He probado el método siguiente:

Primera hago contracción borde para todos los bordes en el conjunto dado de bordes para formar un gráfico modificado.

Entonces calcular el número total de árboles de expansión, utilizando el teorema de árbol de matriz, a partir del gráfico modificado.

Quiero saber si este método es correcto y si hay algunos otros métodos mejores.

Answer 1

Sea G una gráfica, sea E un borde, y sea G / e sea el mismo gráfico con e contrajo. Entonces,

Propuesta:. Hay una biyección entre los árboles de expansión de G que contienen electrónico, y los árboles de expansión de G / e

Esta proposición no es difícil de probar; es mejor comprensión de la prueba a sí mismo en lugar de simplemente preguntando a otras personas si es verdad. Obviamente, si usted tiene un árbol que abarca T de G que contiene la dirección, entonces T / E es un árbol de expansión de G / e. Lo que hay que pensar en es que también se puede ir hacia atrás.

Y, como señala Adam, usted tiene que tener cuidado para manejar adecuadamente gráficos con bordes paralelos y gráficos con bordes de un vértice a sí mismo.

Answer 2

No sé si es correcto o no, pero usted tendrá que tener cuidado de que la contracción de aristas puede conducir a bordes paralelos. Usted tiene que asegurarse de que los árboles que sólo difieren por el cual se utiliza borde paralelo se cuentan como un sistema distinto.