Kaavio ilman kolmioita

Graafiteoriassa kolmioton graafi on suuntaamaton graafi, jossa ei kolme kärkeä muodosta reunojen kolmiota . Kolmiovapaat graafit voidaan määritellä myös graafisiksi, joiden klikkiluku on ≤ 2, kaavioiksi, joiden ympärysmitta on ≥ 4, kuvaajiksi, joissa ei ole generoitua 3-sykliä tai paikallisesti riippumattomina kaavioina.

Turanin lauseen mukaan n -pisteinen kolmiovapaa graafi , jossa on maksimimäärä reunoja, on täydellinen kaksiosainen graafi , jossa graafin kunkin osan kärkien määrät ovat mahdollisimman lähellä.

Graafilla, jossa on 2n kärkeä ja jossa ei ole kolmioita, tulee olla vähemmän reunoja. $n^{2}+1$

Kolmioiden löytämisen ongelma

Kolmioiden löytämisen ongelma on ongelma sen määrittämisessä, sisältääkö kaavio kolmioita vai ei. Jos graafi sisältää kolmion, algoritmia pyydetään usein tulostamaan kolme kärkeä, jotka muodostavat kolmion.

On mahdollista tarkistaa, onko graafissa, jossa on m reunaa, kolmioita O( m 1.41 ) -ajassa. [1] Toinen lähestymistapa on löytää matriisin A 3 jälki , jossa A on graafin vierekkäisyysmatriisi . Jälki on nolla silloin ja vain, jos kaaviossa ei ole kolmioita. Tiheille graafiille tämä yksinkertainen matriisin kertolaskualgoritmi on tehokkaampi, koska se vähentää aikamonimutkaisuuden O( n 2.373 ), missä n on pisteiden lukumäärä.

Kuten Imrich, Klavžar ja Mulder ( Imrich, Klavžar, Mulder 1999 ) ovat osoittaneet, kolmioton graafin tunnistus vastaa monimutkaisuudeltaan mediaanikuvaajan tunnistusta . Kuitenkin tällä hetkellä parhaat mediaanigrafiikkaalgoritmit käyttävät kolmion tunnistusta aliohjelmana, eivät päinvastoin.

Päätöspuun tai ongelman kyselyn monimutkaisuus , jossa kyselyt graafin vierekkäisyysmatriisit muistavaan oraakkeliin, on yhtä suuri kuin Θ( n 2 ). Kvanttialgoritmeille paras alaraja on kuitenkin Ω( n ), mutta tunnetuimman algoritmin arvio on O( n 1,29 ) ( Belovs 2011 ).

Itsenäisyysluku ja Ramseyn teoria

Itsenäinen kärkijoukko n - pisteen kolmiottomasta graafista on helppo löytää – joko kärkipisteessä on enemmän kuin naapureita (jolloin naapurit muodostavat itsenäisen joukon), tai kaikilla pisteillä on vähemmän kuin naapureita (jossa tapauksessa missä tahansa suurimmassa itsenäisessä joukossa on oltava vähintään kärjet) [2] . Tätä rajaa voidaan hieman parantaa - missä tahansa graafissa ilman kolmioita on riippumaton joukko, jossa on kärkipisteitä, ja joissakin graafisissa ilman kolmioita missä tahansa itsenäisessä joukossa on kärjet. [3] Yksi tapa luoda tegonittomia graafia, joissa kaikki riippumattomat joukot ovat pieniä, on kolmioton prosessi [ 4] , joka luo maksimaalisia kolmioitavapaita graafia lisäämällä peräkkäin satunnaisesti valittuja reunoja välttäen kolmioiden luomista. Prosessi muodostaa suurella todennäköisyydellä kuvaajia, joiden riippumattomuusluku on . Voidaan myös löytää säännöllisiä kaavioita , joilla on samat ominaisuudet. [5] ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ $\Omega ({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$

Nämä tulokset voidaan ymmärtää myös Ramsey-lukujen R(3, t ) asymptoottisten rajojen asettamisena muotoon - jos kokonaisen graafin, jossa on pisteet, reunat ovat punaisia ja sinisiä, niin joko punainen graafi sisältää kolmion tai siinä ei ole kolmioita, ja silloin täytyy olla olemassa riippumaton joukko, jonka koko on t , joka vastaa tämän kokoista klikkiä sinisessä kaaviossa. $\Theta ({\tfrac {t^{2)){\log t)))$ $\Omega ({\tfrac {t^{2)){\log t)))$

Kaavioiden väritys ilman kolmioita

Suuri osa kolmiottomien kaavioiden tutkimuksesta on keskittynyt kuvaajien värjäämiseen . Missä tahansa kaksiosaisessa graafissa (eli missä tahansa kaksivärisessä graafissa) ei ole kolmioita, ja Grötzschin lause sanoo, että mikä tahansa kolmioton tasograafi voi olla kolmivärinen. [6] Epätasoiset kuvaajat ilman kolmioita voivat kuitenkin vaatia enemmän kuin kolme väriä.

Mycielski ( 1955 ) määritteli konstruktion, jota nykyään kutsutaan Mycielskiksi ja joka muodostaa uuden kolmiottoman graafin toisesta kolmiosta vapaasta graafista. Jos graafilla on kromaattinen luku k , sen Mychelskin kromaattinen luku on k + 1, joten tätä konstruktiota voidaan käyttää osoittamaan, että kolmiosta vapaan epätasoisen graafin värittämiseen voidaan tarvita mielivaltaisen suuri määrä värejä. Erityisesti Grötzsch -graafi, 11-pisteinen graafi, joka on muodostettu toistamalla Mycielskin konstruktiota, on kolmioton graafi, jota ei voi värjätä alle neljällä värillä, ja se on pienin graafi, jolla on nämä ominaisuudet. [7] Gimbel ja Thomassen ( Gimbel, Thomassen & 2000 ) ja ( Nilli 2000 ) osoittivat, että minkä tahansa kolmiottoman m -viivakaavion värittämiseen tarvittavien värien määrä on

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

ja on kolmiota sisältämättömiä kaavioita, joiden kromaattiset luvut ovat verrannollisia tähän rajaan.

Myös värityksen ja kolmiottomien graafien vähimmäisasteen välisestä yhteydestä on saatu tuloksia. Andrásfai ja Erdős ( Andrásfai, Erdős, Sós 1974 ) osoittivat, että minkä tahansa n -pisteisen kolmiottoman graafin, jossa jokaisella kärjellä on useampi kuin yksi naapuri, on oltava kaksiosainen. Tämä on tämän tyypin paras mahdollinen tulos, koska 5-jakso vaatii kolme väriä, mutta sillä on täsmälleen naapurit jokaiselle kärjelle. Tämän tuloksen rohkaisemana Erdős ja Simonovits ( Erdős, Simonovits 1973 ) arvelivat, että mikä tahansa kolmioton graafi, jossa on n kärkeä, jossa jokaisella kärjellä on vähintään naapureita, voidaan värittää vain kolmella värillä. Häggkvist ( 1981 ) kuitenkin kumosi tämän olettamuksen esittämällä vastaesimerkin, jossa Grötsch-graafin kukin kärkipiste on korvattu riippumattomalla, erityisesti valitun kokoisella joukolla. Jin ( Jin 1995 ) osoitti, että mikä tahansa n -pisteen kolmioton graafi, jossa jokaisella kärjellä on useampi kuin yksi naapuri, voi olla 3-värinen. Tämä on tämän tyypin paras tulos, koska Haggquist-graafi vaatii neljä väriä ja sillä on täsmälleen naapurit kullekin kärjelle. Lopuksi Brandt ja Thomassé ( Brandt, Thomassé 2006 ) osoittivat, että mikä tahansa n -pisteinen kolmioton graafi, jossa millä tahansa kärjellä on enemmän kuin 4 naapuria, voidaan värittää 4 värillä. Tämän tyyppiset lisätulokset ovat mahdottomia, koska Hajnal [8] löysi esimerkkejä kolmiottomista graafista, joilla oli mielivaltaisen suuri kromaattinen luku ja minimiaste mille tahansa . $2n/5$ $2n/5$ $n/3$ $10n/29$ $10n/29$ $n/3$ $(1/3-\epsilon )n$ $\epsilon > 0$

Linkit

↑ Alon, Yuster, Zwick, 1994 .
↑ Boppana, Halldórsson, 1992 , Avi Wigdersonin aikaisemman approksimaatioalgoritmin idean pohjalta . 184.
↑ Kim, 1995 .
↑ Erdős, Suen, Winkler, 1995 ; Bohman, 2008
↑ Alon, Ben-Shimon, Krivelevich, 2008 .
↑ Grötzsch, 1959 ; ( Thomassen 1994 )).
↑ Chvatal, 1974 .
↑ katso Erdős, Simonovits, 1973 .

Lähteet

N. Alon, S. Ben-Shimon, M. Krivelevich. Huomautus tavallisista Ramsey-kaavioista. – 2008.
N. Alon, R. Yuster, U. Zwick. Proceedings of 2nd European Symposium on Algorithms , Utrecht, Alankomaat. - 1994. - S. 354-364 .
B. Andrásfai, P. Erdős, VT Sos. Kromaattisen luvun, maksimiklikin ja graafin minimiasteen välisestä yhteydestä // Diskreetti matematiikka . - 1974. - T. 8 , no. 3 . — S. 205–218 . - doi : 10.1016/0012-365X(74)90133-2 .
T. Bohman. Kolmioton prosessi . – 2008.
Ravi Boppana, Magnús M. Halldorsson. Riippumattomien joukkojen enimmäismäärän arvioiminen jättämällä pois aligraafit // BIT. - 1992. - T. 32 , no. 2 . — S. 180–196 . - doi : 10.1007/BF01994876 .
S. Brandt, S. Thomasse. Tiheät kolmiovapaat graafit ovat nelivärisiä: ratkaisu Erdős-Simonovits-ongelmaan. - 2006. Arkistoitu 4. helmikuuta 2012.
N. Chiba, T. Nishizeki. Arboricity ja aligraafien listausalgoritmit // SIAM Journal on Computing . - 1985. - T. 14 , no. 1 . — S. 210–223 . - doi : 10.1137/0214017 .
Vasek Chvatal. Graafit ja kombinatoriikka (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973). - Springer-Verlag, 1974. - T. 406. - S. 243-246. — (Matematiikan luentomuistiinpanot).
P. Erdős, M. Simonovits. Valenssiongelmasta äärimmäisessä graafiteoriassa // Diskreetti matematiikka. - 1973. - V. 5 , no. 4 . — S. 323–334 . - doi : 10.1016/0012-365X(73)90126-X .
P. Erdős, S. Suen, P. Winkler. Satunnaisen maksimigraafin koosta // Satunnaiset rakenteet ja algoritmit. - 1995. - T. 6 , no. 2-3 . — S. 309–318 . - doi : 10.1002/rsa.3240060217 .
John Gimbel, Carsten Thomassen. Kolmiottomien kaavioiden väritys kiinteällä koossa // Discrete Mathematics. - 2000. - T. 219 , no. 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. Graph Theory (Cambridge, 1981). - 1981. - S. 89-99 .
Wilfried Imrich, Sandi Klavžar, Henry Martyn. Mediaanikaaviot ja kolmiotottomat graafit // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , no. 1 . — s. 111–118 . - doi : 10.1137/S0895480197323494 .
A. Itai, M. Rodeh. Minimipiirin löytäminen kaaviosta // SIAM Journal on Computing . - 1978. - V. 7 , no. 4 . — S. 413–423 . - doi : 10.1137/0207033 .
G. Jin. Kolmiotonta nelikromaattista kuvaajaa // Diskreetti matematiikka. - 1995. - T. 145 , no. 1-3 . — S. 151–170 . - doi : 10.1016/0012-365X(94)00063-O .
JH Kim. Ramsey-luvulla on suuruusluokka // Random Structures and Algorithms. - 1995. - T. 7 , no. 3 . — S. 173–207 . $R(3,t)$ ${\tfrac {t^{2}}{\log t}}$
Frederic Magniez, Miklos Santha, Mario Szegedy. Kvanttialgoritmit kolmioongelmalle. – 2003.
J. Mycielski. Sur le coloriage des graphes // Colloq. Matematiikka.. - 1955. - T. 3 . — S. 161–162 .
A. Nilli. Kolmiottomat graafit suurilla kromaattisilla luvuilla // Diskreetti matematiikka. - 2000. - T. 211 , no. 1-3 . — S. 261–262 . - doi : 10.1016/S0012-365X(99)00109-0 .
JB Shearer. Huomautus kolmiottomien graafien riippumattomuudesta // Discrete Mathematics. - 1983. - T. 46 , no. 1 . — s. 83–87 . - doi : 10.1016/0012-365X(83)90273-X .
C. Thomassen. Grötzschin 3-värilause // Journal of Combinatorial Theory, sarja B. - 1994. - T. 62 , no. 2 . — S. 268–279 . - doi : 10.1006/jctb.1994.1069 .
Aleksandrs Belovs. Span-ohjelmat funktioille, joissa on vakiokokoiset 1-sertifikaatit. – 2011.