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.

Ekvivalens meghatározások

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]

Példák

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 ugyanannyi csúcs van a bipartíció mindkét oldalán.

Ha az $m$ és $n$ számok relatív prímek, akkor az $m \times n$ -es bástyagráf (gráf, melynek csúcsai egy $m \times 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 $\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]

Egy specifikus példa

A $C_{n}^{s_{1},\ldots ,s_{k}}$ cirkuláns gráf, melynek ugrásai $s_{1},\ldots ,s_{k}$ úgy definiálható, mint az az $n$ csúcsú, $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: $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$ .

A $C_{n}^{s_{1},\ldots ,s_{k}}$ gráf pontosan akkor összefüggő, ha $\gcd(n,s_{1},\ldots ,s_{k})=1$ .
Ha $1\leq s_{1}<\cdots <s_{k}$ $1\leq 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},\ldots ,s_{k}})=na_{n}^{2}$ $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ , ahol $a_{n}$ $a_{n}$ kielégít egy $2^{s_{k}-1}$ $2^{s_{k}-1}$ fokú rekurrencia-relációt.
- Ezen belül $t(C_{n}^{1,2})=nF_{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.^[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ése

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 $z$ vel 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 \pm 1$ , $x \pm 2$ és $x \pm 7$ modulo 16, míg a $H$ -beli hat szomszéd az $x \pm 2$ , $x \pm 3$ és $x \pm 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é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ó.^[6]^[7]

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

Jegyzetek

1 2 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
1 2 3 4 5 Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, 34–36. o.
↑ Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., 1–22. o, MR 1468786.
1 2 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..
↑ http://mta.hu/koztestuleti_tagok?PersonId=11622
↑ Muzychuk, Mikhail (2004). "A Solution of the Isomorphism Problem for Circulant Graphs". Proc. London Math. Soc. 88: 1–41. doi:10.1112/s0024611503014412. MR 2018956.
↑ Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Recognition and verification of an isomorphism of circulant graphs in polynomial time". St. Petersburg Math. J. 15: 813–835. doi:10.1090/s1061-0022-04-00833-7. MR 2044629.

További információk

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

[ds1-1] 1 2 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.

[v04-2] 1 2 3 4 5 Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, 34–36. o.

[3] Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., 1–22. o, MR 1468786.

[s62-4] 1 2 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..

[5] ttp://mta.hu/koztestuleti_tagok?PersonId=11622

[muz04-6] Muzychuk, Mikhail (2004). "A Solution of the Isomorphism Problem for Circulant Graphs". Proc. London Math. Soc. 88: 1–41. doi:10.1112/s0024611503014412. MR 2018956.

[ep04-7] Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Recognition and verification of an isomorphism of circulant graphs in polynomial time". St. Petersburg Math. J. 15: 813–835. doi:10.1090/s1061-0022-04-00833-7. MR 2044629.

[1]

[2]

[3]

[4]

[5]

[6]

[7]