Circumferința (teoria graficelor)

Circumferința în teoria grafurilor este lungimea celui mai mic ciclu conținut într-un graf dat [1] . Dacă graficul nu conține cicluri (adică este un grafic aciclic), circumferința lui este, prin definiție, egală cu infinitul [2] . De exemplu, un 4 cicluri (pătrat) are circumferința 4. O rețea pătrată are și circumferința 4, iar o grilă triunghiulară are circumferința 3. Un grafic cu circumferința patru sau mai mult nu are triunghiuri .

Celule

Graficele cubice (toate nodurile au gradul trei) cu o circumferință cât mai mică posibil sunt cunoscute ca -celule (sau ca (3, )-celule). Graficul Petersen este singurul cu 5 celule (cel mai mic grafic cubic cu circumferința 5), graficul Heawood este singurul cu 6 celule, graficul McGee este singurul cu 7 celule și graficul Tutt-Coxeter este singurul 8- celula [3] . Pot exista mai multe (graf-)celule pentru o anumită circumferință. De exemplu, există trei celule neizomorfe cu 10 celule, fiecare cu 70 de vârfuri - Balaban cu 10 celule , graficul Harris și graficul Harris-Wong . $g$ $g$ $g$

Graficul Petersen are circumferința 5
Graficul Heawood are circumferința 6
Earl McGee are o circumferință de 7
Graficul Tutta-Coxeter ( celule 8 ale lui Tatta ) are circumferința 8

Circumferința și colorarea graficului

Pentru orice număr întreg pozitiv , există un grafic cu circumferința și numărul cromatic . De exemplu, graficul Grötzsch este un grafic fără triunghi și are numărul cromatic 4, iar repetarea construcției Myzelskiană folosită pentru a crea graficul Grötzsch de multe ori produce grafice fără triunghi cu un număr cromatic arbitrar mare. Pal Erdős a demonstrat această teoremă folosind metoda probabilistică [4] . $k$ $G$ $g(G)\geq k$ $\chi (G)\geq k$

Plan de probă . Numim cicluri de lungime cel mult scurte și seturi cu sau mai multe vârfuri mari. Pentru a demonstra teorema, este suficient să găsim un grafic fără cicluri scurte și seturi mari independente de vârfuri. Apoi, seturile de culori din colorare nu vor fi mari și, ca urmare, culorile vor fi necesare pentru colorare. $k$ $|G|/k$ $G$ $k$

Pentru a găsi un astfel de grafic, vom fixa probabilitatea de alegere egală cu . Pentru v mic , apare doar un număr mic de cicluri scurte. Dacă acum eliminăm un vârf din fiecare astfel de ciclu, graficul rezultat nu va avea cicluri scurte, iar numărul său de independență nu va fi mai mic decât cel al graficului [1] . $p$ $n^{\epsilon -1}$ $\epsilon$ $G$ $H$ $G$

Concepte înrudite

Circumferința impară și circumferința pară a unui grafic sunt lungimile celui mai mic ciclu impar și, respectiv, ciclul par.

Circumferința unui grafic este lungimea celui mai lung ciclu, nu cel mai scurt.

Gândirea la lungimea celui mai mic ciclu non-trivial poate fi văzută ca o generalizare a 1-sistolei sau a sistolei mai mari în geometria sistolice .

Note

↑ 1 2 Reinhard Distel. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică, 2002.
↑ Circumferință -- Wolfram MathWorld.
↑ Andries E. Brouwer. cuști. Supliment electronic la cartea Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
↑ Paul Erdős. Teoria graficelor și probabilitatea // Canadian Journal of Mathematics. - 1959. - T. 11 . - S. 34-38 . - doi : 10.4153/CJM-1959-003-9 .