Grafic circular

În teoria grafurilor, un graf circulant este un graf nedirecționat care are un grup de simetrie ciclică care include o simetrie care duce orice vârf la orice alt vârf .

Definiții echivalente

Graficele circulante pot fi definite în mai multe moduri echivalente [1] :

Un automorfism de grup de graf conține un subgrup ciclic care acționează tranzitiv pe vârfurile grafului.
Graficul are o matrice de adiacență care este o circulară .
$n$ vârfurile graficului pot fi numerotate de la 0 la n − 1 în așa fel încât, dacă două vârfuri cu numere și sunt adiacente, atunci oricare două vârfuri cu numere și ( z − x + y ) mod n sunt de asemenea adiacente. $X$ $y$ $z$
Un grafic poate fi desenat (cu posibile intersecții ale muchiilor) în așa fel încât vârfurile sale să se afle la colțurile unui poligon obișnuit, iar orice rotație a poligonului în sine este o simetrie a desenului (obținem același desen).

Exemple

Orice ciclu este un grafic circulant, la fel ca orice coroană .

Graficele Paley de ordin (unde este un prim congruent cu 1 modulo 4) sunt grafice în care vârfurile sunt numere de la 0 la n - 1 și două vârfuri sunt adiacente dacă diferența numerelor corespunzătoare este un rest patratic modulo . Datorită faptului că prezența sau absența unei muchii depinde doar de diferența dintre numerele de vârfuri modulo , orice graf Paley este un graf circulant. $n$ $n$ $n$ $n$

Orice scară Möbius este un grafic circulant, la fel ca orice grafic complet . Un graf bipartit complet este circular dacă ambele părți au același număr de vârfuri.

Dacă două numere și sunt coprime , atunci graficul m × n turn (un grafic care are un vârf în fiecare celulă a unei table de șah m × n și o margine între oricare două celule dacă turnul se poate muta de la o celulă la alta într-o singură mișcare ) este un grafic circular. Aceasta este o consecință a faptului că simetriile sale conțin grupul ciclic {{{1}}} ca subgrup . Ca o generalizare a acestui caz, produsul direct al graficelor dintre orice grafice circulare cu și vârfuri are ca rezultat un grafic circular [1] . $m$ $n$ $m$ $n$

Multe dintre limitele inferioare cunoscute pentru numerele Ramsey provin din exemple de grafuri circulante având mici clicuri maxime și seturi independente maxime mici [2] .

Studiu de caz

Un graf circulant (sau , sau ) cu salturi este definit ca un graf cu noduri numerotate și fiecare nod este adiacent la 2 k noduri modulo . $C_{n}^{s_{1},\ldots, s_{k))$ $C_{n}(s_{1},\ldots, s_{k})$ $circ(n:s_{1},\ldots, s_{k})$ $s_{1},\ldots ,s_{k)$ $n$ $0,1,\ldots ,n-1$ $i$ $i\pm s_{1},\ldots,i\pm s_{k)$ $n$

Graficul este conectat dacă și numai dacă mcd . $C_{n}^{s_{1},\ldots, s_{k))$ $(n,s_{1},\ldots,s_{k})=1$

Dacă sunt numere întregi fixe, atunci numărul de arbori care se întind , unde satisface relația de recurență a ordinii . $1\leq s_{1}<\cdots <s_{k)$ $t(C_{n}^{s_{1},\ldots ,s_{k)))=na_{n}^{2)$ $un$ $2^{s_{k}-1}$
- În special, , unde este al
n -lea număr Fibonacci . $t(C_{n}^{1,2})=nF_{n}^{2}$ $F_{n}$

Circulare autocomplementare

Un graf auto-complementar este unul în care eliminarea muchiilor existente și adăugarea celor lipsă are ca rezultat un grafic izomorf cu cel original.

De exemplu, un grafic ciclic cu cinci vârfuri este auto-complementar și este, de asemenea, circular. Mai general, orice graf Paley este un graf circulant auto-complementar [3] . Horst Sachs a arătat că, dacă un număr are proprietatea că orice divizor prim este congruent cu 1 modulo 4, atunci există un graf circular auto-complementar cu vârfuri. El a emis ipoteza că această condiție este necesară, adică pentru alte valori nu există grafuri circulante autocomplementare [1] [3] . Conjectura a fost dovedită 40 de ani mai târziu de Wilfred [1] . $n$ $n$ $n$ $n$

Ipoteza lui Adams

Definim numerotarea circulară a unui grafic circulant ca marcarea vârfurilor graficului cu numere de la 0 la n - 1 în așa fel încât, dacă două vârfuri și sunt adiacente, atunci oricare două vârfuri cu numere și ( z - x + y ) mod n sunt de asemenea adiacente. În mod echivalent, o numerotare circulară este o numerotare a vârfurilor astfel încât matricea de adiacență a unui grafic este o matrice circulantă. $X$ $y$ $z$

Fie un întreg coprim c , și fie orice număr întreg. Apoi funcția liniară ax + b transformă numerotarea circulantă într-o altă numerotare circulantă. András Ádám a presupus că o mapare liniară este singura modalitate de a renumerota vârfurile unui grafic care păstrează proprietatea de circulație. Adică, dacă și sunt două grafice circulante izomorfe cu numerotări diferite, atunci există o transformare liniară care transformă numerotarea pentru în numerotarea pentru . Cu toate acestea, după cum sa dovedit, ipoteza lui Adam nu este corectă. Graficele cu 16 vârfuri în fiecare servesc drept contraexemplu ; vârful in este conectat la șase vecini x ± 1 , x ± 2 și x ± 7 (mod 16), în timp ce în șase vecini sunt x ± 2 , x ± 3 și x ± 5 (mod 16) . Aceste două grafice sunt izomorfe, dar izomorfismul lor nu poate fi obținut printr-o transformare liniară. [unu] $A$ $n$ $b$ $G$ $H$ $G$ $H$ $G$ $H$ $X$ $G$ $H$

Note

↑ 1 2 3 4 5 V. Wilfred. Teoria grafurilor și aplicațiile sale (Universitatea Anna, Chennai, 14–16 martie 2001) / editori: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. - Alpha Science, 2004. - S. 34-36 .
^ Small Ramsey Numbers Arhivat la 18 ianuarie 2012 la Wayback Machine , Stanisław P. Radziszowski, Electronic J. Combinatorics , dynamic survey updated 2009.
↑ 12 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . - S. 270-288 .

Link -uri

Weisstein, Eric W. Circulant Graph (engleză) pe site-ul web Wolfram MathWorld .