Cirkuláns gráf

matematikai fogalom a gráfelméletben
A hasonló nevű négyzetes mátrixhoz lásd: Ciklikus mátrix

A matematika, azon belül a gráfelmélet területén egy cirkuláns gráf (circulant graph) olyan irányítatlan gráf, ami bármely csúcsot bármely csúcsba átvivő ciklikus csoport-szimmetriákkal rendelkezik. Néha ciklikus gráfnak (cyclic graph)[1] is nevezik, de ennek a kifejezésnek néhány más jelentése is van.

A cirkuláns gráfok egy példája, a 13 rendű Paley-gráf.

Ekvivalens meghatározásokSzerkesztés

A cirkuláns gráfok több, egymással ekvivalens módon definiálhatók:[2]

PéldákSzerkesztés

Minden körgráf, továbbá minden 2 modulo 4 csúccsal rendelkező koronagráf cirkuláns.

Az n rendű Paley-gráf (ahol n olyan prímszám, ami kongruens 1 modulo 4) olyan gráf, amiben a csúcsok 0-tól n − 1-ig vannak számozva és két csúcs akkor szomszédos, ha különbségük kvadratikus maradék modulo n. Mivel egy él jelenléte kizárólag a két csúcs számai közötti modulo n különbségen múlik, bármely Paley-gráf egyben cirkuláns gráf is.

Minden Möbius-létra cirkuláns gráf, ahogy minden teljes gráf is az. A teljes páros gráfok közül azok cirkulánsak, melyeknél ugyanannyú csúcs van a bipartíció mindkét oldalán.

Ha az m és n számok relatív prímek, akkor az m × n-es bástyagráf (gráf, melynek csúcsai egy m × n-es sakktábla mezőinek felelnek meg, az élek pedig a bástyával közöttük elvégezhető legális lépéseket) cirkuláns gráf. Ennek oka, hogy szimmetriái között részcsoportként szerepel a Cmn   Cm×Cn ciklikus csoport. Általánosabban nézve bármely m, illetve n csúcsú cirkuláns gráf tenzorszorzata maga is cirkuláns.[2]

A Ramsey-számok több ismert alsó korlátja olyan cirkuláns gráfokból származik, melyek kis maximális elemszámú klikkkel és kis maximális elemszámú független csúcshalmazzal rendelkeznek.[1]

Egy specifikus példaSzerkesztés

A   cirkuláns gráf, melynek ugrásai   úgy definiálható, mint az az   csúcsú,   számokkal címkézett gráf, melynek minden i csúcsa pontosan ezzel a 2k csúccsal szomszédos:  .

  • A   gráf pontosan akkor összefüggő, ha  .
  • Ha   rögzített egész számok, akkor a feszítőfák száma,  , ahol   kielégít egy   fokú rekurrencia-relációt.
    • Ezen belül  , ahol   az n-edik Fibonacci-szám.

Önkomplementer cirkulánsokSzerkesztés

Egy önkomplementer gráf olyan gráf, melyben az éleket nem-élekre cserélve és vice versa az eredetivel izomorf gráfot kapunk. Például az öt csúcsú körgráf önkomplementer, egyben cirkuláns. Általánosabban, minden Paley-gráf önkomplementer cirkuláns gráf.[4] Horst Sachs megmutatta, hogy ha egy n számra igaz, hogy n minden prímtényezője kongruens 1 modulo 4, akkor létezik n csúcsú önkomplementer cirkuláns gráf. Sejtése szerint ez a feltétel nem csak elégséges, de szükséges is: egyetlen más n értékre sem létezik önkomplementer cirkuláns gráf.[2][4] A sejtést mintegy 40 évvel később Vilfred igazolta.[2]

Ádám András sejtéseSzerkesztés

Egy cirkuláns gráf cirkuláns számozása legyen a gráf csúcsainak olyan, a 0 és n − 1 közötti egész számokkal való címkézése, hogy ha az x-szel és y-nal címkézett két csúcs szomszédos, akkor bármely zvel címkézett csúcs és a (zx + y) mod n-nel címkézett csúcs is szomszédos. Ezzel ekvivalens, hogy a cirkuláns számozás a csúcsok olyan számozása, melyben a gráf szomszédsági mátrixa egy ciklikus mátrix.

Legyen a az n-nel relatív prím egész szám, b pedig tetszőleges egész szám. Ekkor az a lineáris függvény, ami az x-et ax + b-be viszi át, a cirkuláns számozást egy másik cirkuláns számozássá transzformálja. Ádám András[5] sejtése szerint ezek a lineáris hozzárendelések az egyedüli módjai a cirkuláns gráfok a cirkuláns tulajdonságot megtartó átszámozásának: más szóval, ha G és H különböző számozással bíró, izomorf cirkuláns gráfok, akkor létezik G számozását H számozásába átvivő lineáris függvény. Ádám sejtését azóta cáfolták. Az ellenpélda G és H gráfjai mindössze 16 csúcsúak; bármely, G-beli x csúcs a következő hat szomszédjához kapcsolódik: x ± 1, x ± 2 és x ± 7 modulo 16, míg a H-beli hat szomszéd az x ± 2, x ± 3 és x ± 5 modulo 16. Ez a két gráf izomorf, de az izomorfizmus nem valósítható meg egy lineáris leképezéssel.[2]

Algoritmikus kérdésekSzerkesztés

A cirkuláns gráfok polinom idejű algoritmussal felismerhetők, és a cirkuláns gráfokra az izomorfizmus-probléma is polinom időben megoldható.[6][7]

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Circulant 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. a b Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
  2. a b c d e Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G. & Wilson, Robin J., Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36, <https://books.google.com/books?id=wG-08Lv8E-0C&pg=PA34>.
  3. Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), vol. 497, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Dordrecht: Kluwer Acad. Publ., pp. 1–22, <https://books.google.com/books?id=-tIaXdII8egC&pg=PA1>.
  4. a b Sachs, Horst (1962). „Über selbstkomplementäre Graphen”. Publicationes Mathematicae Debrecen 9, 270–288. o.  .
  5. http://mta.hu/koztestuleti_tagok?PersonId=11622
  6. (2004) „A Solution of the Isomorphism Problem for Circulant Graphs”. Proc. London Math. Soc. 88, 1–41. o. DOI:10.1112/s0024611503014412.  
  7. (2004) „Recognition and verification of an isomorphism of circulant graphs in polynomial time”. St. Petersburg Math. J. 15, 813–835. o. DOI:10.1090/s1061-0022-04-00833-7.  

További információkSzerkesztés