Bestimmung der Gerüstanzahl eines Graphen

Einführung

Def 1: Es sei G ein zusammenhängender Graph. Ein zusammenhängender, alle Knotenpunkte von G enthaltender Untergraph von G mit minimaler Kantenanzahl heißt Gerüst von G.

Beispiel:

Die fett gezeichneten Kanten stellen eines der Gerüste des Graphen dar.

Die Anzahl der Gerüste eines vollständigen Graphen

Bevor die Gerüstanzahl eines allgemeinen Graphen diskutiert wird, soll auf den speziellen Fall der vollständigen Graphen eingegangen werden. Für den vollständigen Graphen bewies "Cayley" 1889 eine geschlossene Formel zur Berechnung der Gerüstanzahl, wodurch sehr einfach die Gerüstanzahl bestimmt werden kann.

Satz von Cayley : Der vollständige Graph mit n Knotenpunkten besitzt genau n^n-2 verschiedene Gerüste.

Gleichung 1

Beweis :Man nehme ein k-tupel T^n-2 = ( J₁, J₂, , J_n-2 ) und ordne ihm auf folgende Weise ein eindeutiges Gerüst zu. Dazu geben wir die Knotenpunkte 1,2, , n vor und fügen nach und nach Kanten hinzu, bis ein Baum entstanden ist.

Wir bestimmen die kleinste Zahl I₁ von
X= { 1,2,,n}, die nicht in T^n-2 enthalten ist, und zeichnen die Kante l₁=(I₁,J₁).
Bsp. T⁵=(4,3,7,4,5); X={1,2,3,4,5,6,7} l₁=(1,4)

Dann bestimmen wir die kleinste Zahl I₂ aus X-{I₁}, die nicht in dem k-1 tupel (J₂, J₃, , J_n-2) vorkommt und zeichnen die Kante
l₂ = (I₂,J₂).
Bsp.T⁴=(3,7,4,5);X-{I₁}={2,3,4,5,6,7} l₂=(2,3)

Nach n-2 Schritten enthält X-{I₁, I₂, , I_n-2} nur noch die beiden Knotenpunkte I_n-1 und I_n, die durch die Kante l_n-1 verbunden werden. X-{I₁, I₂, , I_n-2}= {5,7}l_n-1=(5,7)

Der auf diese Weise konstruierte Graph H^* hat n Knotenpunkte und n-1 Kanten. Um zu beweisen, daß H^* ein Baum ist, brauchen wir nur zu beweisen, daß H^* keinen Kreis enthält.

In jedem Stadium der Konstruktion gilt :

a) Jeder Knotenpunkt ist Anfangspunkt höchstens einer Kante, I_n ist Anfangspunkt keiner Kante. Die schon benutzten Anfangspunkte werden ja aus X gelöscht.

b) Kein Endpunkt einer Kante ist Anfangspunkt einer schon früher gezeichneten Kante

Die Endpunkte der Kanten, was dem Zahlen des Tupels entspricht, werden bei der Konstruktion ebenfalls als Anfangspunkte ausgeschlossen.

Angenommen, H^*enthalte einen Kreis, dann sei l_s die erste der Kanten, durch deren Hinzunahme ein Kreis C entsteht. Nun gibt es zwei Möglichkeiten auf welchem Weg ein Kreis entsteht.

A)

Die Kanten im Kreis haben verschiedenen Umlaufsinn.
B)

Alle Kanten im Kreis haben den gleichen Umlaufsinn.

Der Fall A kann nicht eintreten, da er im Widerspruch zu a) steht, da der obere Knoten zwei Kanten als Anfangspunkt dient. Der Fall B kann ebenfalls nicht eintreten, da an der Stelle wo sich der Kreis schließt ein Widerspruch zu Punkt b) eintreten würde.

Damit ist bewiesen, daß eine eindeutige Abbildung der Menge der (n-2)-Tupel auf die Menge der Gerüste existiert. Um den Beweis vollständig zu machen, muß nun noch gezeigt werden, daß auch eine umgekehrte Abbildung existiert. Dazu ordnet man jedem Gerüst auf folgende Weise ein (n-2)-Tupel zu. Man bestimme den Knoten vom Grad 1, der die kleinste Knotennummer besitzt. Nun trage man den (einzigen) Nachbar des Knotens in das Tupel ein. Danach lösche man den Knoten und seine Kante. Dieser Vorgang wird nun solange wiederholt, bis nur noch zwei durch eine Kante verbundene Knoten übrig sind, der Tupel also einen Umfang von n-2 besitzt.

Damit ist umkehrbar eindeutig bewiesen, daß jedem Gerüst ein (n-2)-Tupel zugewiesen werden kann.

Im Programm zur Bestimmung der Gerüstanzahl wird dieser Satz ausgenutzt, indem getestet wird , ob der Graph G ein vollständiger Graph ist. Sollte dies der Fall sein, wird auf die weiter unten beschriebene Berechnung verzichtet und das Ergebnis aus Gleichung 1 berechnet. Die Erkennung des vollständigen Graphen erfolgt über seine Kantenanzahl von .

Bestimmung der Gerüstanzahl für einen allgemeinen Graphen

Um die Gerüstanzahl für einen allgemeinen Graphen zu bestimmen, benutzen wir einen Satz, der auf grundlegende Arbeiten von Kirchhoff zur Theorie der elektrischen Netzwerke zurückgeht und 1954 von Trent auf anderem Weg bewiesen wurde.

Bevor jedoch der Satz genannt und bewiesen wird, muß man sich mit verschiedenen Arten von Matrizen beschäftigen, mit deren Hilfe man einen Graphen beschreiben kann.

Beschreibung eines Graphen mit Hilfe von Matrizen

Für verschiedene graphentheoretische Probleme und deren Lösung hat es sich als sinnvoll erwiesen, Graphen mit Hilfe von Matrizen zu beschreiben. Dabei soll an dieser Stelle auf drei Arten von Matrizen näher eingegangen werden.

Beispielgraph für alle Matrizen :

Die Adjazenzmatrix G

Sei G(V,E) ein Graph mit der Knotenmenge V und Kantenmenge E, so heißt die quadratische Matrix G[nn] Adjazenzmatrix von G, genau dann wenn

Gleichung 2

Adjazenzmatrix des Beispielgraphen :

Die Valenzmatrix B

Sei G(V,E) ein Graph mit der Knotenmenge V und Kantenmenge E, so heißt die quadratische Matrix B[nn] Valenzmatrix von G, genau dann wenn

Gleichung 3

Valenzmatrix des Beispielgraphen :

Die Admittanzmatrix A

Sei G(V,E) ein Graph mit der Knotenmenge V und Kantenmenge E, so heißt die quadratische Matrix A[nn] Admittanzmatrix von G, genau dann wenn

Gleichung 4

Admittanzmatrix des Beispielgraphen :

Der Satz von Kirchhoff-Trent

(Satz und Beweis laut H.Sachs [3])

Satz : Der Graph G mit den Knotenpunkten 1,2, ,n ( n2 ) habe die Admittanzmatrix A. Es sei i eine beliebige Zahl zwischen 1 n. Die Matrix A_i entstehe aus A durch Streichung der i-ten Zeile und der i-ten Spalte. Es gilt dann : Die Determinante |A_i| ist gleich der Anzahl h(G) der Gerüste von G.

Bezeichnungen :

M = (m_ik ) sei eine beliebige quadratische Matrix

|M| bezeichne die Determinante von M

M_i entstehe durch Streichen der i-ten Zeile und der i-ten Spalte

M_j^* entstehe aus M, indem alle Elemente der j-ten Spalte bis auf das Diagonalelement durch 0 und m_jj durch 1 ersetzt werden.

M^k entstehe aus M, indem m_kk um 1 verkleinert wird.

Wie man leicht sieht ist für i k :

|M_i|=|M_i^*| Gleichung 5

Beispiel :

(M_i)^k=(M^k)_i man schreibt

M_iksei erklärt durch M_ik=(M_i)_k (ik).

Aus |M| = |M^k| + |M_k^*| mit Gleichung 5 folgt direkt |M| = |M^k| + |M_k|

Ersetzt man nun M durch M_i dann ergibt sich :

|M_i| = |
| + |M_ik|
Gleichung 6

Hilfssatz:Die Knotenpunkte I und K (IK) des Graphen G seien durch die Kante u verbunden. G^u entstehe aus G durch Zusammenziehen von u. Hierbei werden I und K durch einen einzigen neuen Knotenpunkt ersetzt und alle I und K verbindenden Kanten werden gelöscht. G-u dagegen entstehe durch Löschen der Kante u.

Daraus folgt :

h(G )=h(G^u) + h(G_u);

Beweis:

1. Den Gerüsten von G^u entsprechen umkehrbar eindeutig diejenigen Gerüste von G, die die Kante u enthalten.

2. Den Gerüsten von G-u entsprechen umkehrbar eindeutig diejenigen Gerüste von G, die die Kante u nicht enthalten.

A^(u) und A_(u) seien die Admittanzmatrizen von G^u bzw. G-u , dann gilt :

(A^(u)) = (A_K) = A_K . Aus der Admittanzmatrix wird eine um einen Grad verminderte Matrix, da ja ein Knoten wegfällt.

(A_(u)) = (A)^K = A^K. Die Admittanzmatrix wird um die entfernte Kante vermindert.

Der Beweis kann nun mit der vollständigen Induktion erfolgen.

Beweis :

Es wird angenommen, daß die Anzahl der Gerüste in einem Graphen gleich |A_I| ist. Dies kann für triviale Fälle ( G enthält keine Kante; G enthält zwei Knoten und eine Kante; G enthält n Knoten und n-1 Kanten ) sofort bestätigt werden.

Wir nehmen also an, der Satz sei bewiesen für alle Graphen G mit weniger als p Kanten. Nun nehmen wir weiterhin an, unser Graph G hat genau p Kanten, wurde also durch Einfügen von Kante u erweitert. Da h(G^u) = |(A^(u))_K| = |A_IK| und h(G_u) = |(A_(u))_I| = |A_I^K| bewiesen ist, da diese Graphen weniger als p Kanten besitzen, folgt aus

h(G) = h(G^u) + h(G_u) h(G)= |A_IK| + |A_I^K|.

Dies entspricht aber laut Gleichung (1) h(G)=|A_I|, d.h. jeder Graph mit mehr als p Kanten läßt sich in kleinere Graphen zerlegen, für die der Satz bewiesen ist.

Aus der Rechenregel h(G)= |A_IK| + |A_I^K| = |A_I| folgt dann, daß der Satz auch für größere Graphen bewiesen ist.

Da h(G_u) = |(A_(u))_I| = |A_I^K| und h(G^u) = |(A^(u))_K| = |A_IK| bewiesen werden konnte, folgt daraus unmittelbar, daß auch h(G)= |A_IK| + |A_I^K| = |A_I| richtig ist.

Die Ermittlung der Determinante der Admittanzmatrix

Die Ermittlung der Determinante der Admittanzmatrix und damit der Gerüstanzahl des Graphen G erfolgt mit Hilfe eines leicht modifizierten Gauß-Algorithmus. Der Gauß-Algorithmus wird hier als modifiziert bezeichnet, weil er um einen Programmteil ergänzt wurde, der Rundungsfehler beim Berechnen größeren Matrizen bzw. sehr kleiner Werte vermindern hilft. Da der Algorithmus allgemein bekannt ist, einer Toolbox entnommen wurde und in fast jedem Buch über numerische Mathematik z.B. [2] zu finden ist, wird hier auf eine Erklärung desselben verzichtet. Der Algorithmus erwartet als Parameter die Größe der Matrix, so daß das statt des Streichens einer Zeile und Spalte, nur dieser Parameter um 1 verringert zu werden braucht. Es wird dadurch stets die letzte Zeile und Spalte gestrichen.

Rechengeschwindigkeit

Der Algorithmus erstellt eine Matrix aus der Ebert Struktur eínes Graphen und berechnet dann die Determinante der um eine Spalte und Zeile verminderten Matrix. Zur Erstellung der Matrix wird das Feld Valenz und das Feld Node komplett durchlaufen, was eine Rechenzeit von maximal O(n²) verursachen kann. Die Durchführung des Gauß-Algorithmus zur Berechnung der Determinante benötigt eine Rechenzeit O(n³). Insgesamt hat der Algorithmus also eine Rechenzeit von maximal O(n³). Da es sich hierbei um eine polynomiale Rechenzeit handelt, war zu erwarten, daß auch die Gerüstanzahl von größeren Graphen in kurzer Zeit ermittelt werden kann. Dies bestätigte sich durch Testberechnungen.

Beispielberechnung

Beispielgraph :

Admittanzmatrix des Graphen :

Determinante der Admittanzmatrix des Graphen :

Die Gerüstanzahl des Beispielgraphen beträgt damit 8.

Wir bestimmen die kleinste Zahl I₁ von X= { 1,2,,n}, die nicht in T^n-2 enthalten ist, und zeichnen die Kante l₁=(I₁,J₁).	Bsp. T⁵=(4,3,7,4,5); X={1,2,3,4,5,6,7} l₁=(1,4)
Dann bestimmen wir die kleinste Zahl I₂ aus X-{I₁}, die nicht in dem k-1 tupel (J₂, J₃, , J_n-2) vorkommt und zeichnen die Kante l₂ = (I₂,J₂).	Bsp.T⁴=(3,7,4,5);X-{I₁}={2,3,4,5,6,7} l₂=(2,3)
Nach n-2 Schritten enthält X-{I₁, I₂, , I_n-2} nur noch die beiden Knotenpunkte I_n-1 und I_n, die durch die Kante l_n-1 verbunden werden.	X-{I₁, I₂, , I_n-2}= {5,7}l_n-1=(5,7)