Berechnung der Gesamtzahl der Spannbäume einen bestimmten Satz von Kanten enthalten,

Question

Ich habe den folgenden Ansatz versucht:

Zuerst ich Kante Kontraktion für alle Kanten in dem vorgegebenen Satz von Kanten eines modifizierten Graphen zu bilden.

Dann berechne ich die Gesamtzahl Bäume von Spanning, die Matrix Baumsatz verwendet wird, aus dem modifizierten Graphen.

Ich möchte wissen, ob diese Methode richtig ist und wenn es einige andere, bessere Methoden.

Answer 1

Es sei G ein Graph, sei e eine Kante, und sei G / e der gleiche Graph mit e zusammengezogen. Dann

Vorschlag:. Es gibt eine Bijektion zwischen den Spannbäumen von G, die E enthalten, und die Spannbäume von G / e

Dieser Satz ist nicht schwer zu beweisen; du bist besser dran den Beweis zu verstehen, sich statt nur andere Leute zu fragen, ob es wahr ist. Natürlich, wenn Sie einen Spanning T Baum von G, die E enthält, dann T / E ist ein Spanning Tree von G / e. Das ist daran zu denken, durch ist, dass man auch rückwärts gehen kann.

Und wie Adam weist darauf hin, müssen Sie vorsichtig sein, um richtig Graphen mit parallelen Kanten und Grafiken mit den Kanten an mich von einem Scheitel zu behandeln.

Answer 2

Ich weiß nicht, ob es richtig ist oder nicht, aber Sie werden vorsichtig von der Tatsache sein müssen, dass Kantenkontraktion zu parallelen Kanten führen kann. Sie werden sicher unterscheiden, dass Bäume nur machen, durch die parallele Kante als verschieden gezählt verwendet wird.