Koronagráf (gráfelmélet)

Koronagráf
6, 8, illetve 10 csúcsú koronagráfok
Csúcsok száma	2 n
Élek száma	n (n - 1)
Sugár	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{egyébként}}\end{array}}\right.}$
Átmérő	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{egyébként}}\end{array}}\right.}$
Derékbőség	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\6&n=3\\4&{\text{egyébként}}\end{array}}\right.}$
Kromatikus szám	${\displaystyle \left\{{\begin{array}{ll}1&n=1\\2&{\text{egyébként}}\end{array}}\right.}$
Egyéb	Távolságtranzitív
Jelölés	${\displaystyle S_{n}^{0}}$

A matematika, azon belül a gráfelmélet területén egy koronagráf 2n csúccsal rendelkező irányítatlan gráf, melynek csúcsai az {u₁, u₂, ..., u_n}, illetve a {v₁, v₂, ..., v_n} halmazba tartoznak, élek pedig u_i és v_j között húzódnak, amennyiben i ≠ j.

A koronagráf felfogható olyan teljes páros gráfként, melyből egy teljes párosítás éleit eltávolították, egy teljes gráf páros dupla fedéseként, a K_n × K₂ tenzorszorzatként, a K_n és K₂ Descartes-szorzatának komplementereként vagy a H_n,1 páros Kneser-gráfként, melynek csúcsait az n elemű halmaz 1-, illetve (n − 1) elemű részhalmazai alkotnak, két részhalmazt jelképező csúcsok között pedig akkor húzódik él, ha az egyik részhalmaz tartalmazza a másikat.

Példák

A 6 csúcsú koronagráf kört alkot, a 8 csúcsú izomorf a kockagráffal. A Schläfli-féle dupla hatos a térben 12 egyenesből és 30 pontból álló konfiguráció, melynek tizenkét egyenesének metszéspontjai egy tizenkét csúcsból álló koronagráf mintázatát adják ki.

Tulajdonságok

A 10 csúcsú koronagráf páros dupla fedése

A koronagráf éleinek száma az n(n − 1) téglalapszám. Akromatikus száma n: egy teljes színezés előállítható az egyes {u_i, v_i} párokat választva egy-egy színosztálynak.^[1] A koronagráfok szimmetrikusak és távolságtranzitívak. (Archdeacon et al. 2004) leírja a koronagráf éleinek egyenlő hosszúságú körökbe particionálását.

A 2n csúcsú koronagráf beágyazható a négydimenziós euklideszi térbe úgy, hogy minden éle egységnyi hosszúságú szakasz legyen. Ezzel a beágyazással azonban egymással nem szomszédos csúcsok is egységnyi távolságra kerülhetnek. Olyan beágyazáshoz, ahol az élek egységnyi távolságra vannak, a nem-élek pedig nem, legalább n − 2 dimenzióra van szükség. Ez a példa is mutatja, hogy nagyon különböző számú dimenzióra lehet szükség egy gráf egységtávolsággráfként és szigorú egységtávolsággráfként való ábrázolásához.^[2]

A koronagráf éleinek lefedéséhez szükséges teljes páros részgráfok minimális száma (páros dimenziója, avagy minimális páros dupla fedésének mérete)

${\displaystyle \sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\},}$

ami a központi binomiális együttható inverz függvénye.^[3]

A 2n csúcsú koronagráf komplementer gráfja a K₂ ${\displaystyle \square }$ K_n Descartes-szorzattal, illetve a 2 × n-es bástyagráffal egyezik meg.

Alkalmazásai

Az etikett hagyományos szabálya szerint az ebédlőasztalnál a vendégeket úgy ültetik le, hogy a férfiak és nők váltakozva üljenek, de házaspárok ne kerüljenek egymás mellé. Ha egy fogadás résztvevői éppen n házaspárból állnak, akkor a követelményeknek megfelelő elrendezések épp egy koronagráf Hamilton-köreiként írhatók le. Az ilyen elrendezések leszámlálását, vagy ami ezzel csaknem ekvivalens,^[4] a koronagráf Hamilton-köreinek megszámolását nevezik a kombinatorikában ültetési problémának (ménage problem); a 6, 8, 10, ... csúcsból álló koronagráfokra az (irányított) Hamilton-körök száma:

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (A094047 sorozat az OEIS-ben)

A koronagráfok jó példát szolgáltatnak arra, hogy a mohó színezési algoritmusok milyen rosszul is viselkedhetnek: ha a koronagráf csúcsait az algoritmus u₀, v₀, u₁, v₁ stb. sorrendben kapja meg, akkor a mohó színezés n színt használ el, miközben a színek optimális száma mindössze kettő. Ezt a konstrukciót (Johnson 1974)-nak tulajdonítják, ezért néha a koronagráfokat Johnson gráfjainak (Johnson’s graphs) is nevezik, J_n jelöléssel.^[5] (Fürer 1995) a koronagráfokat színezési problémák approximációjának nehézségét megmutató konstrukciójának részeként használta fel.

(Matoušek 1996) a koronagráfokbeli távolságokat olyan metrikus térre hozza példának, ami nehezen beágyazható egy normált térbe.

Ahogy (Miklavič & Potočnik 2003) megmutatja, a koronagráfok a távolságreguláris cirkuláns gráfok kevés különböző típusának egyikét alkotják.

(Agarwal et al. 1994) olyan sokszögeket írnak le, melyek láthatósági gráfjaiként koronagráfok szerepelnek; ezzel a példával mutatva be, hogy a láthatósági gráfok teljes páros gráfok uniójaként való ábrázolása nem minden esetben helytakarékos.

Egy 2n csúcsú koronagráf éleinek a bipartíció egyik felétől a másik felé irányításával tankönyvi példáját adja egy n részbenrendezési dimenziójú (szélességű) részbenrendezett halmaznak.

Jegyzetek

1. Chaudhary & Vishwanathan (2001).
2. Erdős & Simonovits (1980).
3. de Caen, Gregory & Pullman (1981).
4. Az ültetési problémában a kör kezdőpontját is számításba veszik, ezért az ültetési probléma megoldása és a Hamilton-körök száma egy 2n-es szorzótényezőben eltérnek.
5. Kubale (2004).

Fordítás

• Ez a szócikk részben vagy egészben a Crown graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Agarwal, Pankaj K.; Alon, Noga & Aronov, Boris et al. (1994), "Can visibility graphs be represented compactly?", Discrete and Computational Geometry 12 (1): 347–365, DOI 10.1007/BF02574385.
• Archdeacon, D.; Debowsky, M. & Dinitz, J. et al. (2004), "Cycle systems in the complete bipartite graph minus a one-factor", Discrete Mathematics 284 (1–3): 37–43, DOI 10.1016/j.disc.2003.11.021.
• Chaudhary, Amitabh & Vishwanathan, Sundar (2001), "Approximation algorithms for the achromatic number", Journal of Algorithms 41 (2): 404–416, DOI 10.1006/jagm.2001.1192.
• de Caen, Dominique; Gregory, David A. & Pullman, Norman J. (1981), "The Boolean rank of zero-one matrices", in Cadogan, Charles C., Proc. 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173.
• Erdős, Paul & Simonovits, Miklós (1980), "On the chromatic number of geometric graphs", Ars Combinatoria 9: 229–246, <https://www.renyi.hu/~p_erdos/1980-25.pdf>.
• Fürer, Martin (1995), "Improved hardness results for approximating the chromatic number", Proc. 36th IEEE Symp. Foundations of Computer Science (FOCS '95), pp. 414–421, ISBN 0-8186-7183-1, DOI 10.1109/SFCS.1995.492572.
• Johnson, D. S. (1974), "Worst-case behavior of graph coloring algorithms", Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae, Winnipeg, pp. 513–527
• Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4
• Matoušek, Jiří (1996), "On the distortion required for embedding finite metric spaces into normed spaces", Israel Journal of Mathematics 93 (1): 333–344, DOI 10.1007/BF02761110.
• Miklavič, Štefko & Potočnik, Primož (2003), "Distance-regular circulants", European Journal of Combinatorics 24 (7): 777–784, DOI 10.1016/S0195-6698(03)00117-3.

További információk

• Weisstein, Eric W.: Crown Graph (angol nyelven). Wolfram MathWorld