Grafic fără triunghiuri

În teoria grafurilor, un graf fără triunghi este un graf nedirecționat în care trei vârfuri nu formează un triunghi de muchii. Graficele fără triunghi pot fi, de asemenea, definite ca grafice cu număr de clic ≤ 2, grafice cu circumferință ≥ 4, grafice fără 3-cicluri generate sau ca grafice independente local .

După teorema lui Turan , un graf fără triunghi cu n -vertice cu numărul maxim de muchii este un graf complet bipartit în care numărul de vârfuri din fiecare parte a graficului este cât mai apropiat posibil.

Un grafic cu 2n vârfuri și fără triunghiuri trebuie să aibă mai puține muchii. $n^{2}+1$

Problema găsirii triunghiurilor

Problema găsirii triunghiurilor este problema de a determina dacă un grafic conține triunghiuri sau nu. Dacă graficul conține un triunghi, algoritmului i se cere adesea să scoată trei vârfuri care formează un triunghi.

Este posibil să verificăm dacă un grafic cu m muchii are triunghiuri în timp O( m 1.41 ). [1] O altă abordare este găsirea urmei matricei A 3 , unde A este matricea de adiacență a graficului. Urma este zero dacă și numai dacă nu există triunghiuri în grafic. Pentru graficele dense, acest algoritm simplu de multiplicare a matricei este mai eficient deoarece reduce complexitatea timpului la O( n 2,373 ), unde n este numărul de vârfuri.

După cum arată Imrich, Klavžar și Mulder ( Imrich, Klavžar, Mulder 1999 ), recunoașterea grafică fără triunghi este echivalentă ca complexitate cu recunoașterea grafică mediană . Cu toate acestea, în prezent, cei mai buni algoritmi de grafic mediană folosesc recunoașterea triunghiului ca subrutină, și nu invers.

Complexitatea arborelui de decizie sau complexitatea interogării a problemei, unde interogările către oracolul care amintește matricele de adiacență ale graficului, este egală cu Θ( n 2 ). Cu toate acestea, pentru algoritmii cuantici, cea mai bună limită inferioară este Ω( n ), dar cel mai cunoscut algoritm are o estimare a O( n 1,29 ) ( Belovs 2011 ).

Numărul independenței și teoria Ramsey

O mulțime independentă de vârfuri într-un grafic fără triunghi cu n - vârfuri este ușor de găsit – fie că există un vârf cu mai mult decât vecini (caz în care vecinii formează o mulțime independentă), fie toate vârfurile au mai puțin decât vecini (în care în cazul în care orice cea mai mare mulțime independentă trebuie să aibă cel puțin vârfuri) [2] . Această limită poate fi ușor îmbunătățită - în orice grafic fără triunghiuri există o mulțime independentă cu vârfuri, iar în unele grafice fără triunghiuri, orice mulțime independentă are vârfuri. [3] O modalitate de a crea grafice fără tegon în care toate mulțimile independente sunt mici este procesul fără triunghi [ 4] , care creează grafice fără triunghi maxim prin adăugarea secvențială de muchii alese aleatoriu, evitând crearea de triunghiuri. Cu un grad ridicat de probabilitate, procesul formează grafice cu număr de independență . De asemenea, se pot găsi grafice obișnuite cu aceleași proprietăți. [5] ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ $\Omega ({\sqrt {n\log n))}$ $O({\sqrt {n\log n)})$ $O({\sqrt {n\log n)})$

Aceste rezultate pot fi, de asemenea, înțelese ca stabilirea limitelor asimptotice ale numerelor Ramsey R(3, t ) în forma - dacă marginile unui grafic complet cu vârfuri sunt colorate în roșu și albastru, atunci fie graficul roșu conține un triunghi, fie nu există triunghiuri în el și atunci trebuie să existe o mulțime independentă de dimensiune t corespunzătoare unei clicuri de această dimensiune în graficul albastru. $\Theta ({\tfrac {t^{2)} {\log t)))$ $\Omega ({\tfrac {t^{2)} {\log t))}$

Colorarea graficelor fără triunghiuri

Multe cercetări asupra graficelor fără triunghi s-au concentrat pe colorarea graficelor . Orice graf bipartit (adică orice graf bicolor) nu are triunghiuri, iar teorema lui Grötzsch afirmă că orice graf planar fără triunghi poate fi tricolorat. [6] Cu toate acestea, graficele neplanare fără triunghiuri pot necesita mai mult de trei culori.

Mycielski ( 1955 ) a definit o construcție, numită acum Mycielskian , care formează un nou graf fără triunghi dintr-un alt graf fără triunghi. Dacă un graf are numărul cromatic k , Mychelskianul său are numărul cromatic k + 1, astfel încât această construcție poate fi folosită pentru a arăta că un număr arbitrar mare de culori poate fi necesar pentru a colora un graf neplanar fără triunghi. În special, graficul Grötzsch , un grafic cu 11 vârfuri format prin repetarea construcției lui Mycielski, este un grafic fără triunghi care nu poate fi colorat cu mai puțin de patru culori și este cel mai mic grafic cu aceste proprietăți. [7] Gimbel și Thomassen ( Gimbel, Thomassen & 2000 ) și ( Nilli 2000 ) au arătat că numărul de culori necesare pentru a colora orice grafic m -line fără triunghi este

O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)

și există grafice fără triunghi având numere cromatice proporționale cu această limită.

Există și câteva rezultate referitoare la legătura dintre colorare și gradul minim de grafice fără triunghiuri. Andrásfai și Erdős ( Andrásfai, Erdős, Sós 1974 ) au demonstrat că orice graf fără triunghi n -vertex în care fiecare vârf are mai mult de un vecin trebuie să fie bipartit. Acesta este cel mai bun rezultat posibil de acest tip, deoarece ciclul de 5 necesită trei culori, dar are exact vecini pentru fiecare vârf. Încurajați de acest rezultat, Erdős și Simonovits ( Erdős, Simonovits 1973 ) au presupus că orice graf fără triunghi cu n vârfuri, în care fiecare vârf are cel puțin vecini, poate fi colorat doar cu trei culori. Cu toate acestea, Häggkvist ( 1981 ) a respins această presupunere prezentând un contraexemplu în care fiecare vârf al grafului Grötsch este înlocuit cu un set independent de mărime special aleasă. Jin ( Jin 1995 ) a arătat că orice graf fără triunghi n -vertex în care fiecare vârf are mai mult de un vecin poate fi tricolorat. Acesta este cel mai bun rezultat de acest tip, deoarece graficul Haggquist necesită patru culori și are exact vecini pentru fiecare vârf. În cele din urmă, Brandt și Thomassé ( Brandt, Thomassé 2006 ) au demonstrat că orice graf fără triunghi n -vertex în care orice vârf are mai mult de 4 vecini poate fi colorat cu 4 culori. Rezultate suplimentare de acest fel sunt imposibile deoarece Hajnal [8] a găsit exemple de grafice fără triunghi cu număr cromatic arbitrar mare și grad minim pentru orice . $2n/5$ $2n/5$ $n/3$ $10n/29$ $10n/29$ $n/3$ $(1/3-\epsilon )n$ $\epsilon > 0$

Link -uri

↑ Alon, Yuster, Zwick, 1994 .
↑ Boppana, Halldórsson, 1992 , pornind de la ideea algoritmului de aproximare anterior al lui Avi Wigderson ., p. 184.
↑ Kim, 1995 .
↑ Erdős, Suen, Winkler, 1995 ; Bohman, 2008
↑ Alon, Ben-Shimon, Krivelevich, 2008 .
↑ Grötzsch, 1959 ; ( Thomassen 1994 )).
↑ Chvatal, 1974 .
↑ vezi Erdős, Simonovits, 1973 .

Surse

N. Alon, S. Ben-Shimon, M. Krivelevich. O notă despre graficele Ramsey obișnuite. — 2008.
N. Alon, R. Yuster, U. Zwick. Proceedings of the 2nd European Symposium on Algorithms , Utrecht, Țările de Jos. - 1994. - S. 354-364 .
B. Andrásfai, P. Erdős, VT Sos. Despre legătura dintre numărul cromatic, clica maximă și gradul minim al unui grafic // Matematică discretă . - 1974. - T. 8 , nr. 3 . — S. 205–218 . - doi : 10.1016/0012-365X(74)90133-2 .
T. Bohman. Procesul fără triunghi . — 2008.
Ravi Boppana, Magnús M. Halldorsson. Aproximarea seturilor independente maxime prin excluderea subgrafelor // BIT. - 1992. - T. 32 , nr. 2 . — S. 180–196 . - doi : 10.1007/BF01994876 .
S. Brandt, S. Thomasse. Graficele dense fără triunghiuri sunt de patru colorate: o soluție la problema Erdős-Simonovits. - 2006. Arhivat la 4 februarie 2012.
N. Chiba, T. Nisizeki. Algoritmi de arboricitate și listare a subgrafelor // SIAM Journal on Computing . - 1985. - T. 14 , nr. 1 . — S. 210–223 . - doi : 10.1137/0214017 .
Vasek Chvatal. Grafice și combinatorie (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Note de curs la matematică).
P. Erdős, M. Simonovits. Despre o problemă de valență în teoria grafurilor extreme // Matematică discretă. - 1973. - V. 5 , nr. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X .
P. Erdős, S. Suen, P. Winkler. Pe dimensiunea unui grafic maxim aleatoriu // Structuri aleatorii și algoritmi. - 1995. - T. 6 , nr. 2–3 . — S. 309–318 . - doi : 10.1002/rsa.3240060217 .
John Gimbel, Carsten Thomassen. Colorarea graficelor fără triunghiuri cu dimensiune fixă // Matematică discretă. - 2000. - T. 219 , nr. 1-3 . — S. 275–277 . - doi : 10.1016/S0012-365X(00)00087-X .
H. Grotzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. - 1959. - T. 8 . — S. 109–120 .
R. Haggkvist. Teoria grafurilor (Cambridge, 1981). - 1981. - S. 89–99 .
Wilfried Imrich, Sandi Klavžar, Henry Martyn. Grafice mediane și grafice fără triunghi // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , nr. 1 . — p. 111–118 . - doi : 10.1137/S0895480197323494 .
A. Itai, M. Rodeh. Găsirea unui circuit minim într-un grafic // SIAM Journal on Computing . - 1978. - V. 7 , nr. 4 . — S. 413–423 . - doi : 10.1137/0207033 .
G. Jin. Grafice cu patru cromatice fără triunghi // Matematică discretă. - 1995. - T. 145 , nr. 1-3 . — S. 151–170 . - doi : 10.1016/0012-365X(94)00063-O .
JH Kim. Numărul Ramsey are un ordin de mărime // Structuri aleatorii și algoritmi. - 1995. - T. 7 , nr. 3 . — S. 173–207 . $R(3,t)$ ${\tfrac {t^{2}}{\log t}}$
Frederic Magniez, Miklos Santha, Mario Szegedy. Algoritmi cuantici pentru problema triunghiului. — 2003.
J. Mycielski. Sur le coloriage des graphes // Colloq. Matematică.. - 1955. - T. 3 . — S. 161–162 .
A. Nilli. Grafice fără triunghiuri cu numere cromatice mari // Matematică discretă. - 2000. - T. 211 , nr. 1–3 . — S. 261–262 . - doi : 10.1016/S0012-365X(99)00109-0 .
JB Shearer. Notă despre numărul de independență al graficelor fără triunghi // Matematică discretă. - 1983. - T. 46 , nr. 1 . — p. 83–87 . - doi : 10.1016/0012-365X(83)90273-X .
C. Thomassen. Teorema lui Grötzsch a 3 culori // Journal of Combinatorial Theory, Seria B . - 1994. - T. 62 , nr. 2 . — S. 268–279 . - doi : 10.1006/jctb.1994.1069 .
Aleksandrs Belovs. Programe de acoperire pentru funcții cu certificate 1 de dimensiune constantă. — 2011.