Cirkuláns gráf

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 több, egymással ekvivalens módon definiálhatók:^[2]

• A gráf automorfizmus-csoportja tartalmaz olyan ciklikus részcsoportot, ami a gráf csúcsain tranzitívan hat. Más szavakkal, a gráfnak van olyan gráfautomorfizmusa, ami a csúcsainak ciklikus permutációja.
• A gráf egy szomszédsági mátrixa ciklikus mátrix.
• A gráf n csúcs megszámozható 0-tól n − 1-ig úgy, hogy ha van két x-szel (x +d) mod n-nel jelölt csúcs, ami szomszédos, akkor bármely két z és (z +d) mod n csúcs is szomszédos.
• A gráf lerajzolható (a metsző élek kizárása nélkül) oly módon, hogy csúcsai egy szabályos sokszög csúcspontjaiban találhatók, és a sokszög minden forgatási szimmetriája egyben a lerajzolás szimmetriája is.
• A gráf ciklikus csoport Cayley-gráfja.^[3]

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 C_mn ${\displaystyle \simeq }$ C_m×C_n 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]

A ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$ cirkuláns gráf, melynek ugrásai ${\displaystyle s_{1},\ldots ,s_{k}}$ úgy definiálható, mint az az ${\displaystyle n}$ csúcsú, ${\displaystyle 0,1,\ldots ,n-1}$ számokkal címkézett gráf, melynek minden i csúcsa pontosan ezzel a 2k csúccsal szomszédos: ${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k}\mod n}$.

• A ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$ gráf pontosan akkor összefüggő, ha ${\displaystyle \gcd(n,s_{1},\ldots ,s_{k})=1}$.
• Ha ${\displaystyle 1\leq s_{1}<\cdots <s_{k}}$ rögzített egész számok, akkor a feszítőfák száma, ${\displaystyle t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}}$, ahol ${\displaystyle a_{n}}$ kielégít egy ${\displaystyle 2^{s_{k}-1}}$ fokú rekurrencia-relációt.
  • Ezen belül ${\displaystyle t(C_{n}^{1,2})=nF_{n}^{2}}$, ahol ${\displaystyle F_{n}}$ az n-edik Fibonacci-szám.

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]

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 (z − x + 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]

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]

• 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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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