Kneserův graf - Kneser graph
Kneserův graf | |
---|---|
![]() | |
Pojmenoval podle | Martin Kneser |
Vrcholy | |
Hrany | |
Chromatické číslo | |
Vlastnosti | -pravidelný oblouk-tranzitivní |
Zápis | K.(n, k), KGn,k. |
Tabulka grafů a parametrů |
v teorie grafů, Kneserův graf K.(n, k) (alternativně KGn,k) je graf, jehož vrcholy odpovídají k-prvkové podmnožiny sady n elementy, a kde dva vrcholy sousedí právě tehdy, pokud dva odpovídají množiny jsou disjunktní. Kneserovy grafy jsou pojmenovány po Martin Kneser, který je nejprve vyšetřoval v roce 1955.
Příklady
Kneserův graf K.(n, 1) je kompletní graf na n vrcholy.
Kneserův graf K.(n, 2) je doplněk z hranový graf celého grafu na n vrcholy.
Kneserův graf K.(2n − 1, n − 1) je lichý graf Ón; zejména Ó3 = K.(5, 2) je Petersenův graf.
Vlastnosti
- Kneserův graf K.(n, k) má vrcholy. Každý vrchol má přesně sousedé.
- Kneserův graf je vrchol tranzitivní a oblouk tranzitivní. Není to však obecně a silně pravidelný graf, protože různé páry nesousedících vrcholů mají různý počet společných sousedů v závislosti na velikosti průsečíku odpovídající dvojice množin.
- Protože Kneserovy grafy jsou pravidelný a hrana tranzitivní, jejich konektivita vrcholů rovná se jejich stupeň, až na K.(2k, k) který je odpojen. Přesněji konektivita K.(n, k) je stejný jako počet sousedů na vrchol (Watkins 1970 ).
- Jako Kneser (1955 ) se domníval, že chromatické číslo Kneserova grafu K.(n, k) pro je přesně n − 2k + 2; například Petersenův graf vyžaduje tři barvy v jakémkoli správném vybarvení. László Lovász (1978 ) to prokázal topologickými metodami, které vedly k pole topologická kombinatorika. Brzy poté Imre Bárány (1978 ) poskytl jednoduchý důkaz pomocí Borsuk – Ulamova věta a lemma David Gale a Joshua E. Greene (2002 ) vyhrál Morganova cena pro další zjednodušený, ale stále topologický důkaz. Jiří Matoušek (2004 ) našel čistě kombinatorický důkaz.
- Kneserův graf K.(n, k) obsahuje a Hamiltonovský cyklus pokud (Chen 2003 ):
- Od té doby
- platí pro všechny k tato podmínka je splněna, pokud
- Kneserův graf K.(n, k) obsahuje Hamiltoniánský cyklus, pokud existuje nezáporné celé číslo A takhle (Mütze, Nummenpalo & Walczak 2018 ). Zejména lichý graf Ón má hamiltonovský cyklus, pokud n ≥ 4.
- S výjimkou Petersenova grafu všechny připojené Kneserovy grafy K.(n, k) s n ≤ 27 jsou Hamiltonovci (Štíty 2004 ).
- Když n < 3k, Kneserův graf K.(n, k) neobsahuje žádné trojúhelníky. Obecněji, kdy n < ck neobsahuje kliky velikosti C, zatímco takové kliky obsahuje, když n ≥ ck. Navíc, i když Kneserův graf vždy obsahuje cykly kdykoli o délce čtyři n ≥ 2k + 2, pro hodnoty n blízko k 2k nejkratší lichý cyklus může mít nekonstantní délku (Denley 1997 ).
- The průměr připojeného Kneserova grafu K.(n, k) je (Valencia-Pabon & Vera 2005 ):
- The spektrum Kneserova grafu K.(n, k) skládá se z k + 1 odlišný vlastní čísla:
- navíc nastává s multiplicita pro a má multiplicitu 1. Viz tento papír na důkaz.
- The Erdős – Ko – Radova věta uvádí, že číslo nezávislosti Kneserova grafu K.(n, k) pro je
Související grafy
The Johnsonův graf J(n, k) je graf, jehož vrcholy jsou k-prvkové podmnožiny souboru n- sada prvků, dva vrcholy sousedí, když se setkají v a (k − 1)- sada prvků. Johnsonův graf J(n, 2) je doplněk Kneserova grafu K.(n, 2). Johnsonovy grafy úzce souvisí s Johnsonovo schéma, z nichž oba jsou pojmenovány po Selmer M. Johnson.
The zobecněný Kneserův graf K.(n, k, s) má stejný vrchol nastavený jako Kneserův graf K.(n, k), ale spojuje dva vrcholy, kdykoli odpovídají množinám, které se protínají s nebo méně položek (Denley 1997 ). Tím pádem K.(n, k, 0) = K.(n, k).
The bipartitní Kneserův graf H(n, k) má jako vrcholy množiny k a n − k položky čerpané ze sbírky n elementy. Dva vrcholy jsou spojeny hranou, kdykoli je jedna sada podmnožinou druhé. Stejně jako Kneserův graf je vrcholný tranzitivní se stupněm Bipartitní Kneserův graf může být vytvořen jako a dvojdílný dvojitý kryt z K.(n, k) ve kterém jeden vytvoří dvě kopie každého vrcholu a nahradí každou hranu dvojicí hran spojujících odpovídající dvojice vrcholů (Simpson 1991 ). Bipartitní Kneserův graf H(5, 2) je Desargues graf a bipartitní Kneserův graf H(n, 1) je korunový graf.
Reference
- Bárány, Imre (1978), „Krátký důkaz Kneserova domněnky“, Journal of Combinatorial Theory, Series A, 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, PAN 0514626
- Chen, Ya-Chen (2003), "Grafy Hamiltonian Kneser bez trojúhelníků", Journal of Combinatorial Theory, Series B, 89 (1): 1–16, doi:10.1016 / S0095-8956 (03) 00040-6, PAN 1999733
- Denley, Tristan (1997), „Zvláštní obvod zobecněného Kneserova grafu“, European Journal of Combinatorics, 18 (6): 607–611, doi:10.1006 / eujc.1996.0122, PAN 1468332
- Greene, Joshua E. (2002), „Nový krátký důkaz Kneserova domněnky“, Americký matematický měsíčník, 109 (10): 918–920, doi:10.2307/3072460, JSTOR 3072460, PAN 1941810
- Kneser, Martin (1955), „Aufgabe 360“, Jahresbericht der Deutschen Mathematiker-Vereinigung, 58 (2): 27
- Lovász, László (1978), „Kneserova domněnka, chromatické číslo a homotopie“, Journal of Combinatorial Theory, Řada A, 25 (3): 319–324, doi:10.1016/0097-3165(78)90022-5, hdl:10338.dmlcz / 126050, PAN 0514625
- Matoušek, Jiří (2004), „Kombinatorický důkaz Kneserovy domněnky“, Combinatorica, 24 (1): 163–170, doi:10.1007 / s00493-004-0011-1, hdl:20.500.11850/50671, PAN 2057690
- Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), „Sparse Kneser graphs are Hamiltonian“, STOC'18 - sborník z 50. výročního sympozia ACM SIGACT o teorii práce s počítačem, New York: ACM, s. 912–919, arXiv:1711.01636, PAN 3826304
- Štíty, Ian Beaumont (2004), Heuristika Hamiltonova cyklu v tvrdých grafech, Ph.D. teze, Státní univerzita v Severní Karolíně, archivovány z originál dne 2006-09-17, vyvoláno 2006-10-01
- Simpson, J. E. (1991), „Hamiltonovské bipartitní grafy“, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, 85, s. 97–110, PAN 1152123
- Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), „O průměru Kneserových grafů“, Diskrétní matematika, 305 (1–3): 383–385, doi:10.1016 / j.disc.2005.10.001, PAN 2186709
- Watkins, Mark E. (1970), „Konektivita tranzitivních grafů“, Journal of Combinatorial Theory, 8: 23–29, doi:10.1016 / S0021-9800 (70) 80005-9, PAN 0266804