Regulärer Graph

In der Graphentheorie heißt ein Graph regulär, falls alle seine Knoten gleich viele Nachbarn haben, also den gleichen Grad besitzen. Bei einem regulären gerichteten Graphen muss weiter die stärkere Bedingung gelten, dass alle Knoten den gleichen Eingangs- und Ausgangsgrad besitzen.[1] Ein regulärer Graph mit Knoten vom Grad k wird k-regulär oder regulärer Graph vom Grad k genannt.

Reguläre Graphen mit einem Grad von höchstens 2 lassen sich leicht klassifizieren: Ein 0-regulärer Graph besteht aus unzusammenhängenden Knoten, ein 1-regulärer Graph besteht aus unzusammenhängenden Kanten, und ein 2-regulärer Graph besteht aus unzusammenhängenden Kreisen.

Ein 3-regulärer Graph wird auch als kubischer Graph bezeichnet.

Ein stark regulärer Graph ist ein regulärer Graph, bei dem je 2 benachbarte Knoten genau a gemeinsame Nachbarn, und je zwei nicht benachbarte Knoten genau b gemeinsame Nachbarn haben. Der kleinste reguläre, aber nicht stark reguläre Graph ist der Kreisgraph und der zirkuläre Graph mit je 6 Knoten.

Der vollständige Graph ist für jedes stark regulär.

Nach einem Satz von Nash-Williams hat jeder k-reguläre Graph mit Knoten einen Hamiltonkreis.

Algebraische Eigenschaften

Sei A die Adjazenzmatrix eines Graphen. Der Graph ist genau dann regulär, wenn ein Eigenvektor von A ist.[2] Der Eigenwert dieses Vektors ist gleichbedeutend mit dem Grad des Graphen. Eigenvektoren mit anderen Eigenwerten sind orthogonal zu , d. h. für solche Eigenvektoren gilt: .

Ein regulärer Graph vom Grad k ist genau dann zusammenhängend, wenn der Eigenwert k die Vielfachheit eins hat.[2]

Kombinatorik

Die Anzahl der zusammenhängenden -regulären Graphen steigt für gegebenes im Wesentlichen schneller als exponentiell mit der Anzahl der Knoten. Wenn und ungerade sind, ist diese Anzahl offensichtlich gleich 0.

Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen für und :[3][4]

Anzahl der zusammenhängenden regulären Graphen
nk
3456789101112
41000000000
50100000000
62110000000
70201000000
85631100000
901604010000
1019596021511000
1102650266060100
12851544784878491547949110
13010778036786001078601001
145098816834593832160930021609301345938688193540131
15080549101470293675014702936760805579017
16406080374182585136675113314233808733351105934733351105935113314233813258513674180377964207

Weblinks

Commons: Reguläre Graphen – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Wai-Kai Chen: Graph Theory and its Engineering Applications. World Scientific, 1997, ISBN 978-981-02-1859-1, S. 29.
  2. a b D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs: Theory and Applications. 3. überarbeitete Auflage. Wiley, New York 1998.
  3. Folge A068934 in OEIS
  4. Wolfram MathWorld: Regular Graph

Auf dieser Seite verwendete Medien

0-regular graph.svg
Autor/Urheber: 0x24a537r9, Lizenz: CC BY-SA 3.0
An example of a 0-regular graph
1-regular graph.svg
Autor/Urheber: 0x24a537r9, Lizenz: CC BY-SA 3.0
An example of a 1-regular graph
2-regular graph.svg
Autor/Urheber: 0x24a537r9, Lizenz: CC BY-SA 3.0
An example of a 2-regular graph
3-regular graph.svg
Autor/Urheber: 0x24a537r9, Lizenz: CC BY-SA 3.0
An example of a 3-regular graph