Hjul (grafteori)
| Hjulgrafeksempler | |
|---|---|
| Toppe | n |
| ribben | 2( n − 1) |
| Diameter |
2 for n>4 1 for n =4 |
| Omkreds | 3 |
| Kromatisk tal | 3 for ulige n , 4 for lige n |
| Ejendomme |
Hamiltonsk dobbeltplan _ |
| Betegnelse | W n |
| Mediefiler på Wikimedia Commons | |
I grafteori er et hjul W n en graf med n toppunkter (n ≥ 4), dannet ved at forbinde et enkelt toppunkt med alle toppunkter i ( n -1) -cyklussen . Den numeriske betegnelse af hjulene i litteraturen er ikke veletableret - nogle forfattere bruger n til at angive længden af cyklussen, så deres W n betyder grafen W n+1 som defineret ovenfor [1] . Et hjul kan defineres på samme måde som et 1-skelet( n -1 ) -kulpyramide .
Indstil repræsentation
Lad sættet af toppunkter {1,2,3,...,v} være givet. Sættet af kanter på grafhjulet kan repræsenteres som et sæt {{1,2},{1,3},...,{1,v},{2,3},{3,4},..., {v-1, v},{v,2}} [2] .
Egenskaber
Hjulene er plane grafer , og har derfor en unik indlejring i planet. Ethvert hjul er en Halin-graf . De er selv-duale - den dobbelte graf for ethvert hjul er isomorf i forhold til selve hjulet. Enhver maksimal plan graf bortset fra K 4 = W 4 indeholder enten W 5 eller W 6 som en undergraf .
Der er altid en Hamilton-cyklus i hjulet, og antallet af cyklusser i W n er (sekvens A002061 i OEIS ).
7 cyklusser i hjulet W 4 . |
For ulige værdier af n er W n en perfekt graf med kromatisk nummer 3 - cyklussens hjørner kan farves i to farver, og det centrale toppunkt vil have en tredje farve. For selv n W n har hjulet kromatisk nummer 4 og (for n ≥ 6) vil ikke være en perfekt graf. W 7 er det eneste hjul, der er en enhedsafstandsgraf på det euklidiske plan [3] .
Det kromatiske polynomium af hjulet W n er:
Der er to særligt vigtige slags matroider i matroideori, hjul og hvirvler , som begge er afledt af hjulgrafer. K -hjulet matroide er en graf matroidehjul W k+1 , og k -hvirvelmatroiden opnås fra k -hjulmatroiden ved at erklære den ydre cyklus (fælg) lige så uafhængig som dens spændende træer .
W 6 - hjulet giver et modeksempel til Paul Erdős formodning i Ramsey-teorien - han formodede, at en komplet graf har det mindste Ramsey-tal blandt alle grafer med det samme kromatiske tal. Faudree og McKay (Faudree, McKay, 1993) viste imidlertid, at for W 6 er Ramsey-tallet 17, mens for en komplet graf K 4 med samme kromatiske tal er Ramsey-tallet 18 [4] . For enhver 17-vertex graf G indeholder enten G selv eller dens komplement W 6 som en undergraf, mens hverken 17-vertex Paley-grafen eller dens komplement indeholder K 4 .
Noter
- ↑ Weisstein, Eric W. Wheel Graph på Wolfram MathWorld- webstedet .
- ↑ Richard J. Trudeau. Introduktion til grafteori. — Rettet, udvidet udgivelse. New York: Dover Pub. - S. 56. - ISBN 978-0-486-67870-2 .
- ↑ Fred Buckley, Frank Harary. Om den euklidiske dimension af et hjul // Grafer og kombinatorik. - 1988. - V. 4 , no. 1 . — S. 23–30 . - doi : 10.1007/BF01864150 .
- ↑ Ralph J. Faudree, Brendan D. McKay. En formodning om Erdős og Ramsey-tallet r ( W 6 ) // J. Combinatorial Math. og Combinatorial Comput. - 1993. - T. 13 . — S. 23–31 .