Calcolare il numero totale di alberi abbracciano contenenti un particolare insieme di bordi

Question

Ho provato il seguente approccio:

Prima faccio contrazione degli spigoli per tutti gli spigoli di un dato insieme di bordi per formare un grafico modificato.

Poi ho calcolare il numero totale di spanning tree, usando il teorema albero della matrice, dal grafico modificato.

Vorrei sapere se questo metodo è corretto e se ci sono alcuni altri metodi migliori.

Answer 1

Sia G un grafo, sia E un bordo, e G / e sia lo stesso grafico con e contratta. Poi,

Proposizione:. Esiste una corrispondenza biunivoca tra le spanning tree di G che contengono e, e lo spanning tree di G / e

Questa proposizione non è difficile da dimostrare; si sta meglio comprendere la prova voi stessi invece di chiedere ad altre persone se è vero. Ovviamente se si dispone di un albero di copertura T di G che contiene e, quindi T / E è un albero di copertura di G / e. La cosa da pensare attraverso è che si può anche tornare indietro.

E, come sottolinea Adam, bisogna stare attenti a gestire correttamente i grafici con bordi paralleli e grafici con i bordi da un vertice a se stesso.

Answer 2

Non so se è corretto o meno, ma dovrete fare attenzione al fatto che la contrazione bordo può portare a bordi paralleli. Dovrete fare in modo che gli alberi differiscono solo per cui bordo parallelo viene utilizzato vengono conteggiati come distinti.