Korona (gráfelmélet)

A gráfelméletben a 2n csúcsú korona egy irányítatlan gráf két u i és v i csúcskészlettel , valamint u i és v j közötti élekkel, ha i ≠ j . A koronát úgy tekinthetjük, mint egy teljes kétrészes gráfot , amelyből a tökéletes illeszkedést eltávolítottuk , a teljes gráf kettős kétrészes gráffedőjének , vagy egy H n ,1 Kneser-féle kétrészes gráfnak , amely 1 elem és ( n − ) részhalmazait reprezentálja. 1) egy n elemű halmaz elemei két részhalmaz között élekkel, ha az egyik részhalmaz a másikban található.

Példák

A hat csúcsú korona ciklust alkot , a nyolc csúcsú korona pedig izomorf egy kockagráfhoz . A háromdimenziós térben 12 vonalból és 30 pontból álló kettős hat Schläfli - konfigurációban tizenkét vonal metszi egymást 12 csúcsos koronamintázatban.

Tulajdonságok

A korona éleinek száma egy n ( n − 1) téglalap szám . Akromatikus száma n  — a teljes színezést úgy találhatjuk meg, ha színosztályként egy { u i , v i } párt választunk [1] . A koronák szimmetrikus és távolságtranzitív gráfok. Archdeacon és munkatársai [2] a korona éleinek egyenlő hosszúságú ciklusokra való felosztását írják le.

Egy 2n csúcsú korona beágyazható egy négydimenziós euklideszi térbe úgy, hogy minden éle egy hosszúságú legyen. Egy ilyen beágyazás azonban nem szomszédos csúcsokat is elhelyezhet egy távolságra. A beágyazáshoz, ahol az élek hossza egy, és a nem szomszédos csúcsok távolsága nem egyenlő eggyel, legalább az n − 2 méretre van szükség. Ez azt mutatja, hogy a gráf egységnyi távolságok grafikonjaként és szigorúan egységnyi távolságok grafikonjaként való ábrázolásához , teljesen más méretekre van szükség [3 ] . A korona széleinek lefedéséhez szükséges teljes kétrészes részgráfok minimális száma (a kétrészes dimenziója vagy a minimális klikk lefedettség mérete)

vagyis a centrális binomiális együttható inverz függvénye [4] .

A 2n csúcsú korona komplementere a K 2 K n teljes gráfok közvetlen szorzata , ami ekvivalens egy 2 ×  n -es rook gráfnak .

Alkalmazás

Az etikettben  – a vendégek vacsoraasztalhoz ültetésének hagyományos szabályai szerint – a férfiaknak és a nőknek felváltva kell lenniük, és egyetlen házaspár sem ülhet egymás mellett. Hamiltoni koronaciklusnak nevezhető egy ülőhely, amely megfelel ezeknek a szabályoknak egy n párból álló társaság számára. A lehetséges ülőalkalmazottak számának megszámlálásának problémáját, vagy ami közel azonos [5] a korona Hamilton-ciklusainak számával, a kombinatorika vendégproblémaként ismeri . A 6, 8, 10, … csúcsú koronák esetében a (orientált) Hamilton-ciklusok száma

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

A koronák segítségével kimutatható, hogy egy mohó színező algoritmus bizonyos esetekben rosszul viselkedik – ha a korona csúcsai u 0 , v 0 , u 1 , v 1 stb. sorrendben kerülnek az algoritmus elé, akkor mohó színezést használnak. n szín, bár a színek optimális száma kettő. Ezt a konstrukciót Johnsonnak [6] tulajdonítják , magukat a koronákat pedig néha Johnson-gráfoknak nevezik J n [7] jelöléssel . Führer [8] koronákat használt egy olyan konstrukció részeként, amely bemutatja a színezési probléma közelítésének összetettségét.

Matushek [9] a koronákban mért távolságot használta olyan metrikus tér példájaként, amelyet nehéz beágyazni egy normált vektortérbe .

Amint azt Miklavic és Poroshnik [10] kimutatta , a koronák kis számú különböző típusú gráfban szerepelnek, amelyek távolságszabályos körkörös gráfok .

Agarwal és munkatársai [11] láthatósági grafikonként írják le a koronás sokszögeket . Példaként használják őket annak bemutatására, hogy a gráfok teljes kétrészes gráfok uniójaként való megjelenítése nem mindig memóriahatékony.

Egy kétrészes gráf egyik oldaláról a másikra orientált élekkel rendelkező 2n csúcsból álló korona szabványos példája egy n rendezési dimenziójú , részben rendezett halmaznak .

Jegyzetek

  1. ↑ Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: A diszkrét algoritmusokról szóló 8. ACM-SIAM szimpózium anyaga. - 1997. - S. 558-563 .
  2. ↑ D. Archdeacon, M. Debowsky, J. Dinitz, H. Gavlas. Ciklikus rendszereket a teljes kétrészes gráfban mínusz egytényezős // Discrete Mathematics . - 2004. - T. 284 , sz. 1-3 . - S. 37-43 . - doi : 10.1016/j.disc.2003.11.021 .
  3. ↑ Erdős Pál, Simonovits Miklós. A geometriai gráfok kromatikus számáról // 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 / szerk. Charles C. Cadogan. - Matematika Tanszék, University of the West Indies, 1981. - S. 169-173 .
  5. ↑ A vendégfeladatban a ciklus kezdeti pozíciója jelentős, így a Hamilton-ciklusok száma és a vendég probléma megoldása 2n -szeresen tér el .
  6. ↑ D.S. Johnson. Proc. 5. délkeleti konf. a kombinatorikáról, gráfelméletről és számítástechnikáról, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Grafikon színezések. - American Mathematical Society, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Furer. Proc. 36. IEEE Symp. A számítástechnika alapjai (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . - doi : 10.1109/SFCS.1995.492572 .
  9. ↑ Jiri Matousek. A véges metrikus terek normált terekbe való beágyazásához szükséges torzításról // Israel Journal of Mathematics. - 1996. - T. 93 , sz. 1 . - S. 333-344 . - doi : 10.1007/BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Distance-regular Circulants // European Journal of Combinatorics. - 2003. - T. 24 , sz. 7 . - S. 777-784 . - doi : 10.1016/S0195-6698(03)00117-3 .
  11. ↑ Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. Kompaktan ábrázolhatók a láthatósági grafikonok? // Diszkrét és számítási geometria. - 1994. - T. 12 , sz. 1 . - S. 347-365 . - doi : 10.1007/BF02574385 .

Linkek