Ulige graf

I grafteori er ulige grafer O n  en familie af symmetriske grafer med høj ulige omkreds defineret på nogle familier af sæt . De inkluderer og generaliserer Petersen-graferne .

Definitioner og eksempler

Den ulige graf O n har et toppunkt for hver af ( n  − 1)-element-delmængderne af sættet af (2 n  − 1) elementer. To hjørner er forbundet med en kant, hvis og kun hvis de tilsvarende delmængder ikke skærer hinanden [4] . Så O n  er Kneser-grafen KG (2 n  − 1, n  − 1), O 2  er en trekant, og O 3  er den velkendte Petersen-graf .

Generaliserede ulige grafer omfatter ulige grafer og foldekubiske grafer, og er defineret som afstand-regulære grafer med diameter n  − 1 og ulige omkreds 2 n  − 1 for nogle n [5] .

Historie og applikationer

Selvom Petersen-grafer har været kendt siden 1898, går deres definition som "ulige grafer" tilbage til Kowalewski [6] , hvor han studerer den ulige O 4 -graf [2] [6] . Ulige grafer studeres på grund af deres brug i kemisk grafteori til modellering af skiftet af kulstofioner .[7] [8] . De bruges også som netværkstopologi i parallel computing [9] .

O n - notationen for disse grafer blev foreslået af Norman Biggsi 1972 [10] . Biggs og Tony Gardinerforklar navnet på ulige grafer i en upubliceret monografi fra 1974 - hver kant af en ulige graf kan associeres med et enkelt element X , som er "ulige mand ud" (som kan oversættes som "en spiller uden en partner forlader spillet" ), det vil sige, at elementet ikke tilhører nogen anden delmængde forbundet med toppunkter, der falder ind på den givne kant [11] [12] .

Egenskaber

En ulige graf O n er en regulær graf af grad n . Den har spidser og kanter. Så antallet af hjørner for n = 1, 2,... vil være

1, 3, 10, 35, 126, 462, 1716, 6435 (sekvens A001700 i OEIS ).

Afstand og symmetri

Hvis to hjørner i O n svarer til sæt af samme størrelse, der adskiller sig med k elementer, så kan du få det andet fra det første i 2 k trin, fjerne eller tilføje et element ved hvert trin. Hvis 2 k  <  n , så er dette den korteste vej . Ellers kan du finde en kortere vej af denne type, hvis du starter med et komplementært sæt til det andet sæt, og derefter får det andet sæt ved at tage et skridt mere. Diameteren af ​​grafen O n er altså lig med n  − 1 [1] [2] .

Enhver ulige graf er 3-bue-transitiv  - enhver orienteret trekantssti i en ulige graf kan kortlægges til enhver sådan vej ved hjælp af grafsymmetri [13] . Ulige grafer er afstandstransitive, fordi de er afstandsregulære [2] . Som afstand-regulære grafer er de unikt defineret af deres skæringsarray - ingen anden afstand-regulær graf kan have de samme parametre som en ulige graf [14] . På trods af den høje grad af symmetri er ulige O n -grafer for n  > 2 dog aldrig Cayley- grafer [15] .

Ulige grafer med n ≥ 3 har omkreds seks. Men selvom de ikke er todelte grafer , er deres ulige cyklusser meget længere, nemlig den ulige graf O n har ulige omkreds 2 n  − 1. Hvis en n - regulær graf har diameter n  − 1, er den ulige omkreds 2 n  − 1 og kun n forskellige egenværdier skal den være afstandsregulær. Afstandsregulære grafer med diameter n  − 1 og ulige omkreds 2n  ​​− 1 er kendt som generaliserede ulige grafer og inkluderer foldekubiske graferligesom de ulige grafer selv [5] .

Uafhængige sæt og vertexfarvning

Lad O n  være en ulige graf defineret på (2 n  − 1)-elementdelmængder af X , og lad x  være elementer af X . Så blandt O n toppunkter svarer nøjagtigt toppunkter til mængder, der indeholder x . Da alle disse mængder indeholder x , er de ikke usammenhængende og danner et uafhængigt sæt af grafen O n . O n har således 2 n  − 1 forskellige uafhængige sæt af størrelse . Fra Erdős-Ko-Rado-sætningendet følger, at disse er de maksimale uafhængige sæt af grafen O n . Således er uafhængighedstallet for grafen O n . Desuden skal enhver maksimal uafhængig mængde have denne form, så O n har præcis 2 n  − 1 maksimale uafhængige mængder [2] .

Hvis I  er den maksimale uafhængige mængde dannet af mængden, der indeholder elementet x , så er komplementet af mængden I  mængden af ​​hjørner, der ikke indeholder x . Dette komplement genererer en matchning i G. Hvert toppunkt i det uafhængige sæt støder op til n toppunkter af matchningen, og hvert toppunkt i matchningen støder op til n  − 1 toppunkter i det uafhængige sæt [2] . I lyset af denne nedbrydning og i lyset af det faktum, at ulige grafer ikke er todelte, har de et kromatisk tal , der er lig med tre - en farve kan tildeles hjørnerne af det maksimale uafhængige sæt, og to andre farver kan fås fra matchningen genereret af komplementet.

Kantfarvning

Ved Vizings sætning er antallet af farver, der skal til for at farve kanterne af en ulige graf O n enten n eller n  + 1, og i tilfældet med Petersen grafer O 3 er det n  + 1. Hvis n  er en potens af to, antallet af hjørner i grafen er ulige, hvoraf det igen følger, at antallet af farver i en kantfarvning er n  + 1 [16] . O 5 , O 6 og O 7 kan dog farves med n farver [ 2] [16] .

Biggs [10] forklarer dette problem med følgende historie: Elleve fodboldspillere i den fiktive by Kroam ønsker at danne par af futsalhold ( en person er tilbage til at dømme kampen) på alle 1386 forskellige måder og ønsker at planlægge kampe mellem alle par. , med seks kampe for hvert hold skal spilles på forskellige dage i ugen, i mangel af kampe om søndagen. Er det muligt? I denne historie repræsenterer hvert spil en kant O 6 , alle dage er repræsenteret af farver, og en 6-farvet kantfarvning af grafen O 6 giver tidsplanen.

Ulige grafer og Hamiltonske grafer

Petersen-grafen O 3  er velkendte ikke-hamiltonske grafer, men graferne O 4 til O 14 har vist sig at indeholde Hamiltonske cyklusser [8] [17] [18] [19] . Mere stringent kan man ved at kombinere problemerne med at finde Hamiltonske cyklusser og kantfarvning opdele kanterne af grafen O n (for n = 4, 5, 6, 7) i det nærmeste lavere heltal fra ( n /2) Hamiltonske cyklusser . Hvis n er ulige, danner de resterende kanter en perfekt kombination [2] [16] . For n  = 8 tillader et ulige antal hjørner i O n ikke, at kanterne farves med 8 farver, men lukker ikke muligheden for at nedbrydes i fire Hamiltonske cyklusser.

Lovas' Hamiltonske cyklusformodning antager, at hver ulige graf har en Hamiltonsk bane, og at hver ulige O n -graf med n  ≥ 4 har en Hamiltonsk cyklus.

Noter

  1. ↑ 1 2 Norman L. Biggs. Automorfe grafer og Kerin-tilstanden // Geometriae Dedicata. - 1976. - Udgave. 5 . - S. 117-127 . - doi : 10.1007/BF00148146 .
  2. ↑ 1 2 3 4 5 6 7 8 Biggs, 1979
  3. ↑ Douglas B. West. Introduktion til grafteori. — 2. - Englewood Cliffs, NJ: Prentice-Hall, 2000. - S. 17.
  4. ↑ Weisstein, Eric W. Odd Graph  på Wolfram MathWorld- webstedet .
  5. ↑ 1 2 Edwin Van Dam, Willem H. Haemers. En ulige karakterisering af de generaliserede ulige grafer. – 2010.
  6. ↑ 1 2 A. Kowalewski. WR Hamiltons Dodekaederaufgabe som Buntordnungproblem // Sitzungsber. Akad. Wiss. Wien (Abt. IIa). - 1917. - T. 126 . - S. 67-90, 963-1007 . Som citeret i Biggs ( Biggs 1979 ).
  7. ↑ Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ. Grafer over flere 1, 2-skift i carboniumioner og relaterede systemer // Rev. værelse. Chim.. - 1966. - T. 11 . - S. 1205 .
  8. ↑ 1 2 Alexandru T. Balaban. Kemiske grafer, del XIII: Kombinatoriske mønstre // Rev. Roumaine matematik. Pures Appl.. - 1972. - Vol . 17 . - S. 3-16 .
  9. ↑ Arif Ghafoor, Theodore R. Bashkow. En undersøgelse af ulige grafer som fejltolerante sammenkoblingsnetværk // IEEE Transactions on Computing. - 1991. - T. 40 , no. 2 . - S. 225-232 . - doi : 10.1109/12.73594 .
  10. ↑ 1 2 Norman Biggs. Forskningsproblemer  // American Mathematical Monthly. - 1972. - T. 79 , no. 9 . - S. 1018-1020 . — .
  11. ↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Afstandsregulære grafer. - 1989. - ISBN 0-387-50619-5 .
  12. ↑ Ed Pegg, Jr. Kubiske symmetriske grafer. - Mathematical Association of America , 2003. Arkiveret fra originalen den 21. august 2010.
  13. ↑ Laszlo Babai. Håndbog i kombinatorik / Ronald L. Graham, Martin Grötschel, László Lovász. - Nord-Holland, 1995. - T. I. - S. 1447-1540.
  14. ↑ Aeryung Moon. Karakterisering af de ulige grafer O k ved parametre // Diskret matematik. - 1982. - T. 42 , no. 1 . - S. 91-97 . - doi : 10.1016/0012-365X(82)90057-7 .
  15. ↑ CD Godsil. Mere mærkelig grafteori // Diskret matematik. - 1980. - T. 32 , no. 2 . - S. 205-207 . - doi : 10.1016/0012-365X(80)90055-2 .
  16. ↑ 1 2 3 Guy HJ Meredith, E. Keith Lloyd. Fodboldspillerne fra Croam // Journal of Combinatorial Theory, Series B. - 1973. - T. 15 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
  17. ↑ Guy HJ Meredith, E. Keith Lloyd. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Southend: Inst. Matematik. Appl., 1972. - S. 229-236 .
  18. ↑ Michael Mor. Rugby-fodboldspillerne fra Croam // Journal of Combinatorial Theory, Series B. - 1976. - V. 20 . - S. 62-63 . - doi : 10.1016/0095-8956(76)90066-6 .
  19. ↑ Ian Shields, Carla D. Savage. En note om Hamilton-cyklusser i Kneser-grafer // Bulletin fra Institute for Combinatorics and Its Applications. - 2004. - T. 40 . - S. 13-22 .

Litteratur