Crown (teorie grafů)

V teorii grafů je 2n -vrcholová koruna neorientovaný graf se dvěma sadami vrcholů u i a v i a hranami mezi u i a v j , pokud i ≠ j . Korunu si můžeme představit jako úplný bipartitní graf s odstraněnou dokonalou shodou , jako dvojitý bipartitní kryt celého grafu nebo jako bipartitní Kneserův graf H n ,1 představující podmnožiny 1 prvku a ( n − 1) prvky množiny n prvků s hranami mezi dvěma podmnožinami, pokud je jedna podmnožina obsažena ve druhé.

Příklady

Koruna se šesti vrcholy tvoří cyklus a koruna s osmi vrcholy je izomorfní s krychlovým grafem . V konfiguraci double six Schläfli s 12 čarami a 30 body v trojrozměrném prostoru se dvanáct čar protíná v korunovém vzoru s 12 vrcholy.

Vlastnosti

Počet hran v koruně je obdélníkové číslo n ( n − 1). Jeho achromatické číslo je n — úplné zbarvení  lze najít výběrem dvojice { u i , v i } jako barevných tříd [1] . Koruny jsou symetrické a vzdálenostně tranzitivní grafy. Archdeacon et al [2] popisují rozdělení okrajů koruny do cyklů stejné délky.

Korunu s 2n vrcholy lze vložit do čtyřrozměrného euklidovského prostoru tak, že všechny její hrany mají délku jedna. Takové vložení však může umístit nesousedící vrcholy ve vzdálenosti jedné. Vložení, kde hrany mají délku jedna a vzdálenost mezi jakýmikoli nesousedními vrcholy není rovna jedné, vyžaduje alespoň rozměr n − 2. To ukazuje, že reprezentovat graf jako graf jednotkových vzdáleností a graf striktně jednotkových vzdáleností jsou požadovány zcela jiné rozměry [3] . Minimální počet úplných bipartitních podgrafů potřebných k pokrytí okrajů koruny (její bipartitní rozměr nebo velikost minimálního pokrytí kliky) je

tedy inverzní funkce centrálního binomického koeficientu [4] .

Doplněk 2n -vrcholové koruny je přímým součinem úplných grafů K 2 K n , což je ekvivalentní 2 ×  n věžovému grafu .

Aplikace

V etiketě  – tradičních pravidlech pro usazování hostů u jídelního stolu – by se muži a ženy měli střídat a žádný manželský pár by neměl sedět vedle sebe. Sezení, které splňuje tato pravidla pro skupinu n párů, lze popsat jako hamiltonovský korónový cyklus. Problém počítání počtu možných uspořádání sedadel nebo, který je téměř stejný [5] jako počet hamiltonovských cyklů v koruně, je v kombinatorice znám jako problém hosta . Pro koróny s 6, 8, 10, … vrcholy je počet (orientovaných) hamiltonovských cyklů

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... OEIS sekvence A094047 .

Koruny lze použít k ukázce toho, že algoritmus chamtivého vybarvování se v některých případech chová špatně – pokud jsou vrcholy koruny algoritmu prezentovány v pořadí u 0 , v 0 , u 1 , v 1 atd., pak se používá chamtivé barvení n barev, i když optimální počet barev jsou dvě. Tato konstrukce je připisována Johnsonovi [6] a samotné koruny se někdy nazývají Johnsonovy grafy s označením J n [7] . Fuhrer [8] použil korunky jako součást konstrukce ukazující složitost aproximace problému zbarvení.

Matushek [9] použil vzdálenost v korónách jako příklad metrického prostoru , který je obtížné vložit do normovaného vektorového prostoru .

Jak ukázali Miklavic a Poroshnik [10] , koruny jsou zahrnuty v malém počtu různých typů grafů, které jsou grafy s regulárním oběžným pohybem vzdálenosti .

Agarwal et al [11] popisují polygony s korunami jako grafy viditelnosti . Používají je jako příklad, aby ukázali, že reprezentovat grafy jako spojení úplných bipartitních grafů není vždy paměťově efektivní.

Koruna s 2n vrcholy s hranami orientovanými z jedné strany bipartitního grafu na druhou tvoří standardní příklad částečně uspořádané množiny s uspořádaným rozměrem n .

Poznámky

  1. ↑ Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: Sborník příspěvků z 8. sympozia ACM-SIAM o diskrétních algoritmech. - 1997. - S. 558-563 .
  2. ↑ D. Arciděkan, M. Debowsky, J. Dinitz, H. Gavlas. Cyklické systémy v kompletním bipartitním grafu mínus jednofaktor // Diskrétní matematika . - 2004. - T. 284 , č. 1-3 . - S. 37-43 . - doi : 10.1016/j.disc.2003.11.021 .
  3. ↑ Paul Erdős, Miklos Simonovits. O chromatickém počtu geometrických grafů // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 .
  4. ↑ Dominique de Caen, David A. Gregory, Norman J. Pullman. Proč. 3rd Caribbean Conference on Combinatorics and Computing / ed. Charles C. Cadogan. - Katedra matematiky, University of the West Indies, 1981. - S. 169-173 .
  5. ↑ V hostujícím problému je počáteční poloha cyklu významná, takže počet hamiltonovských cyklů a řešení hostujícího problému se liší faktorem 2n .
  6. ↑ D.S. Johnson. Proč. 5. jihovýchodní konf. na kombinatoriku, teorii grafů a výpočetní techniku, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Barvy grafů. - American Mathematical Society, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Furer. Proč. 36. IEEE Symp. Základy informatiky (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . - doi : 10.1109/SFCS.1995.492572 .
  9. ↑ Jiří Matoušek. O zkreslení potřebném pro vkládání konečných metrických prostorů do normovaných prostorů // Israel Journal of Mathematics. - 1996. - T. 93 , no. 1 . - S. 333-344 . - doi : 10.1007/BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Distance-regular circulants // European Journal of Combinatorics. - 2003. - T. 24 , no. 7 . - S. 777-784 . - doi : 10.1016/S0195-6698(03)00117-3 .
  11. ↑ Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. Mohou být grafy viditelnosti reprezentovány kompaktně? // Diskrétní a výpočetní geometrie. - 1994. - T. 12 , no. 1 . - S. 347-365 . - doi : 10.1007/BF02574385 .

Odkazy