Cirkulär graf

I grafteorin är en cirkulerande graf en oriktad graf som har en cyklisk symmetrigrupp som inkluderar en symmetri som tar vilken vertex som helst till vilken annan vertex som helst .

Motsvarande definitioner

Cirkulerande grafer kan definieras på flera likvärdiga sätt [1] :

En grafgruppautomorfism innehåller en cyklisk undergrupp som verkar transitivt på grafens hörn.
Grafen har en närliggande matris som är en cirkulant .
$n$ grafens hörn kan numreras från 0 till n − 1 på ett sådant sätt att om två hörn med siffror och är intilliggande, så är två höjdpunkter med siffror och ( z − x + y ) mod n också intilliggande. $x$ $y$ $z$
En graf kan ritas (med möjliga skärningspunkter av kanter) på ett sådant sätt att dess hörn ligger i hörnen av en vanlig polygon, och varje rotation av polygonen in i sig själv är en symmetri av ritningen (vi får samma ritning).

Exempel

Varje cykel är en cirkulerande graf, precis som vilken krona som helst .

Paley-grafer av ordning (där är ett primtal som är kongruent med 1 modulo 4) är grafer där hörnen är tal från 0 till n − 1 och två hörn ligger intill om skillnaden mellan motsvarande tal är en kvadratisk rest modulo . På grund av det faktum att närvaron eller frånvaron av en kant endast beror på skillnaden i modulo vertexnummer , är alla Paley-grafer en cirkulerande graf. $n$ $n$ $n$ $n$

Vilken Möbius-stege som helst är en cirkulerande graf, precis som vilken komplett graf som helst . En komplett tvådelad graf är cirkulerande om båda delarna har samma antal hörn.

Om två siffror och är coprime , då m × n torngrafen (en graf som har en vertex i varje cell på ett m × n schackbräde och en kant mellan två valfria celler om tornet kan flytta från en cell till en annan i ett drag ) är en cirkulerande graf. Detta är en konsekvens av det faktum att dess symmetrier innehåller den cykliska gruppen {{{1}}} som en undergrupp . Som en generalisering av detta fall resulterar den direkta produkten av grafer mellan alla cirkulerande grafer med och hörn i en cirkulerande graf [1] . $m$ $n$ $m$ $n$

Många av de kända nedre gränserna för Ramsey-tal kommer från exempel på cirkulerande grafer med små maximala klick och små maximala oberoende uppsättningar [2] .

Fallstudie

En cirkulerande graf (eller , eller ) med hopp definieras som en graf med noder numrerade och varje nod ligger intill 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$ $i$ ${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k))$ $n$

Grafen är kopplad om och endast om gcd . $C_{n}^{s_{1},\ldots ,s_{k))$ $(n,s_{1},\ldots,s_{k})=1$

Om fasta heltal, då antalet spännande träd , där uppfyller ordningsupprepningsrelationen . ${\displaystyle 1\leq s_{1}<\cdots <s_{k))$ ${\displaystyle t(C_{n}^{s_{1},\ldots ,s_{k)))=na_{n}^{2))$ $en$ $2^{s_{k}-1}$
- I synnerhet, , var är det
n :te Fibonacci- talet . ${\displaystyle t(C_{n}^{1,2})=nF_{n}^{2))$ $F_{n}$

Självkompletterande cirkulanter

En självkomplementär graf är en där borttagning av befintliga kanter och tillägg av saknade resulterar i en graf som är isomorf till den ursprungliga.

Till exempel är en cyklisk graf med fem hörn självkomplementär och är också cirkulerande. Mer allmänt är vilken Paley-graf som helst en självkompletterande cirkulationsgraf [3] . Horst Sachs visade att om ett tal har egenskapen att någon primtalsdelare är kongruent med 1 modulo 4, så finns det en självkomplementär cirkulerande graf med hörn. Han antog att detta villkor är nödvändigt, det vill säga för andra värden existerar inte självkomplementära cirkulerande grafer [1] [3] . Gissningen bevisades 40 år senare av Wilfred [1] . $n$ $n$ $n$ $n$

Adams hypotes

Vi definierar cirkulationsnumreringen av en cirkulationsgraf som att markera grafens hörn med siffror från 0 till n − 1 på ett sådant sätt att om två hörn och är intill varandra, så är två punkter med siffror och ( z − x + y ) mod n ligger också intill. På motsvarande sätt är en cirkulationsnumrering en vertexnumrering så att närliggande matris i en graf är en cirkulerande matris. $x$ $y$ $z$

Låt vara ett heltal coprime c , och låt vara vilket heltal som helst. Sedan omvandlar den linjära funktionen ax + b cirkulationsnumreringen till en annan cirkulantnumrering. András Ádám antog att en linjär mappning är det enda sättet att numrera om hörnen på en graf som bevarar cirkulansegenskapen. Det vill säga om och är två isomorfa cirkulerande grafer med olika numrering, så finns det en linjär transformation som omvandlar numreringen för till numreringen för . Men som det visade sig är Adams hypotes inte korrekt. Graferna med 16 hörn i varje fungerar som ett motexempel; vertex in är ansluten till sex grannar x ± 1 , x ± 2 och x ± 7 (mod 16), medan i sex grannar är x ± 2 , x ± 3 och x ± 5 (mod 16). Dessa två grafer är isomorfa, men deras isomorfism kan inte erhållas genom en linjär transformation. [ett] $a$ $n$ $b$ $G$ $H$ $G$ $H$ $G$ $H$ $x$ $G$ $H$

Anteckningar

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

Länkar

Weisstein, Eric W. Circulant Graph (engelska) på Wolfram MathWorld- webbplatsen .