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) 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 csúcs megszámozható 0-tól -ig úgy, hogy ha van két -szel -nel jelölt csúcs, ami szomszédos, akkor bármely két és 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 csúccsal rendelkező koronagráf cirkuláns.
Az rendű Paley-gráf (ahol olyan prímszám, ami kongruens ) olyan gráf, amiben a csúcsok 0-tól -ig vannak számozva és két csúcs akkor szomszédos, ha különbségük kvadratikus maradék modulo . Mivel egy él jelenléte kizárólag a két csúcs számai közötti modulo 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 ugyanannyi csúcs van a bipartíció mindkét oldalán.
Ha az és számok relatív prímek, akkor az -es bástyagráf (gráf, melynek csúcsai egy -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 , illetve 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.Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
Egy specifikus példa 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á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 számra igaz, hogy minden prímtényezője kongruens , akkor létezik 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 é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 közötti egész számokkal való címkézése, hogy ha az -szel és -nal címkézett két csúcs szomszédos, akkor bármely vel címkézett csúcs és a -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 az -nel relatív prím egész szám, pedig tetszőleges egész szám. Ekkor az a lineáris függvény, ami az -et -be viszi át, a cirkuláns számozást egy másik cirkuláns számozássá transzformálja. Ádám Andráshttp://mta.hu/koztestuleti_tagok?PersonId=11622 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 és különböző számozással bíró, izomorf cirkuláns gráfok, akkor létezik számozását számozásába átvivő lineáris függvény. Ádám sejtését azóta cáfolták. Az ellenpélda és gráfjai mindössze 16 csúcsúak; bármely, -beli csúcs a következő hat szomszédjához kapcsolódik: , és modulo 16, míg a -beli hat szomszéd az , és 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
Jegyzetek
További információk
Kategória:Gráfcsaládok Kategória:Reguláris gráfok