Krona (grafteori)

I grafteorin är en 2n -vertexkrona en oriktad graf med två uppsättningar av hörn u i och v i och kanter mellan u i och v j om i ≠ j . Man kan tänka på kronan som en komplett tvådelad graf från vilken en perfekt matchning har tagits bort , som ett dubbelt tvådelat graftäcke av hela grafen , eller som en Kneser tvådelad graf Hn , 1 som representerar delmängder av 1 element och ( n− 1) element i en n - elementuppsättning med kanter mellan två delmängder om en delmängd ingår i den andra.

Exempel

En krona med sex hörn bildar en cykel , och en krona med åtta hörn är isomorf till en kubgraf . I den dubbla sex Schläfli- konfigurationen med 12 linjer och 30 punkter i tredimensionell rymd, skär tolv linjer varandra i ett kronmönster med 12 hörn.

Egenskaper

Antalet kanter i kronan är ett rektangulärt tal n ( n − 1). Dess akromatiska nummer är n  — man kan hitta en komplett färgning genom att välja ett par { u i , v i } som färgklasser [1] . Kronor är symmetriska och distanstransitiva grafer. Archdeacon et al [2] beskriver uppdelningen av kronans kanter i lika långa cykler.

En krona med 2n hörn kan bäddas in i ett fyrdimensionellt euklidiskt utrymme på ett sådant sätt att alla dess kanter har längden ett. En sådan inbäddning kan emellertid placera icke-angränsande hörn på ett avstånd av ett. Inbäddning där kanterna har längden ett och avståndet mellan eventuella icke-angränsande hörn inte är lika med ett kräver åtminstone dimensionen n − 2. Detta visar att för att representera en graf som en graf över enhetsavstånd och en graf med strikt enhetsavstånd krävs helt andra dimensioner [3] . Det minsta antalet kompletta tvådelade subgrafer som krävs för att täcka kanterna på kronan (dess tvådelade dimension eller storleken på den minsta klicktäckningen) är

det vill säga den inversa funktionen av den centrala binomialkoefficienten [4] .

Komplementet av en 2n -vertexkrona är den direkta produkten av kompletta grafer K 2 K n , vilket motsvarar en 2 ×  n torngraf .

Applikation

I etiketten  - de traditionella reglerna för att sitta gäster vid middagsbordet - ska män och kvinnor växla om varandra och inga gifta par ska sitta sida vid sida. En sittplats som uppfyller dessa regler för ett sällskap med n par kan beskrivas som en Hamiltonsk coronacykel. Problemet med att räkna antalet möjliga sittarrangemang eller, vilket är nästan samma [5] som antalet Hamiltonska cykler i kronan, är känt inom kombinatoriken som gästproblemet . För koronor med 6, 8, 10, … hörn är antalet (orienterade) Hamilton-cykler

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

Kronor kan användas för att visa att en girig färgningsalgoritm beter sig dåligt i vissa fall — om kronans hörn presenteras för algoritmen i ordningen u 0 , v 0 , u 1 , v 1 , etc., så används girig färgning n färger, även om det optimala antalet färger är två. Denna konstruktion tillskrivs Johnson [6] , och själva kronorna kallas ibland Johnson-grafer med notationen J n [7] . Fuhrer [8] använde kronor som en del av en konstruktion som visar komplexiteten i att approximera färgproblemet.

Matushek [9] använde avstånd i koronor som ett exempel på ett metriskt utrymme som är svårt att bädda in i ett normerat vektorrum .

Som visat av Miklavic och Poroshnik [10] ingår kronor i ett litet antal olika typer av grafer som är avståndsregelbundna cirkulerande grafer .

Agarwal et al [11] beskriver polygoner som har kronor som synlighetsgrafer . De använder dem som ett exempel för att visa att det inte alltid är minneseffektivt att representera grafer som en förening av kompletta tvådelade grafer.

En krona med 2n hörn med kanter orienterade från ena sidan av en tvådelad graf till den andra bildar ett standardexempel på en delvis ordnad uppsättning med ordningsmått n .

Anteckningar

  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. Cykelsystem i den kompletta tvådelade grafen minus en enfaktor // Diskret matematik . - 2004. - T. 284 , nr. 1-3 . - S. 37-43 . - doi : 10.1016/j.disc.2003.11.021 .
  3. ↑ Paul Erdős, Miklos Simonovits. På det kromatiska antalet geometriska grafer // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 .
  4. ↑ Dominique de Caen, David A. Gregory, Norman J. Pullman. Proc. 3rd Caribbean Conference on Combinatorics and Computing / ed. Charles C. Cadogan. - Matematiska institutionen, University of the West Indies, 1981. - S. 169-173 .
  5. ↑ I gästproblemet är cykelns initiala position signifikant, så antalet Hamilton-cykler och lösningen på gästproblemet skiljer sig med en faktor 2n .
  6. ↑ D.S. Johnson. Proc. 5th Southeastern Conf. om kombinatorik, grafteori och beräkning, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Graffärger. - American Mathematical Society, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Furer. Proc. 36:e IEEE Symp. Grunderna för datavetenskap (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . - doi : 10.1109/SFCS.1995.492572 .
  9. ↑ Jiri Matousek. Om förvrängningen som krävs för att bädda in finita metriska utrymmen i normerade utrymmen // Israel Journal of Mathematics. - 1996. - T. 93 , nr. 1 . - S. 333-344 . - doi : 10.1007/BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Avståndsregelbundna cirkulanter // European Journal of Combinatorics. - 2003. - T. 24 , nr. 7 . - S. 777-784 . - doi : 10.1016/S0195-6698(03)00117-3 .
  11. ↑ Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. Kan synlighetsgrafer representeras kompakt? // Diskret och beräkningsgeometri. - 1994. - T. 12 , nr. 1 . - S. 347-365 . - doi : 10.1007/BF02574385 .

Länkar