imported>DeWikiMan: + Normdaten

2024-08-30T10:30:32Z

+ Normdaten

Neue Seite

In der [[Graphentheorie]] heißt ein [[Graph (Graphentheorie)|Graph]] '''regulär''', falls alle seine [[Knoten (Graphentheorie)|Knoten]] gleich viele Nachbarn haben, also den gleichen [[Grad (Graphentheorie)|Grad]] besitzen. Bei einem regulären [[Gerichteter Graph|gerichteten Graphen]] muss weiter die stärkere Bedingung gelten, dass alle Knoten den gleichen [[Eingangsgrad|Eingangs-]] und [[Ausgangsgrad]] besitzen.<ref>{{Literatur |Autor=Wai-Kai Chen |Titel=Graph Theory and its Engineering Applications |Verlag=World Scientific |Datum=1997 |ISBN=978-981-02-1859-1 |Seiten=29}}</ref> 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 (Graphentheorie)|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 [[Kreisgraph|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 [[Nachbar (Graphentheorie)|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ärer Graph|zirkuläre Graph]] mit je 6 Knoten.

Der [[Vollständiger Graph|vollständige Graph]] <math>K_m</math> ist für jedes <math>m</math> stark regulär.

Nach einem Satz von [[Crispin Nash-Williams|Nash-Williams]] hat jeder ''k''-reguläre Graph mit <math>2k + 1</math> Knoten einen [[Hamiltonkreis]].

<gallery>
0-regular graph.svg|0-regulärer Graph
1-regular graph.svg|1-regulärer Graph
2-regular graph.svg|2-regulärer Graph
3-regular graph.svg|3-regulärer Graph
</gallery>

== Algebraische Eigenschaften ==
Sei ''A'' die [[Adjazenzmatrix]] eines Graphen. Der Graph ist genau dann regulär, wenn <math>\textbf{j}=(1, \dots ,1)</math> ein [[Eigenvektor]] von ''A'' ist.<ref name="Cvetkovic">{{Literatur |Autor=D. M. Cvetković, M. Doob, H. Sachs |Titel=Spectra of Graphs: Theory and Applications |Auflage=3. überarbeitete |Verlag=Wiley |Ort=New York |Datum=1998}}</ref> Der [[Eigenwert]] dieses Vektors ist gleichbedeutend mit dem Grad des Graphen. Eigenvektoren mit anderen Eigenwerten sind [[orthogonal]] zu <math>\textbf{j}</math>, d. h. für solche Eigenvektoren <math>v=(v_1,\dots,v_n)</math> gilt: <math>\textstyle \sum_{i=1}^n v_i = 0</math>.

Ein regulärer Graph vom Grad ''k'' ist genau dann [[Zusammenhang von Graphen|zusammenhängend]], wenn der Eigenwert ''k'' die [[Algebraische Vielfachheit|Vielfachheit]] eins hat.<ref name="Cvetkovic" />

== Kombinatorik ==
Die Anzahl der [[Zusammenhängender Graph|zusammenhängenden]] <math>k</math>-regulären [[Graph (Graphentheorie)|Graphen]] steigt für gegebenes <math>k</math> im Wesentlichen schneller als [[Exponentialfunktion|exponentiell]] mit der Anzahl <math>n</math> der [[Knoten (Graphentheorie)|Knoten]]. Wenn <math>n</math> und <math>k</math> ungerade sind, ist diese Anzahl offensichtlich gleich 0.

Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer|Computers]] bestimmten Anzahlen für <math>n \leq 16</math> und <math>k \leq 12</math>:<ref>{{OEIS|A068934}}</ref><ref>Wolfram MathWorld: [https://mathworld.wolfram.com/RegularGraph.html Regular Graph]</ref>
{| class="wikitable" style="text-align:right"
! colspan="11" |Anzahl der zusammenhängenden regulären Graphen
|-
! rowspan="2" |n
! colspan="10" |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 ==
{{Commonscat|Regular graphs|Reguläre Graphen}}
* {{MathWorld |id=RegularGraph |title=Regular Graph}}
* {{MathWorld |id=StronglyRegularGraph |title=Strongly Regular Graph}}
* [http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html GenReg] Software und Daten von Markus Meringer.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4214561-2}}
{{SORTIERUNG:Regularer Graph}}
[[Kategorie:Regulärer Graph| ]]

Regulärer Graph - Versionsgeschichte

imported>DeWikiMan: + Normdaten