www.wikidata.de-de.nina.az

Regulärer Graph In der Graphentheorie heißt ein Graph regulär falls alle seine Knoten gleich viele Nachbarn haben also d

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. 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 Bearbeiten

Sei A die Adjazenzmatrix eines Graphen. Der Graph ist genau dann regulär, wenn ein Eigenvektor von A ist. 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.

Kombinatorik Bearbeiten

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 :

Anzahl der zusammenhängenden regulären Graphen
n k
3 4 5 6 7 8 9 10 11 12
4 1 0 0 0 0 0 0 0 0 0
5 0 1 0 0 0 0 0 0 0 0
6 2 1 1 0 0 0 0 0 0 0
7 0 2 0 1 0 0 0 0 0 0
8 5 6 3 1 1 0 0 0 0 0
9 0 16 0 4 0 1 0 0 0 0
10 19 59 60 21 5 1 1 0 0 0
11 0 265 0 266 0 6 0 1 0 0
12 85 1544 7848 7849 1547 94 9 1 1 0
13 0 10778 0 367860 0 10786 0 10 0 1
14 509 88168 3459383 21609300 21609301 3459386 88193 540 13 1
15 0 805491 0 1470293675 0 1470293676 0 805579 0 17
16 4060 8037418 2585136675 113314233808 733351105934 733351105935 113314233813 2585136741 8037796 4207

Weblinks Bearbeiten

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

Einzelnachweise Bearbeiten

  1. Wai-Kai Chen: Graph Theory and its Engineering Applications. World Scientific, 1997, ISBN 978-981-02-1859-1, S. 29.
  2. ↑ 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Graphentheorie heisst ein Graph regular falls alle seine Knoten gleich viele Nachbarn haben also den gleichen Grad besitzen Bei einem regularen gerichteten Graphen muss weiter die starkere Bedingung gelten dass alle Knoten den gleichen Eingangs und Ausgangsgrad besitzen 1 Ein regularer Graph mit Knoten vom Grad k wird k regular oder regularer Graph vom Grad k genannt Regulare Graphen mit einem Grad von hochstens 2 lassen sich leicht klassifizieren Ein 0 regularer Graph besteht aus unzusammenhangenden Knoten ein 1 regularer Graph besteht aus unzusammenhangenden Kanten und ein 2 regularer Graph besteht aus unzusammenhangenden Kreisen Ein 3 regularer Graph wird auch als kubischer Graph bezeichnet Ein stark regularer Graph ist ein regularer Graph bei dem je 2 benachbarte Knoten genau a gemeinsame Nachbarn und je zwei nicht benachbarte Knoten genau b gemeinsame Nachbarn haben Der kleinste regulare aber nicht stark regulare Graph ist der Kreisgraph und der zirkulare Graph mit je 6 Knoten Der vollstandige Graph K m displaystyle K m ist fur jedes m displaystyle m stark regular Nach einem Satz von Nash Williams hat jeder k regulare Graph mit 2 k 1 displaystyle 2k 1 Knoten einen Hamiltonkreis 0 regularer Graph 1 regularer Graph 2 regularer Graph 3 regularer GraphInhaltsverzeichnis 1 Algebraische Eigenschaften 2 Kombinatorik 3 Weblinks 4 EinzelnachweiseAlgebraische Eigenschaften BearbeitenSei A die Adjazenzmatrix eines Graphen Der Graph ist genau dann regular wenn j 1 1 displaystyle textbf j 1 dots 1 nbsp ein Eigenvektor von A ist 2 Der Eigenwert dieses Vektors ist gleichbedeutend mit dem Grad des Graphen Eigenvektoren mit anderen Eigenwerten sind orthogonal zu j displaystyle textbf j nbsp d h fur solche Eigenvektoren v v 1 v n displaystyle v v 1 dots v n nbsp gilt i 1 n v i 0 displaystyle textstyle sum i 1 n v i 0 nbsp Ein regularer Graph vom Grad k ist genau dann zusammenhangend wenn der Eigenwert k die Vielfachheit eins hat 2 Kombinatorik BearbeitenDie Anzahl der zusammenhangenden k displaystyle k nbsp regularen Graphen steigt fur gegebenes k displaystyle k nbsp im Wesentlichen schneller als exponentiell mit der Anzahl n displaystyle n nbsp der Knoten Wenn n displaystyle n nbsp und k displaystyle k nbsp ungerade sind ist diese Anzahl offensichtlich gleich 0 Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen fur n 16 displaystyle n leq 16 nbsp und k 12 displaystyle k leq 12 nbsp 3 4 Anzahl der zusammenhangenden regularen Graphenn k3 4 5 6 7 8 9 10 11 124 1 0 0 0 0 0 0 0 0 05 0 1 0 0 0 0 0 0 0 06 2 1 1 0 0 0 0 0 0 07 0 2 0 1 0 0 0 0 0 08 5 6 3 1 1 0 0 0 0 09 0 16 0 4 0 1 0 0 0 010 19 59 60 21 5 1 1 0 0 011 0 265 0 266 0 6 0 1 0 012 85 1544 7848 7849 1547 94 9 1 1 013 0 10778 0 367860 0 10786 0 10 0 114 509 88168 3459383 21609300 21609301 3459386 88193 540 13 115 0 805491 0 1470293675 0 1470293676 0 805579 0 1716 4060 8037418 2585136675 113314233808 733351105934 733351105935 113314233813 2585136741 8037796 4207Weblinks Bearbeiten nbsp Commons Regulare Graphen Sammlung von Bildern Videos und Audiodateien Eric W Weisstein Regular Graph In MathWorld englisch Eric W Weisstein Strongly Regular Graph In MathWorld englisch GenReg Software und Daten von Markus Meringer Einzelnachweise Bearbeiten Wai Kai Chen Graph Theory and its Engineering Applications World Scientific 1997 ISBN 978 981 02 1859 1 S 29 a b D M Cvetkovic M Doob H Sachs Spectra of Graphs Theory and Applications 3 uberarbeitete Auflage Wiley New York 1998 Folge A068934 in OEIS Wolfram MathWorld Regular Graph Abgerufen von https de wikipedia org w index php title Regularer Graph amp oldid 229274407