Cirkulær graf

I grafteori er en cirkulerende graf en urettet graf , der har en cyklisk symmetrigruppe , der inkluderer en symmetri, der tager et hvilket som helst toppunkt til et hvilket som helst andet toppunkt .

Tilsvarende definitioner

Cirkulerende grafer kan defineres på flere ækvivalente måder [1] :

En grafgruppeautomorfi indeholder en cyklisk undergruppe , der virker transitivt på grafens hjørner.
Grafen har en tilstødende matrix , der er et cirkulationsmiddel .
$n$ grafens hjørnepunkter kan nummereres fra 0 til n − 1 på en sådan måde, at hvis to hjørner med tal og er nabostillede, så er to vilkårlige knudepunkter med tal og ( z − x + y ) mod n også tilstødende. $x$ $y$ $z$
En graf kan tegnes (med mulige skæringer af kanter) på en sådan måde, at dens toppunkter ligger i hjørnerne af en regulær polygon, og enhver rotation af polygonen ind i sig selv er en symmetri af tegningen (vi får den samme tegning).

Eksempler

Enhver cyklus er en cirkulerende graf, ligesom enhver krone er det .

Paley-grafer af orden (hvor er et primtal kongruent med 1 modulo 4) er grafer, hvor knudepunkterne er tal fra 0 til n − 1 og to knudepunkter støder op til hinanden, hvis forskellen mellem de tilsvarende tal er en kvadratisk rest modulo . På grund af det faktum, at tilstedeværelsen eller fraværet af en kant kun afhænger af forskellen i modulo vertex-tal , er enhver Paley-graf en cirkulerende graf. $n$ $n$ $n$ $n$

Enhver Möbius-stige er en cirkulerende graf, ligesom enhver komplet graf er det . En komplet todelt graf er cirkulerende, hvis begge dele har det samme antal hjørner.

Hvis to tal og er coprime , så m × n tårngrafen (en graf, der har et toppunkt i hver celle på et m × n skakbræt og en kant mellem to celler, hvis tårnet kan flytte fra en celle til en anden i et træk ) er en cirkulerende graf. Dette er en konsekvens af, at dens symmetrier indeholder den cykliske gruppe {{{1}}} som en undergruppe . Som en generalisering af dette tilfælde resulterer det direkte produkt af grafer mellem alle cirkulerende grafer med og toppunkter i en cirkulerende graf [1] . $m$ $n$ $m$ $n$

Mange af de kendte nedre grænser for Ramsey-tal kommer fra eksempler på cirkulerende grafer med små maksimale kliker og små maksimale uafhængige sæt [2] .

Casestudie

En cirkulerende graf (eller , eller ) med spring er defineret som en graf med noder nummererede, og hver node støder op til 2 k noder 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$ $jeg$ ${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k))$ $n$

Grafen er forbundet hvis og kun hvis gcd . $C_{n}^{s_{1},\ldots ,s_{k))$ $(n,s_{1},\ldots,s_{k})=1$

Hvis faste heltal, så opfylder antallet af spændende træer , hvor rækkefølgegentagelsesrelationen . ${\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}$
- Især , hvor er det
n . Fibonacci- tal . $t(C_{n}^{1,2})=nF_{n}^{2}$ $F_{n}$

Selvkomplementære cirkulanter

En selvkomplementær graf er en, hvor fjernelse af eksisterende kanter og tilføjelse af manglende kan resultere i en graf, der er isomorf i forhold til den oprindelige.

For eksempel er en cyklisk graf med fem hjørner selvkomplementær og er også cirkulerende. Mere generelt er enhver Paley-graf en selvkomplementær cirkulationsgraf [3] . Horst Sachs viste, at hvis et tal har den egenskab, at enhver primtal divisor er kongruent med 1 modulo 4, så eksisterer der en selvkomplementær cirkulerende graf med toppunkter. Han antog, at denne betingelse er nødvendig, det vil sige, for andre værdier eksisterer der ikke selvkomplementære cirkulerende grafer [1] [3] . Formodningen blev bevist 40 år senere af Wilfred [1] . $n$ $n$ $n$ $n$

Adams' hypotese

Vi definerer cirkulationsnummereringen af en cirkulerende graf som markering af grafens hjørner med tal fra 0 til n − 1 på en sådan måde, at hvis to spidser og er tilstødende, så er to vilkårlige spidser med tal og ( z − x + y ) mod n er også tilstødende. Tilsvarende er en cirkulationsnummerering en toppunktsnummerering, således at den tilstødende matrix af en graf er en cirkulerende matrix. $x$ $y$ $z$

Lad være et heltal coprime c , og lad være et hvilket som helst heltal. Så transformerer den lineære funktion ax + b cirkulantnummereringen til en anden cirkulantnummerering. András Ádám formodede, at en lineær kortlægning er den eneste måde at omnummerere hjørnerne af en graf, der bevarer cirkulationsegenskaben. Det vil sige, at hvis og er to isomorfe cirkulerende grafer med forskellige nummereringer, så er der en lineær transformation, der transformerer nummereringen for til nummereringen for . Men som det viste sig, er Adams hypotese ikke korrekt. Graferne med 16 hjørner i hver tjener som modeksempel ; vertex in er forbundet med seks naboer x ± 1 , x ± 2 og x ± 7 (mod 16), mens i seks naboer er x ± 2 , x ± 3 og x ± 5 (mod 16). Disse to grafer er isomorfe, men deres isomorfi kan ikke opnås ved en lineær transformation. [en] $-en$ $n$ $b$ $G$ $H$ $G$ $H$ $G$ $H$ $x$ $G$ $H$

Noter

↑ 1 2 3 4 5 V. Wilfred. Graph Theory and its Applications (Anna University, Chennai, 14.-16. marts 2001) / redaktører: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. - Alpha Science, 2004. - S. 34-36 .
↑ Small Ramsey Numbers Arkiveret 18. januar 2012 på Wayback Machine , Stanisław P. Radziszowski, Electronic J. Combinatorics , dynamisk undersøgelse opdateret 2009.
↑ 12 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . - S. 270-288 .