Graf bez trojúhelníků - Triangle-free graph

V matematický oblast teorie grafů, a graf bez trojúhelníků je neorientovaný graf, ve kterém žádné tři vrcholy netvoří a trojúhelník hran. Grafy bez trojúhelníků lze ekvivalentně definovat jako grafy s číslo kliky ≤ 2, grafy s obvod ≥ 4, grafy s č indukovaný 3-cyklus nebo místně nezávislý grafy.

Grafy bez trojúhelníků s největším počtem hran pro jejich vrcholy jsou vyvážené kompletní bipartitní grafy. Mnoho grafů bez trojúhelníků není bipartitních, například jakýkoli cyklický graf C_n pro lichén > 3.

Podle Turánova věta, n-vertexový trojúhelníkový graf s maximálním počtem hran je a kompletní bipartitní graf ve kterém jsou počty vrcholů na každé straně bipartice co nejrovnější.

Problém s vyhledáním trojúhelníku

Problém s nalezením trojúhelníku je problém určení, zda je graf bez trojúhelníků nebo ne. Když graf obsahuje trojúhelník, jsou často vyžadovány algoritmy pro výstup tří vrcholů, které v grafu tvoří trojúhelník.

Je možné vyzkoušet, zda graf s m hran je bez trojúhelníků v čase O (m^1.41).^[1] Dalším přístupem je najít stopa z A³, kde A je matice sousedství grafu. Trasa je nulová, právě když je graf bez trojúhelníků. Pro husté grafy, je efektivnější použít tento jednoduchý algoritmus, na který se spoléhá násobení matic, protože dostává časovou složitost na O (n^2.373), kde n je počet vrcholů.

Tak jako Imrich, Klavžar & Mulder (1999) ukázáno, rozpoznání grafu bez trojúhelníků je ve složitosti ekvivalentní střední graf uznání; současné nejlepší algoritmy pro střední rozpoznávání grafů však používají detekci trojúhelníků spíše jako podprogram než naopak.

The složitost rozhodovacího stromu nebo složitost dotazu problému, kde se dotazy týkají věštce, která ukládá matici sousedství grafu, je Θ (n²). Nicméně pro kvantové algoritmy, nejznámější dolní mez je Ω (n), ale nejznámější algoritmus je O (n^5/4).^[2]

Číslo nezávislosti a Ramseyova teorie

An nezávislá sada √n vrcholy v n-vertexový trojúhelníkový graf je snadné najít: buď existuje vrchol s více než √n sousedé (v takovém případě jsou sousedé nezávislou množinou) nebo všechny vrcholy mají méně než √n sousedé (v takovém případě vůbec maximální nezávislá množina musí mít alespoň √n vrcholy).^[3] Tuto vazbu lze mírně utáhnout: v každém grafu bez trojúhelníků existuje nezávislá sada ${displaystyle Omega ({sqrt {nlog n}})}$ vrcholy a v některých grafech bez trojúhelníků má každá nezávislá množina ${displaystyle O ({sqrt {nlog n}})}$ vrcholy.^[4] Jedním ze způsobů generování grafů bez trojúhelníků, ve kterých jsou všechny nezávislé sady malé, je proces bez trojúhelníků^[5] ve kterém jeden generuje maximální graf bez trojúhelníku opakovaným přidáváním náhodně vybraných hran, které nedokončí trojúhelník. Tento proces s vysokou pravděpodobností vytvoří graf s číslem nezávislosti ${displaystyle O ({sqrt {nlog n}})}$ . Je také možné najít pravidelné grafy se stejnými vlastnostmi.^[6]

Tyto výsledky lze také interpretovat tak, že dávají asymptotické hranice Ramseyova čísla R (3,t) formuláře ${displaystyle Theta ({frac {t ^ {2}} {log t}})}$ : pokud jsou okraje celého grafu zapnuty ${displaystyle Omega ({frac {t ^ {2}} {log t}})}$ vrcholy jsou zbarveny červeně a modře, pak buď červený graf obsahuje trojúhelník, nebo pokud je bez trojúhelníků, pak musí mít nezávislou množinu velikostí t odpovídá klikě stejné velikosti v modrém grafu.

Barvení grafů bez trojúhelníků

The Grötzschův graf je graf bez trojúhelníků, který nelze obarvit méně než čtyřmi barvami

Hodně se zaměřilo na výzkum grafů bez trojúhelníků zbarvení grafu. Každý bipartitní graf (tj. každý 2barevný graf) je bez trojúhelníků a Grötzschova věta uvádí, že každý trojúhelník bez rovinný graf může být 3-barevný.^[7] Neplanární grafy bez trojúhelníků však mohou vyžadovat mnohem více než tři barvy.

Mycielski (1955) definoval konstrukci, nyní nazývanou Mycielskian, pro vytvoření nového grafu bez trojúhelníků z jiného grafu bez trojúhelníků. Pokud má graf chromatické číslo k, jeho Mycielskian má chromatické číslo k + 1, takže tuto konstrukci lze použít k ukázání, že k zbarvení neplanárních grafů bez trojúhelníků může být zapotřebí libovolně velké množství barev. Zejména Grötzschův graf, 11-vertexový graf vytvořený opakovanou aplikací konstrukce Mycielski, je graf bez trojúhelníků, který nelze obarvit méně než čtyřmi barvami a je nejmenší graf s touto vlastností.^[8] Gimbel & Thomassen (2000) a Nilli (2000) ukázal, že počet barev potřebných k vybarvení jakékoli mgraf bez hranatého trojúhelníku je

{displaystyle Oleft ({frac {m ^ {1/3}} {(log m) ^ {2/3}}} včas)}

a že existují grafy bez trojúhelníků, které mají chromatická čísla úměrná této hranici.

Bylo také několik výsledků týkajících se zbarvení na minimální stupeň v grafech bez trojúhelníků. Andrásfai, Erdős & Sós (1974) dokázal, že jakýkoli n-vertexový trojúhelníkový graf, ve kterém má každý vrchol více než 2n/ 5 sousedů 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ě 2n/ 5 sousedů na vrchol. Motivován tímto výsledkem, Erdős & Simonovits (1973) domníval se, že vůbec n-vertexový trojúhelníkový graf, ve kterém má každý vrchol alespoň n/ 3 sousedé mohou být obarveni pouze třemi barvami; nicméně, Häggkvist (1981) vyvrátil tuto domněnku nalezením protipříkladu, ve kterém je každý vrchol Grötzschova grafu nahrazen nezávislou sadou pečlivě zvolené velikosti. Jin (1995) ukázal, že každý n-vertexový trojúhelníkový graf, ve kterém má každý vrchol více než 10n/ 29 sousedů musí být tříbarevných; toto je nejlepší možný výsledek tohoto typu, protože Häggkvistův graf vyžaduje čtyři barvy a má přesně 10n/ 29 sousedů na vrchol. Konečně, Brandt & Thomassé (2006) dokázal, že jakýkoli n-vertexový trojúhelníkový graf, ve kterém má každý vrchol více než n/ 3 sousedé musí být 4barevní. Další výsledky tohoto typu nejsou možné, jako Hajnal^[9] nalezené příklady grafů bez trojúhelníků s libovolně velkým chromatickým číslem a minimálním stupněm (1/3 - ε)n pro libovolné ε> 0.

Viz také

Andrásfai graf, rodina cirkulačních grafů bez trojúhelníků o průměru dva
Hensonův graf, nekonečný graf bez trojúhelníků, který obsahuje všechny konečné grafy bez trojúhelníků jako indukované podgrafy
Monochromatický trojúhelník problém, problém rozdělení hran daného grafu do dvou grafů bez trojúhelníků
Problém Ruzsa – Szemerédi, na grafech, ve kterých každá hrana patří přesně jednomu trojúhelníku

Reference

Poznámky

^ Alon, Yuster & Zwick (1994).
^ Le Gall (2014), vylepšení předchozích algoritmů o Lee, Magniez & Santha (2013) a Milované (2012).
^ Boppana & Halldórsson (1992) str. 184, na základě nápadu z dřívějšího algoritmu zbarvení aproximace Avi Wigderson.
^ Kim (1995).
^ Erdős, Suen & Winkler (1995); Bohman (2009).
^ Alon, Ben-Shimon a Krivelevich (2010).
^ Grötzsch (1959); Thomassen (1994) ).
^ Chvátal (1974).
^ vidět Erdős & Simonovits (1973).

Zdroje

Alon, Noga; Ben-Shimon, Sonny; Krivelevich, Michael (2010), „Poznámka k pravidelným Ramseyho grafům“, Journal of Graph Theory, 64 (3): 244–249, arXiv:0812.2386, doi:10.1002 / jgt.20453, PAN 2674496, S2CID 1784886.
Alon, N.; Yuster, R .; Zwick, U. (1994), "Hledání a počítání daných délkových cyklů", Sborník z 2. evropského sympozia o algoritmech, Utrecht, Nizozemsko, str. 354–364.
Andrásfai, B .; Erdős, P.; Sós, V. T. (1974), "O spojení mezi chromatickým číslem, maximální klikou a minimálním stupněm grafu" (PDF), Diskrétní matematika, 8 (3): 205–218, doi:10.1016 / 0012-365X (74) 90133-2.
Belovs, Aleksandrs (2012), „Span programs for functions with constant-sized 1-certificates“, Sborník ze čtyřicátého čtvrtého výročního sympózia ACM o teorii práce s počítači (STOC '12), New York, NY, USA: ACM, s. 77–84, arXiv:1105.4024, doi:10.1145/2213977.2213985, ISBN 978-1-4503-1245-5, S2CID 18771464.
Bohman, Tom (2009), „Proces bez trojúhelníků“, Pokroky v matematice, 221 (5): 1653–1677, arXiv:0806.4375, doi:10.1016 / j.aim.2009.02.018, PAN 2522430, S2CID 17701040.
Boppana, Ravi; Halldórsson, Magnús M. (1992), „Přibližování maximálního počtu nezávislých souborů vyloučením podgrafů“, BIT, 32 (2): 180–196, doi:10.1007 / BF01994876, PAN 1172185, S2CID 123335474.
Brandt, S .; Thomassé, S. (2006), Husté grafy bez trojúhelníků jsou čtyřbarevné: řešení problému Erdős – Simonovits (PDF).
Chiba, N .; Nishizeki, T. (1985), „Algoritmy arboricity a podgrafu“, SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803.
Chvátal, Vašek (1974), „Minimalita Mycielského grafu“, Grafy a kombinatorika (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973)Přednášky z matematiky, 406, Springer-Verlag, str. 243–246.
Erdős, P.; Simonovits, M. (1973), „K valenčnímu problému v teorii extrémních grafů“, Diskrétní matematika, 5 (4): 323–334, doi:10.1016 / 0012-365X (73) 90126-X.
Erdős, P.; Suen, S .; Winkler, P. (1995), „O velikosti náhodného maximálního grafu“, Náhodné struktury a algoritmy, 6 (2–3): 309–318, doi:10.1002 / rsa.3240060217.
Gimbel, John; Thomassen, Carsten (2000), "Barvení grafů bez trojúhelníků s pevnou velikostí", Diskrétní matematika, 219 (1–3): 275–277, doi:10.1016 / S0012-365X (00) 00087-X.
Grötzsch, H. (1959), „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, 8: 109–120.
Häggkvist, R. (1981), „Liché cykly specifikované délky v nebipartitních grafech“, Teorie grafů (Cambridge, 1981), 62, str. 89–99, doi:10.1016 / S0304-0208 (08) 73552-7.
Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Mediánové grafy a grafy bez trojúhelníků", SIAM Journal on Discrete Mathematics, 12 (1): 111–118, doi:10.1137 / S0895480197323494, PAN 1666073, S2CID 14364050.
Itai, A .; Rodeh, M. (1978), "Hledání minimálního obvodu v grafu", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033.
Jin, G. (1995), „Trojúhelníkové čtyři chromatické grafy“, Diskrétní matematika, 145 (1–3): 151–170, doi:10.1016 / 0012-365X (94) 00063-O.
Kim, J. H. (1995), „Ramseyho číslo ${displaystyle R (3, t)}$ má řádovou velikost ${displaystyle {frac {t ^ {2}} {log t}}}$ ", Náhodné struktury a algoritmy, 7 (3): 173–207, doi:10.1002 / rsa.3240070302, S2CID 16658980.
Le Gall, François (říjen 2014), „Vylepšený kvantový algoritmus pro hledání trojúhelníků pomocí kombinatorických argumentů“, Sborník z 55. výročního symposia o základech informatiky (FOCS 2014), IEEE, s. 216–225, arXiv:1407.0085, doi:10.1109 / focs.2014.31, ISBN 978-1-4799-6517-5, S2CID 5760574.
Lee, Troy; Magniez, Frédéric; Santha, Miklos (2013), „Vylepšené algoritmy kvantového dotazu pro hledání trojúhelníků a testování asociativity“, Sborník dvacátého čtvrtého ročníku sympozia ACM-SIAM o diskrétních algoritmech (SODA 2013), New Orleans, Louisiana, str. 1486–1502, ISBN 978-1-611972-51-1.
Mycielski, J. (1955), „Sur le coloriage des graphes“, Colloq. Matematika., 3 (2): 161–162, doi:10,4064 / cm-3-2-161-162.
Nilli, A. (2000), „Grafy bez trojúhelníků s velkými chromatickými čísly“, Diskrétní matematika, 211 (1–3): 261–262, doi:10.1016 / S0012-365X (99) 00109-0.
Shearer, J. B. (1983), „Poznámka k počtu nezávislostí grafů bez trojúhelníků“, Diskrétní matematika, 46 (1): 83–87, doi:10.1016 / 0012-365X (83) 90273-X.
Thomassen, C. (1994), „Grötzschova tříbarevná věta“, Journal of Combinatorial Theory, Series B, 62 (2): 268–279, doi:10.1006 / jctb.1994.1069.

externí odkazy

"Graphclass: bez trojúhelníků", Informační systém o třídách grafů a jejich začlenění

[FOOTNOTEAlonYusterZwick1994-1] Alon, Yuster & Zwick (1994).

[2] Le Gall (2014), vylepšení předchozích algoritmů o Lee, Magniez & Santha (2013) a Milované (2012).

[3] Boppana & Halldórsson (1992) str. 184, na základě nápadu z dřívějšího algoritmu zbarvení aproximace Avi Wigderson.

[FOOTNOTEKim1995-4] Kim (1995).

[5] Erdős, Suen & Winkler (1995); Bohman (2009).

[FOOTNOTEAlonBen-ShimonKrivelevich2010-6] Alon, Ben-Shimon a Krivelevich (2010).

[7] Grötzsch (1959); Thomassen (1994) ).

[FOOTNOTEChvátal1974-8] Chvátal (1974).

[9] vidět Erdős & Simonovits (1973).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]