Regelmäßige Grafik - Regular graph

In der Graphentheorie ist ein regulärer Graph ein Graph, bei dem jeder Knoten die gleiche Anzahl von Nachbarn hat; dh jeder Knoten hat den gleichen Grad oder die gleiche Wertigkeit. Ein regulärer gerichteter Graph muss auch die stärkere Bedingung erfüllen, dass der Innengrad und der Außengrad jedes Knotens gleich sind. Ein regulärer Graph mit Ecken vom Grad ist ein sogenannte -regelmäßige Graph oder reguläre Graph von Grad . Außerdem enthält ein regulärer Graph nach dem Handshaking-Lemma eine gerade Anzahl von Knoten mit ungeradem Grad. ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

Reguläre Graphen höchsten Grades 2 sind leicht zu klassifizieren: Ein 0-regulärer Graph besteht aus nicht zusammenhängenden Knoten, ein 1-regulärer Graph besteht aus getrennten Kanten und ein 2-regulärer Graph besteht aus einer disjunkten Vereinigung von Kreisen und unendlichen Ketten.

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

Ein stark regulärer Graph ist ein regulärer Graph, bei dem jedes benachbarte Knotenpaar dieselbe Anzahl l gemeinsamer Nachbarn hat und jedes nicht benachbarte Knotenpaar dieselbe Anzahl n gemeinsamer Nachbarn hat. Die kleinsten Graphen, die regelmäßig, aber nicht stark regulär sind, sind der Zyklusgraph und der zirkulierende Graph auf 6 Knoten.

Der vollständige Graph ist stark regulär für alle . ${\displaystyle K_{m}}$${\displaystyle m}$

Ein Satz von Nash-Williams besagt, dass jeder reguläre Graph auf 2 k  + 1 Ecken einen Hamilton-Zyklus hat . ${\displaystyle k}$

• 

  0-regulärer Graph

• 

  1-regulärer Graph

• 

  2-regulärer Graph

• 

  3-regulärer Graph

Existenz

Es ist bekannt, dass die notwendigen und hinreichenden Bedingungen für die Existenz eines regulären Ordnungsgraphen dies und das ist gerade sind. ${\displaystyle k}$${\displaystyle n}$${\displaystyle n\geq k+1}$${\displaystyle nk}$

Beweis: Wie wir wissen, hat ein vollständiger Graph jedes Paar verschiedener Knoten, die durch eine eindeutige Kante miteinander verbunden sind. Die Kanten sind also im vollständigen Graphen maximal und die Anzahl der Kanten und der Grad hier . Also . Dies ist das Minimum für eine bestimmte . Beachten Sie auch, dass, wenn ein regulärer Graph eine Ordnung hat, die Anzahl der Kanten gerade sein muss. In einem solchen Fall ist es einfach, reguläre Graphen zu konstruieren, indem man geeignete Parameter für zirkulierende Graphen berücksichtigt . ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}}}$${\displaystyle n-1}$${\displaystyle k=n-1,n=k+1}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle {\dfrac {nk}{2}}}$${\displaystyle nk}$

Algebraische Eigenschaften

Sei A die Adjazenzmatrix eines Graphen. Dann ist der Graph genau dann regulär, wenn er Eigenvektor von A ist . Sein Eigenwert ist der konstante Grad des Graphen. Eigenvektoren zu anderen entsprechenden Eigenwerten orthogonal sind , so dass für eine solche Eigenvektoren , haben wir . ${\displaystyle {\textbf{j}}=(1,\dots,1)}$${\displaystyle {\textbf {j}}}$${\displaystyle v=(v_{1},\dots,v_{n})}$${\displaystyle \sum_{i=1}^{n}v_{i}=0}$

Ein regulärer Graph vom Grad k ist genau dann zusammenhängend, wenn der Eigenwert k die Vielfachheit eins hat. Die "nur wenn"-Richtung ist eine Folge des Satzes von Perron-Frobenius .

Es gibt auch ein Kriterium für regelmäßige und zusammenhängende Graphen: Ein Graph ist genau dann zusammenhängend und regulär, wenn die Matrix der Einsen J , mit , in der Adjazenzalgebra des Graphen liegt (also eine Linearkombination von Potenzen von A ist ). ${\displaystyle J_{ij}=1}$

Sei G ein k- regulärer Graph mit Durchmesser D und Eigenwerten der Adjazenzmatrix . Wenn G nicht bipartit ist, dann ${\displaystyle k=\lambda_{0}>\lambda_{1}\geq\cdots\geq\lambda_{n-1}}$

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda_{0}/\lambda_{1})}}+1.}$

Generation

Es gibt schnelle Algorithmen, um bis auf Isomorphie alle regulären Graphen mit einem gegebenen Grad und einer bestimmten Anzahl von Knoten aufzuzählen.

Siehe auch

• Zufälliger regulärer Graph
• Stark regelmäßiger Graph
• Moore-Grafik
• Käfigdiagramm
• Sehr unregelmäßiger Graph

Verweise

Externe Links

• Weisstein, Eric W. "Reguläres Diagramm" . MathWorld .
• Weisstein, Eric W. "Strongly Regular Graph" . MathWorld .
• GenReg- Software und Daten von Markus Meringer.
• Nash-Williams, Crispin (1969), Valenzsequenzen, die Graphen zwingen, Hamilton-Schaltungen zu haben , University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo