Kruhový graf

V teorii grafů je oběžný graf neorientovaný graf , který má cyklickou skupinu symetrie , která zahrnuje symetrii, která přenese jakýkoli vrchol do jakéhokoli jiného vrcholu .

Ekvivalentní definice

Kruhové grafy lze definovat několika ekvivalentními způsoby [1] :

Automorfismus grup grafu obsahuje cyklickou podgrupu , která působí tranzitivně na vrcholy grafu.
Graf má matici sousednosti , která je oběžná .
$n$ vrcholy grafu lze očíslovat od 0 do n − 1 tak, že pokud dva vrcholy s čísly a sousedí, pak libovolné dva vrcholy s čísly a ( z − x + y ) mod n sousedí také. $X$ $y$ $z$
Graf lze nakreslit (s možnými průsečíky hran) tak, že jeho vrcholy leží v rozích pravidelného mnohoúhelníku a jakékoli otočení mnohoúhelníku do sebe je symetrií kresby (dostaneme stejnou kresbu).

Příklady

Jakýkoli cyklus je obíhajícím grafem, stejně jako jakákoli koruna .

Paleyovy grafy řádu (kde je prvočíslo shodné s 1 modulo 4) jsou grafy, ve kterých jsou vrcholy čísla od 0 do n − 1 a dva vrcholy sousedí, pokud je rozdíl odpovídajících čísel kvadratický zbytek modulo . Vzhledem k tomu, že přítomnost nebo nepřítomnost hrany závisí pouze na rozdílu v číslech modulo vertexů , je každý Paleyův graf obíhajícím grafem. $n$ $n$ $n$ $n$

Jakýkoli Möbiův žebřík je obíhajícím grafem, stejně jako jakýkoli úplný graf . Kompletní bipartitní graf je oběžný, pokud mají obě části stejný počet vrcholů.

Jestliže dvě čísla a jsou coprime , pak m × n věžový graf (graf, který má vrchol v každé buňce šachovnice m × n a hranu mezi libovolnými dvěma buňkami, pokud se věž může přesunout z jedné buňky do druhé jedním tahem ) je cirkulující graf. Je to důsledek toho, že jeho symetrie obsahují jako podgrupu cyklickou grupu {{{1}}} . Zobecněním tohoto případu je, že přímý součin grafů mezi libovolnými obíhajícími grafy s vrcholy a vede k oběžnému grafu [1] . $m$ $n$ $m$ $n$

Mnoho ze známých dolních hranic pro Ramseyho čísla pochází z příkladů cirkulujících grafů s malými maximálními klikami a malými maximálními nezávislými množinami [2] .

Případová studie

Cirkulující graf (nebo , nebo ) se skoky je definován jako graf s očíslovanými uzly a každý uzel sousedí s 2 k uzlům modulo . $C_{n}^{s_{1},\ldots ,s_{k))$ $C_{n}(s_{1},\ldots ,s_{k})$ $circ(n:s_{1},\ldots ,s_{k})$ ${\displaystyle s_{1},\ldots ,s_{k))$ $n$ $0,1,\ldots ,n-1$ $i$ ${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k))$ $n$

Graf je připojen tehdy a jen tehdy, když gcd . $C_{n}^{s_{1},\ldots ,s_{k))$ $(n,s_{1},\ldots ,s_{k})=1$

Pokud jsou pevná celá čísla, pak počet spanning tree , kde splňuje relace opakování objednávky . ${\displaystyle 1\leq s_{1}<\cdots <s_{k))$ ${\displaystyle t(C_{n}^{s_{1},\ldots ,s_{k)))=na_{n}^{2))$ $a_n$ $2^{s_{k}-1}$
- Konkrétně , kde je
n-té Fibonacciho číslo . $t(C_{n}^{1,2})=nF_{n}^{2}$ $F_{n}$

Samokomplementární oběhové látky

Samokomplementární graf je graf, ve kterém odstranění existujících hran a přidání chybějících vede ke grafu isomorfnímu k původnímu.

Například cyklický graf s pěti vrcholy se samodoplňuje a je také oběhový. Obecněji platí, že jakýkoli Paleyův graf je samokomplementárním cirkulujícím grafem [3] . Horst Sachs ukázal, že má-li číslo tu vlastnost, že jakýkoli prvočísel je shodný s 1 modulo 4, pak existuje samokomplementární cirkulující graf s vrcholy. Předpokládal, že tato podmínka je nezbytná, to znamená, že pro jiné hodnoty neexistují samokomplementární cirkulační grafy [1] [3] . Dohad byl prokázán o 40 let později Wilfredem [1] . $n$ $n$ $n$ $n$

Adamsova hypotéza

Oběžné číslování oběžného grafu definujeme jako označení vrcholů grafu čísly od 0 do n − 1 tak, že pokud dva vrcholy a sousedí, pak libovolné dva vrcholy s čísly a ( z − x + y ) mod n jsou také sousedící. Ekvivalentně je oběžné číslování vertexové číslování, takže matice sousednosti grafu je oběžná matice. $X$ $y$ $z$

Nechť je celé číslo coprime c , a nechť je libovolné celé číslo. Poté lineární funkce ax + b transformuje číslování oběžníků na jiné číslování oběžníků. András Ádám se domníval, že lineární zobrazení je jediný způsob, jak přečíslovat vrcholy grafu, který zachovává vlastnost oběhovosti. To znamená, že pokud a jsou dva izomorfní oběžné grafy s různým číslováním, pak existuje lineární transformace, která transformuje číslování pro na číslování pro . Jak se však ukázalo, Adamova hypotéza není správná. Jako protipříklad slouží grafy se 16 vrcholy; vertex in je spojen se šesti sousedy x ± 1 , x ± 2 a x ± 7 (mod 16), zatímco v šesti sousedech jsou x ± 2 , x ± 3 a x ± 5 (mod 16) . Tyto dva grafy jsou izomorfní, ale jejich izomorfismus nelze získat lineární transformací. [jeden] $A$ $n$ $b$ $G$ $H$ $G$ $H$ $G$ $H$ $X$ $G$ $H$

Poznámky

↑ 1 2 3 4 5 V. Wilfred. Teorie grafů a její aplikace (Anna University, Chennai, 14.–16. března 2001) / editoři: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. - Alpha Science, 2004. - S. 34-36 .
↑ Malá Ramseyova čísla archivována 18. ledna 2012 na Wayback Machine , Stanisław P. Radziszowski, Electronic J. Combinatorics , dynamický průzkum aktualizován v roce 2009.
↑ 12 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . - S. 270-288 .

Odkazy

Weisstein, Eric W. Circulant Graph (anglicky) na webových stránkách Wolfram MathWorld .