Graf bez trojúhelníků

V teorii grafů je graf bez trojúhelníku neorientovaný graf, ve kterém žádné tři vrcholy netvoří trojúhelník hran. Grafy bez trojúhelníků lze také definovat jako grafy s číslem kliky ≤ 2, grafy s obvodem ≥ 4, grafy bez vygenerovaných 3-cyklů nebo jako lokálně nezávislé grafy.

Podle Turanova teorému je n -vrcholový trojúhelníkový graf s maximálním počtem hran úplným bipartitním grafem , ve kterém jsou počty vrcholů v každé části grafu co nejblíže.

Graf s 2n vrcholy a bez trojúhelníků musí mít méně hran. $n^{2}+1$

Problém hledání trojúhelníků

Problém hledání trojúhelníků je problém určit, zda graf obsahuje trojúhelníky nebo ne. Pokud graf obsahuje trojúhelník, je algoritmus často požádán, aby vydal tři vrcholy, které tvoří trojúhelník.

Je možné zkontrolovat, zda má graf s m hranami trojúhelníky v čase O( m 1,41 ). [1] Dalším přístupem je nalezení stopy matice A 3 , kde A je matice sousednosti grafu. Stopa je nulová právě tehdy, když v grafu nejsou žádné trojúhelníky. Pro husté grafy je tento jednoduchý algoritmus násobení matic efektivnější , protože snižuje časovou složitost na O( n 2,373 ), kde n je počet vrcholů.

Jak ukazují Imrich, Klavžar a Mulder ( Imrich, Klavžar, Mulder 1999 ), rozpoznávání grafů bez trojúhelníků je co do složitosti ekvivalentní rozpoznávání mediánových grafů . V současnosti však nejlepší algoritmy mediánových grafů používají rozpoznávání trojúhelníků jako podprogram a ne naopak.

Složitost rozhodovacího stromu nebo složitost dotazu problému, kde dotazy na orákulum, které si pamatuje matice sousednosti grafu, se rovná Θ( n 2 ). Pro kvantové algoritmy je však nejlepší dolní mez Ω( n ), ale nejznámější algoritmus má odhad O( n 1,29 ) ( Belovs 2011 ).

Číslo nezávislosti a Ramseyho teorie

Nezávislou množinu vrcholů v n -vrcholovém grafu bez trojúhelníků lze snadno najít – buď existuje vrchol s více než sousedy (v takovém případě tvoří sousedé nezávislou množinu), nebo mají všechny vrcholy méně než sousedů (ve kterém v případě, že každá největší nezávislá množina musí mít alespoň vrcholy) [2] . Tato vazba může být mírně vylepšena - v každém grafu bez trojúhelníků je nezávislá množina s vrcholy a v některých grafech bez trojúhelníků má každá nezávislá množina vrcholy. [3] Jedním ze způsobů, jak vytvořit grafy bez tegonů, ve kterých jsou všechny nezávislé množiny malé, je proces bez trojúhelníků [ 4] , který vytváří maximální grafy bez trojúhelníků postupným přidáváním náhodně vybraných hran, čímž se vyhneme vytváření trojúhelníků. S vysokou mírou pravděpodobnosti proces tvoří grafy s číslem nezávislosti . Lze také najít pravidelné grafy se stejnými vlastnostmi. [5] ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ $\Omega ({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$

Tyto výsledky lze chápat i jako stanovení asymptotických hranic Ramseyových čísel R(3, t ) ve tvaru - pokud jsou okraje kompletního grafu s vrcholy zbarveny červeně a modře, pak buď červený graf obsahuje trojúhelník, popř. nejsou v něm žádné trojúhelníky a pak musí existovat nezávislá množina velikosti t odpovídající klikě této velikosti v modrém grafu. $\Theta ({\tfrac {t^{2)){\log t)))$ $\Omega ({\tfrac {t^{2)){\log t)))$

Barevné grafy bez trojúhelníků

Mnoho výzkumů v oblasti grafů bez trojúhelníků se zaměřilo na barvení grafů . Žádný bipartitní graf (to znamená jakýkoli dvoubarevný graf) nemá trojúhelníky a Grötzschova věta říká, že jakýkoli rovinný graf bez trojúhelníků může být tříbarevný. [6] Nerovinné grafy bez trojúhelníků však mohou vyžadovat více než tři barvy.

Mycielski ( 1955 ) definoval konstrukci, nyní nazývanou Mycielskian , která tvoří nový graf bez trojúhelníků z jiného grafu bez trojúhelníků. Pokud má graf chromatické číslo k , jeho Mychelskian má chromatické číslo k + 1, takže tuto konstrukci lze použít k ukázce, že k obarvení nerovinného grafu bez trojúhelníků může být zapotřebí libovolně velký počet barev. Zejména Grötzschův graf, 11-vrcholový graf vytvořený opakováním Mycielského konstrukce, je graf bez trojúhelníků, který nelze obarvit méně než čtyřmi barvami, a je nejmenším grafem s těmito vlastnostmi. [7] Gimbel a Thomassen ( Gimbel, Thomassen & 2000 ) a ( Nilli 2000 ) ukázali, že počet barev potřebných k vybarvení jakéhokoli m -čárového grafu bez trojúhelníků je

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

a existují grafy bez trojúhelníků s chromatickými čísly úměrnými této hranici.

Existují také některé výsledky týkající se souvislosti mezi zbarvením a minimálním stupněm grafů bez trojúhelníků. Andrásfai a Erdős ( Andrásfai, Erdős, Sós 1974 ) dokázali, že každý n -vrcholový graf bez trojúhelníku, ve kterém má každý vrchol více než jednoho souseda, musí být bipartitní. Toto je nejlepší možný výsledek tohoto typu, protože 5-cyklus vyžaduje tři barvy, ale má přesně sousedy pro každý vrchol. Povzbuzeni tímto výsledkem Erdős a Simonovits ( Erdős, Simonovits 1973 ) usoudili, že každý graf bez trojúhelníků s n vrcholy, ve kterém má každý vrchol alespoň sousedy, může být obarven pouze třemi barvami. Häggkvist ( 1981 ) však tuto domněnku vyvrátil předložením protipříkladu, ve kterém je každý vrchol Grötschova grafu nahrazen nezávislou sadou speciálně zvolené velikosti. Jin ( Jin 1995 ) ukázal, že jakýkoli n -vertexový graf bez trojúhelníku, ve kterém má každý vrchol více než jednoho souseda, může být 3barevný. Toto je nejlepší výsledek tohoto typu, protože Haggquistův graf vyžaduje čtyři barvy a má přesně sousedy pro každý vrchol. Nakonec Brandt a Thomassé ( Brandt, Thomassé 2006 ) dokázali, že jakýkoli n -vertexový graf bez trojúhelníků, ve kterém má kterýkoli vrchol více než 4 sousedy, lze obarvit 4 barvami. Dodatečné výsledky tohoto druhu jsou nemožné, protože Hajnal [8] našel příklady grafů bez trojúhelníků s libovolně velkým chromatickým číslem a minimálním stupněm pro libovolný . $2n/5$ $2n/5$ $n/3$ $10n/29$ $10n/29$ $n/3$ $(1/3-\epsilon )n$ $\epsilon > 0$

Odkazy

↑ Alon, Yuster, Zwick, 1994 .
↑ Boppana, Halldórsson, 1992 , vycházející z myšlenky dřívějšího aproximačního algoritmu Aviho Wigdersona ., str. 184.
↑ Kim, 1995 .
↑ Erdős, Suen, Winkler, 1995 ; Bohman, 2008
↑ Alon, Ben-Shimon, Krivelevich, 2008 .
↑ Grötzsch, 1959 ; ( Thomassen 1994 )).
↑ Chvátal, 1974 .
↑ viz Erdős, Simonovits, 1973 .

Prameny

N. Alon, S. Ben-Shimon, M. Krivelevich. Poznámka k pravidelným Ramseyho grafům. — 2008.
N. Alon, R. Yuster, U. Zwick. Sborník příspěvků z 2. evropského sympozia o algoritmech , Utrecht, Nizozemsko. - 1994. - S. 354-364 .
B. Andrásfai, P. Erdős, VT Sos. O spojení mezi chromatickým číslem, maximální klikou a minimálním stupněm grafu // Diskrétní matematika . - 1974. - T. 8 , no. 3 . — S. 205–218 . - doi : 10.1016/0012-365X(74)90133-2 .
T. Bohman. Proces bez trojúhelníků . — 2008.
Ravi Boppana, Magnús M. Halldorsson. Aproximace maximálních nezávislých sad vyloučením podgrafů // BIT. - 1992. - T. 32 , no. 2 . — S. 180–196 . - doi : 10.1007/BF01994876 .
S. Brandt, S. Thomasse. Husté grafy bez trojúhelníků jsou čtyřbarevné: řešení problému Erdős-Simonovits. - 2006. Archivováno 4. února 2012.
N. Chiba, T. Nishizeki. Arboricita a algoritmy výpisu podgrafů // SIAM Journal on Computing . - 1985. - T. 14 , no. 1 . — S. 210–223 . - doi : 10.1137/0214017 .
Vašek Chvátal. Grafy a kombinatorika (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Poznámky z matematiky).
P. Erdős, M. Simonovits. K valenčnímu problému v extrémní teorii grafů // Diskrétní matematika. - 1973. - V. 5 , čís. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X .
P. Erdős, S. Suen, P. Winkler. O velikosti náhodného maximálního grafu // Náhodné struktury a algoritmy. - 1995. - T. 6 , no. 2–3 . — S. 309–318 . - doi : 10.1002/rsa.3240060217 .
John Gimbel, Carsten Thomassen. Vybarvování grafů bez trojúhelníků s pevnou velikostí // Diskrétní matematika. - 2000. - T. 219 , čís. 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. Teorie grafů (Cambridge, 1981). - 1981. - S. 89–99 .
Wilfried Imrich, Sandi Klavžar, Henry Martyn. Mediánové grafy a grafy bez trojúhelníků // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , no. 1 . — s. 111–118 . - doi : 10.1137/S0895480197323494 .
A. Itai, M. Rodeh. Nalezení minimálního obvodu v grafu // SIAM Journal on Computing . - 1978. - V. 7 , čís. 4 . — S. 413–423 . - doi : 10.1137/0207033 .
G. Jin. Čtyřchromatické grafy bez trojúhelníků // Diskrétní matematika. - 1995. - T. 145 , no. 1-3 . — S. 151–170 . - doi : 10.1016/0012-365X(94)00063-O .
JH Kim. Ramseyho číslo má řádovou velikost // Náhodné struktury a algoritmy. - 1995. - T. 7 , no. 3 . — S. 173–207 . $R(3,t)$ ${\tfrac {t^{2}}{\log t}}$
Frederic Magniez, Miklos Santha, Mario Szegedy. Kvantové algoritmy pro problém trojúhelníku. — 2003.
J. Mycielski. Sur le coloriage des graphes // Colloq. Matematika.. - 1955. - T. 3 . — S. 161–162 .
A. Nilli. Grafy bez trojúhelníků s velkými chromatickými čísly // Diskrétní matematika. - 2000. - T. 211 , čís. 1–3 . — S. 261–262 . - doi : 10.1016/S0012-365X(99)00109-0 .
JB Shearer. Poznámka k počtu nezávislosti grafů bez trojúhelníků // Diskrétní matematika. - 1983. - T. 46 , no. 1 . — s. 83–87 . - doi : 10.1016/0012-365X(83)90273-X .
C. Thomassen. Grötzschova věta o 3 barvách // Journal of Combinatorial Theory, Series B . - 1994. - T. 62 , no. 2 . — S. 268–279 . - doi : 10.1006/jctb.1994.1069 .
Aleksandrs Belovs. Span programy pro funkce s 1 certifikáty konstantní velikosti. — 2011.