Krone (grafteori)

I grafteori er en 2n -vertex- krone en urettet graf med to sæt toppunkter u i og v i og kanter mellem u i og v j hvis i ≠ j . Man kan tænke på kronen som en komplet todelt graf , hvorfra en perfekt matchning er blevet fjernet , som et dobbelt todelt grafdæksel af hele grafen , eller som en Kneser todelt graf Hn , 1, der repræsenterer delmængder af 1 element og ( n− 1) elementer af et n - elementsæt med kanter mellem to delmængder, hvis den ene delmængde er indeholdt i den anden.

Eksempler

En krone med seks hjørner danner en cyklus , og en krone med otte hjørner er isomorf i forhold til en terninggraf . I den dobbelte seks Schläfli -konfiguration med 12 linjer og 30 punkter i tredimensionelt rum, skærer tolv linjer hinanden i et kronemønster med 12 hjørner.

Egenskaber

Antallet af kanter i kronen er et rektangulært tal n ( n − 1). Dens akromatiske tal er n  — man kan finde en komplet farvelægning ved at vælge et par { u i , v i } som farveklasser [1] . Kroner er symmetriske og afstandstransitive grafer. Archdeacon et al . [2] beskriver opdelingen af ​​kronens kanter i cykler af samme længde.

En krone med 2n hjørner kan indlejres i et firedimensionalt euklidisk rum på en sådan måde, at alle dens kanter har længden en. En sådan indlejring kan imidlertid placere ikke-tilstødende hjørner i en afstand af én. Indlejring, hvor kanterne har længde 1, og afstanden mellem eventuelle ikke-tilstødende hjørner ikke er lig med 1, kræver mindst dimensionen n − 2. Dette viser, at for at repræsentere en graf som en graf over enhedsafstande og en graf med strengt enhedsafstande , kræves helt andre dimensioner [3] . Det mindste antal komplette todelte undergrafer , der kræves for at dække kanterne af kronen (dens todelte dimension eller størrelsen af ​​den mindste klikdækning) er

det vil sige den inverse funktion af den centrale binomiale koefficient [4] .

Komplementet af en 2n -vertex krone er det direkte produkt af komplette grafer K 2 K n , hvilket svarer til en 2 ×  n tårngraf .

Ansøgning

I etikette  - de traditionelle regler for at sidde gæster ved middagsbordet - bør mænd og kvinder skiftes, og intet ægtepar bør sidde side om side. En siddeplads, der opfylder disse regler for et selskab på n par, kan beskrives som en Hamiltonsk corona-cyklus. Problemet med at tælle antallet af mulige siddearrangementer eller, som er næsten det samme [5] som antallet af Hamiltonske cyklusser i kronen, er kendt i kombinatorik som gæsteproblemet . For koronaer med 6, 8, 10, … hjørner er antallet af (orienterede) Hamiltonske cyklusser

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... OEIS -sekvens A094047 .

Kroner kan bruges til at vise, at en grådig farvealgoritme opfører sig dårligt i nogle tilfælde - hvis hjørnerne af en krone præsenteres for algoritmen i rækkefølgen u 0 , v 0 , u 1 , v 1 osv., så bruger grådig farvelægning n farver, selvom det optimale antal farver er to. Denne konstruktion tilskrives Johnson [6] , og selve kronerne kaldes undertiden Johnson-grafer med notationen J n [7] . Fuhrer [8] brugte kroner som en del af en konstruktion, der viser kompleksiteten i at tilnærme farveproblemet.

Matushek [9] brugte afstand i koronaer som et eksempel på et metrisk rum , der er svært at indlejre i et normeret vektorrum .

Som vist af Miklavic og Poroshnik [10] indgår kroner i et lille antal forskellige typer grafer, der er afstandsregulære cirkulerende grafer .

Agarwal et al . [11] beskriver polygoner med kroner som synlighedsgrafer . De bruger dem som et eksempel for at vise, at det ikke altid er hukommelseseffektivt at repræsentere grafer som en forening af komplette todelte grafer.

En krone med 2n spidser med kanter orienteret fra den ene side af en todelt graf til den anden danner et standardeksempel på et delvist ordnet sæt med ordensmål n .

Noter

  1. ↑ Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. - 1997. - S. 558-563 .
  2. ↑ D. Archdeacon, M. Debowsky, J. Dinitz, H. Gavlas. Cyklussystemer i den komplette todelte graf minus en enfaktor // Diskret matematik . - 2004. - T. 284 , no. 1-3 . - S. 37-43 . - doi : 10.1016/j.disc.2003.11.021 .
  3. ↑ Paul Erdős, Miklos Simonovits. På det kromatiske antal af geometriske grafer // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 .
  4. ↑ Dominique de Caen, David A. Gregory, Norman J. Pullman. Proc. 3. Caribbean Conference on Combinatorics and Computing / red. Charles C. Cadogan. - Institut for Matematik, Universitetet i Vestindien, 1981. - S. 169-173 .
  5. ↑ I gæsteproblemet er startpositionen af ​​cyklussen signifikant, så antallet af Hamiltonske cyklusser og løsningen på gæsteproblemet adskiller sig med en faktor på 2n .
  6. ↑ D.S. Johnson. Proc. 5. sydøstlige konf. om kombinatorik, grafteori og databehandling, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Graffarver. - American Mathematical Society, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Furer. Proc. 36. IEEE Symp. Fundamenter for datalogi (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . - doi : 10.1109/SFCS.1995.492572 .
  9. ↑ Jiri Matousek. Om den forvrængning, der kræves for at indlejre endelige metriske rum i normerede rum // Israel Journal of Mathematics. - 1996. - T. 93 , no. 1 . - S. 333-344 . - doi : 10.1007/BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Distance-regulære cirkulanter // 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. Kan synlighedsgrafer repræsenteres kompakt? // Diskret og beregningsgeometri. - 1994. - T. 12 , no. 1 . - S. 347-365 . - doi : 10.1007/BF02574385 .

Links