Cirkuláns gráf

A hasonló nevű négyzetes mátrixhoz lásd: Ciklikus mátrix

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

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) is nevezik, de ennek a kifejezésnek néhány más jelentése is van.

Ekvivalens meghatározások

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

• 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 Sablon:Mvar csúcs megszámozható 0-tól Sablon:Math-ig úgy, hogy ha van két Sablon:Mvar-szel Sablon:Math-nel jelölt csúcs, ami szomszédos, akkor bármely két Sablon:Mvar és Sablon:Math 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.

Példák

Minden körgráf, továbbá minden Sablon:Nowrap csúccsal rendelkező koronagráf cirkuláns.

Az Sablon:Mvar rendű Paley-gráf (ahol Sablon:Mvar olyan prímszám, ami kongruens Sablon:Nowrap) olyan gráf, amiben a csúcsok 0-tól Sablon:Math-ig vannak számozva és két csúcs akkor szomszédos, ha különbségük kvadratikus maradék modulo Sablon:Mvar. Mivel egy él jelenléte kizárólag a két csúcs számai közötti modulo Sablon:Mvar 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 Sablon:Mvar és Sablon:Mvar számok relatív prímek, akkor az Sablon:Math-es bástyagráf (gráf, melynek csúcsai egy Sablon:Math-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 $\simeq$ C_m×C_n ciklikus csoport. Általánosabban nézve bármely Sablon:Mvar, illetve Sablon:Mvar csúcsú cirkuláns gráf tenzorszorzata maga is cirkuláns.

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.

Egy specifikus példa

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

• A $C_n^{s_1,\dots ,s_k}$ gráf pontosan akkor összefüggő, ha $\gcd (n,s_1,\dots ,s_k)=1$.
• Ha $1\le s_1<\cdots <s_k$ rögzített egész számok, akkor a feszítőfák száma, $t(C_n^{s_1,\dots ,s_k})=n{a}_n^2$, ahol $a_n$ kielégít egy $2^{s_k-1}$ fokú rekurrencia-relációt.
  • Ezen belül $t(C_n^{1,2})=n{F}_n^2$, ahol $F_n$ az n-edik Fibonacci-szám.

Önkomplementer cirkulánsok

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. Horst Sachs megmutatta, hogy ha egy Sablon:Mvar számra igaz, hogy Sablon:Mvar minden prímtényezője kongruens Sablon:Nowrap, akkor létezik Sablon:Mvar 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 Sablon:Mvar értékre sem létezik önkomplementer cirkuláns gráf. A sejtést mintegy 40 évvel később Vilfred igazolta.

Ádám András sejtése

Egy cirkuláns gráf cirkuláns számozása legyen a gráf csúcsainak olyan, a 0 és Sablon:Math közötti egész számokkal való címkézése, hogy ha az Sablon:Mvar-szel és Sablon:Mvar-nal címkézett két csúcs szomszédos, akkor bármely Sablon:Mvarvel címkézett csúcs és a Sablon:Math-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 Sablon:Mvar az Sablon:Mvar-nel relatív prím egész szám, Sablon:Mvar pedig tetszőleges egész szám. Ekkor az a lineáris függvény, ami az Sablon:Mvar-et Sablon:Math-be viszi át, a cirkuláns számozást egy másik cirkuláns számozássá transzformálja. Ádám András 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 Sablon:Mvar és Sablon:Mvar különböző számozással bíró, izomorf cirkuláns gráfok, akkor létezik Sablon:Mvar számozását Sablon:Mvar számozásába átvivő lineáris függvény. Ádám sejtését azóta cáfolták. Az ellenpélda Sablon:Mvar és Sablon:Mvar gráfjai mindössze 16 csúcsúak; bármely, Sablon:Mvar-beli Sablon:Mvar csúcs a következő hat szomszédjához kapcsolódik: Sablon:Math, Sablon:Math és Sablon:Math modulo 16, míg a Sablon:Mvar-beli hat szomszéd az Sablon:Math, Sablon:Math és Sablon:Math modulo 16. Ez a két gráf izomorf, de az izomorfizmus nem valósítható meg egy lineáris leképezéssel.

Algoritmikus kérdések

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ó.

Fordítás

• Sablon:Fordítás

További információk

• Sablon:Mathworld