Lichý graf

V teorii grafů jsou liché grafy O n  rodinou symetrických grafů s vysokým lichým obvodem definovaným na některých rodinách množin . Zahrnují a zobecňují Petersenovy grafy .

Definice a příklady

Lichý graf O n má jeden vrchol pro každou z ( n  − 1)-prvkových podmnožin množiny (2 n  − 1) prvků. Dva vrcholy jsou spojeny hranou právě tehdy, když se odpovídající podmnožiny neprotínají [4] . O n  je tedy Kneserův graf KG (2 n  − 1, n  − 1), O 2  je trojúhelník a O 3  je známý Petersenův graf .

Zobecněné liché grafy zahrnují liché grafy a skládací kubické grafy, a jsou definovány jako vzdálenostně pravidelné grafy s průměrem n  − 1 a lichým obvodem 2 n  − 1 pro nějaké n [5] .

Historie a aplikace

Přestože jsou Petersenovy grafy známy již od roku 1898, jejich definice jako „liché grafy“ pochází již od Kowalewského [6] , ve kterém studuje lichý graf O 4 [2] [6] . Liché grafy jsou studovány díky jejich použití v chemické teorii grafů při modelování posunu uhlíkových iontů .[7] [8] . Používají se také jako topologie sítě v paralelních výpočtech [9] .

Zápis O n pro tyto grafy navrhl Norman Biggsv roce 1972 [10] . Biggs a Tony Gardinervysvětlit název lichých grafů v nepublikované monografii z roku 1974 – každá hrana lichého grafu může být spojena s jedním prvkem X , což je „odd man out“ (což lze přeložit jako „hráč bez partnera opustí hru“ ), to znamená, že prvek nepatří do žádné jiné podmnožiny spojené s vrcholy dopadajícími na danou hranu [11] [12] .

Vlastnosti

Lichý graf O n je pravidelný graf stupně n . Má vrcholy a hrany. Takže počet vrcholů pro n = 1, 2,… bude

1, 3, 10, 35, 126, 462, 1716, 6435 (sekvence A001700 v OEIS ).

Vzdálenost a symetrie

Pokud dva vrcholy v O n odpovídají množinám stejné velikosti, které se liší o k prvků, pak můžete získat druhý z prvního ve 2 k krocích, přičemž v každém kroku odeberete nebo přidáte jeden prvek. Jestliže 2 k  <  n , pak je to nejkratší cesta . V opačném případě můžete najít kratší cestu tohoto typu, pokud začnete s doplňkovou sadou k druhé sadě a pak získáte druhou sadu tím, že uděláte ještě jeden krok. Průměr grafu O n je tedy roven n  − 1 [1] [2] .

Libovolný lichý graf je 3obloukový tranzitivní  — jakákoliv orientovaná tříhranná cesta v lichém grafu může být mapována na jakoukoli takovou cestu pomocí grafové symetrie [13] . Liché grafy jsou vzdálenostně tranzitivní , protože jsou na vzdálenost regulární [2] . Jako vzdálenost-regulární grafy jsou jednoznačně definovány jejich polem průniků – žádný jiný vzdálenost-regulární graf nemůže mít stejné parametry jako lichý graf [14] . Navzdory vysokému stupni symetrie však liché O n grafy pro n  > 2 nikdy nejsou Cayleyovými grafy [15] .

Liché grafy s n ≥ 3 mají obvod šest. Přestože se nejedná o bipartitní grafy , jejich liché cykly jsou mnohem delší, konkrétně lichý graf O n má lichý obvod 2 n  − 1. Pokud má n - pravidelný graf průměr n  − 1, je lichý obvod 2 n  − 1 a pouze n různých vlastních hodnot , musí být regulární na vzdálenost. Vzdálenostně pravidelné grafy o průměru n  − 1 a lichém obvodu 2n  − 1 jsou známé jako zobecněné liché grafy a zahrnují skládací kubické grafystejně jako samotné liché grafy [5] .

Nezávislé množiny a barvení vrcholů

Nechť O n  je lichý graf definovaný na (2 n  − 1)-prvkových podmnožinách X , a nechť x  jsou prvky X . Potom mezi O n vrcholy přesně vrcholy odpovídají množinám, které obsahují x . Protože všechny tyto množiny obsahují x , nejsou disjunktní a tvoří nezávislou množinu grafu O n . O n má tedy 2 n  − 1 odlišných nezávislých souborů velikosti . Z Erdős–Ko–Rado větyz toho vyplývá, že se jedná o maximální nezávislé množiny grafu O n . Číslo nezávislosti grafu O n je tedy Navíc každá maximální nezávislá množina musí mít tento tvar, takže O n má právě 2 n  − 1 maximálních nezávislých množin [2] .

Jestliže I  je maximální nezávislá množina tvořená množinou obsahující prvek x , pak doplněk množiny I  je množina vrcholů, které neobsahují x . Tento doplněk generuje shodu v G . Každý vrchol nezávislé množiny sousedí s n vrcholy shody a každý vrchol shody sousedí s n  − 1 vrcholy nezávislé množiny [2] . Vzhledem k tomuto rozkladu a vzhledem k tomu, že liché grafy nejsou bipartitní, mají chromatické číslo rovné třem - jednu barvu lze přiřadit vrcholům maximální nezávislé množiny a dvě další barvy lze získat z shoda generovaná doplňkem.

Barvení okrajů

Podle Vizingova teorému je počet barev potřebných k obarvení hran lichého grafu O n buď n nebo n  + 1, a v případě Petersenových grafů O 3 je to n  + 1. Je-li n  mocninou dvou, počet vrcholů v grafu je lichý, z čehož opět vyplývá, že počet barev při zbarvení hran je n  + 1 [16] . O 5 , O 6 a O 7 však mohou být obarveny n barvami [2] [16] .

Biggs [10] vysvětluje tento problém následujícím příběhem: Jedenáct fotbalistů ve fiktivním městě Kroam chce vytvořit dvojice futsalových týmů (jeden člověk zbývá rozhodovat zápas) všemi 1386 různými způsoby a chtějí naplánovat zápasy mezi všemi dvojicemi. , přičemž šest zápasů pro každý tým musí být odehráno v různé dny v týdnu, při absenci her v neděli. Je to možné? V tomto příběhu každá hra představuje hranu O 6 , všechny dny jsou znázorněny barvami a 6barevné zbarvení hrany grafu O 6 dává rozvrh.

Liché grafy a hamiltonovské grafy

Petersenův graf O 3  jsou dobře známé nehamiltonovské grafy, ale ukázalo se, že grafy O 4 až O 14 obsahují hamiltonovské cykly [8] [17] [18] [19] . Přesněji řečeno, kombinací problémů hledání hamiltonovských cyklů a barvení hran lze rozdělit hrany grafu O n (pro n = 4, 5, 6, 7) na nejbližší nižší celé číslo z ( n /2) hamiltonovských cyklů. . Je-li n liché, tvoří zbývající hrany dokonalou kombinaci [2] [16] . Pro n  = 8 lichý počet vrcholů v O n neumožňuje obarvit hrany 8 barvami, ale neuzavírá možnost rozkladu do čtyř hamiltonovských cyklů.

Lovasův Hamiltonův odhad cyklu předpokládá, že každý lichý graf má hamiltonovskou cestu a že každý lichý O n graf s n  ≥ 4 má hamiltonovský cyklus.

Poznámky

  1. ↑ 1 2 Norman L. Biggs. Automorfní grafy a Kerinův stav // Geometriae Dedicata. - 1976. - Vydání. 5 . - S. 117-127 . - doi : 10.1007/BF00148146 .
  2. ↑ 1 2 3 4 5 6 7 8 Biggs, 1979
  3. ↑ Douglas B. West. Úvod do teorie grafů. — 2. - Englewood Cliffs, NJ: Prentice-Hall, 2000. - S. 17.
  4. ↑ Weisstein, Eric W. Odd Graph  na webu Wolfram MathWorld .
  5. ↑ 1 2 Edwin Van Dam, Willem H. Haemers. Lichá charakterizace zobecněných lichých grafů. — 2010.
  6. ↑ 1 2 A. Kowalewski. WR Hamiltonův Dodekaederaufgabe als Buntordnungproblem // Sitzungsber. Akad. Wiss. Vídeň (Abt. IIa). - 1917. - T. 126 . - S. 67-90, 963-1007 . Jak je uvedeno v Biggs ( Biggs 1979 ).
  7. ↑ Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ. Grafy vícenásobných 1, 2-posunů v karboniových iontech a příbuzných systémech // Rev. pokoj, místnost. Chim.. - 1966. - T. 11 . - S. 1205 .
  8. ↑ 1 2 Alexandru T. Balaban. Chemické grafy, Část XIII: Kombinatorické vzory // Rev. Roumainská matematika. Pures Appl.. - 1972. - svazek 17 . - str. 3-16 .
  9. ↑ Arif Ghafoor, Theodore R. Bashkow. Studie lichých grafů jako propojovacích sítí odolných vůči chybám // IEEE Transactions on Computing. - 1991. - T. 40 , no. 2 . - S. 225-232 . - doi : 10.1109/12.73594 .
  10. ↑ 1 2 Norman Biggs. Výzkumné problémy  // Americký matematický měsíčník. - 1972. - T. 79 , čís. 9 . - S. 1018-1020 . — .
  11. ↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Vzdálenost-regulární grafy. - 1989. - ISBN 0-387-50619-5 .
  12. ↑ Ed Pegg, Jr. Kubické symetrické grafy. - Mathematical Association of America , 2003. Archivováno z originálu 21. srpna 2010.
  13. ↑ Laszlo Babai. Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. - North-Holland, 1995. - T. I. - S. 1447-1540.
  14. ↑ Měsíc Aeryung. Charakterizace lichých grafů O k pomocí parametrů // Diskrétní matematika. - 1982. - T. 42 , čís. 1 . - S. 91-97 . - doi : 10.1016/0012-365X(82)90057-7 .
  15. ↑ CD Godsil. Podivnější teorie grafů // Diskrétní matematika. - 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. Fotbalisté Croamu // Journal of Combinatorial Theory, řada B. - 1973. - T. 15 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
  17. ↑ Guy HJ Meredith, E. Keith Lloyd. Kombinatorika (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Southend: Inst. Matematika. Appl, 1972. - S. 229-236 .
  18. ↑ Michael Matka. The Rugby footballers of 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. Poznámka k Hamiltonovým cyklům v Kneserových grafech // Bulletin Institutu pro kombinatoriku a její aplikace. - 2004. - T. 40 . - S. 13-22 .

Literatura