Poikinut polku
Graafiteoriassa generoitu polku ohjaamattomassa graafissa G on polku , joka on G :n generoitu aligraafi . Siten se on G :n kärkijono siten, että mitkä tahansa kaksi vierekkäistä kärkeä sekvenssissä on yhdistetty G :n reunalla , ja mitkä tahansa sekvenssin kaksi ei-vierekkäistä kärkeä eivät ole yhteydessä G :n reunalla . Luotua polkua kutsutaan joskus käärmeeksi , ja pisimmän generoidun polun löytäminen hyperkuutiokaavioista tunnetaan nimellä käärme-in-the-box -ongelma .
Myös generoiduksi jaksoksi kutsutaan sykliä , joka on G :n generoitu aligraafi . Luotuja syklejä kutsutaan myös jaksoiksi ilman sointuja tai (jos syklin pituus on vähintään neljä) reikiä . Antireikä on reikä graafin G komplementissa , eli antireikä on reiän komplementti.
Kuvaajan pisimmän generoidun polun pituutta kutsutaan joskus graafin läpikulkunumeroksi [1] . Harvassa graafissa rajatun läpikulkuluvun olemassaolo vastaa rajatun puun syvyyden olemassaoloa [2] . Graafin G generoitu läpikulkunumero on pienin määrä pisteiden osajoukkoja, joihin graafin kärjet voidaan jakaa siten, että jokainen osajoukko muodostaa generoidun polun [3] ja tämä käsite liittyy läheisesti polun peittonumeroon - pienin määrä katkaistuja polkuja, jotka ovat generoituja G :n aligraafia , jotka kattavat kaikki kärjet G [4] . Graafin ympärysmitta on sen lyhimmän jakson pituus, mutta tämän jakson on oltava generoitu jakso, koska mikä tahansa sointu voi muodostaa lyhyemmän jakson. Samoista syistä graafin pariton ympärysmitta on sen lyhimmän parittoman generoidun jakson pituus.
Esimerkki
Kuvassa on kuutio, graafi, jossa on kahdeksan kärkeä, kaksitoista reunaa ja generoitu polku, jonka pituus on neljä. Suora analyysi osoittaa, että kuutiossa ei ole enää generoitua polkua, vaikka on generoitu kuuden pituinen sykli. Ongelma suurimman generoidun polun tai syklin löytämisestä hyperkuutiosta, jonka ensin esitti Kautz [5] , tunnetaan käärme laatikossa -ongelmana ja sitä on tutkittu laajasti sen käytön vuoksi koodausteoriassa ja -konstruktiossa.
Kuvaus kaavioperheistä
Monet tärkeät kaavioperheet voidaan kuvata perheen kaavioiden generoitujen polkujen tai jaksojen avulla.
- Ilmeisesti yhdistetyt kuvaajat, joilla ei ole generoituja polkuja, joiden pituus on kaksi, ovat täydellisiä kuvaajia , ja yhdistetyt kuvaajat, joissa ei ole generoituja syklejä, ovat puita .
- Kaavio ilman kolmioita on kaavio ilman generoituja syklejä, joiden pituus on kolme.
- Kuvaajat ovat täsmälleen kaavioita ilman generoituja polkuja, joiden pituus on kolme.
- Sointukaaviot ovat kaavioita, joissa ei ole generoituja jaksoja, joiden pituus on neljä tai enemmän.
- Graafit, joissa ei ole parillisen pituisia reikiä , ovat kaavioita, joissa ei ole sykliä, jotka sisältävät parillisen määrän pisteitä.
- Triviaalisti täydelliset graafit ovat kaavioita, joissa ei ole generoituja polkuja, joiden pituus on kolme, eivätkä generoituja jaksoja, joiden pituus on neljä.
- Tiukan täydellisen graafin lauseen mukaan täydelliset graafit ovat kaavioita, joissa ei ole parittomia reikiä ja parittomat antireikiä.
- Etäisyyden periytyneet graafit ovat kaavioita, joissa mikä tahansa generoitu polku on lyhin polku, ja näissä kaavioissa millä tahansa kahdella generoidulla polulla kahden kärjen välillä on sama pituus.
- Lohkograafit ovat kaavioita, joissa on enintään yksi generoitu polku minkä tahansa kahden kärjen välillä, ja yhdistetyt lohkokaaviot ovat kaavioita, joissa on täsmälleen yksi generoitu polku minkä tahansa kahden kärjen välillä.
Algoritmit ja monimutkaisuus
Ongelma sen määrittämiseksi, onko graafilla G generoitu polku, jonka pituus on vähintään k , on NP-täydellinen. Gary ja Johnson [6] ilmaisivat tämän tuloksen julkaisemattomassa tiedonannossa Michalis Giannakakisille . Tämä ongelma voidaan kuitenkin ratkaista polynomiajassa tietyille kaavioperheille, kuten graafit ilman asteroidikolmioita [7] tai graafit ilman pitkiä reikiä [8] .
On myös NP-täydellinen ongelma määrittää, voidaanko graafin pisteet hajottaa kahdeksi generoiduksi poluksi vai kahdeksi generoiduksi sykliksi [9] . Tämän seurauksena generoitujen polkujen määrän määrittäminen kaaviossa on NP-kova ongelma.
Suurimman generoidun polun tai syklin approksimoimisen ongelman monimutkaisuus voidaan yhdistää ongelmaan löytää suurimmat riippumattomat joukot kaavioista [10] .
Reiät (ja antireiät graafissa, jossa ei ole 5 pituisia jaksoja ilman sointuja) graafissa, jossa on n kärkeä ja m reunaa, voidaan löytää ajassa (n+m 2 ) [11] .
Atomisyklit
Atomisyklit ovat syklien yleistys ilman sointuja. Jos sykli on annettu, n -sointu määritellään n pituiseksi poluksi, joka sisältää kaksi syklipistettä, missä n on pienempi kuin nämä pisteet yhdistävän syklin lyhimmän polun pituus. Jos syklissä ei ole n -sointuja, sitä kutsutaan atomisykliksi, koska sitä ei voida pilkkoa pienempiin sykleihin [12] . Pahimmassa tapauksessa graafin atomisyklit voidaan laskea O( m 2 ) -ajassa, missä m on graafin reunojen lukumäärä.
Muistiinpanot
- ↑ Buckley, Harary, 1988 .
- ↑ Nešetřil, Ossona de Mendez, 2012 , Ehdotus 6.4, s. 122.
- ↑ Chartrand et ai., 1994 .
- ↑ Barioli, Fallat, Hogben, 2004 .
- ↑ Kautz, 1958 .
- ↑ Garey, Johnson, 1979 .
- ↑ Kratsch, Müller, Todinca, 2003 .
- ↑ Gavril, 2002 .
- ↑ Le, Le, Müller, 2003 .
- ↑ Berman, Schnitger, 1992 .
- ↑ Nikolopoulos, Palios, 2004 .
- ↑ Gashler, Martinez, 2012 .
Kirjallisuus
- Francesco Barioli, Shaun Fallat, Leslie Hogben. Vähimmäisluokituksen ja polun kansinumeron laskeminen tietyille kaavioille // Linear Algebra Appl .. - 2004. - T. 392 . - S. 289-303 . - doi : 10.1016/j.laa.2004.06.019 .
- Piotr Berman, Georg Schnitger. Riippumattoman joukkoongelman approksimoinnin monimutkaisuudesta // Information and Computation. - 1992. - T. 96 . - S. 77-94 . - doi : 10.1016/0890-5401(92)90056-L .
- Fred Buckley, Frank Harary. Pisin indusoituneilla poluilla kaavioissa // Chinese Quart. J Math. - 1988. - T. 3 . - S. 61-65 .
- Gary Chartrand, Joseph McCanna, Naveed Sherwani, Moazzem Hossain, Jahangir Hashmi. Kaksiosaisten graafien indusoitu polkumäärä // Ars Combin .. - 1994. - T. 37 . - S. 191-208 .
- Michael R. Garey, David S. Johnson. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - S. 196 .
- Michael Gashler, Tony Martinez. Vankka monitoimioppiminen CycleCutilla // Connection Science. - 2012. - T. 24 , no. 1 . - S. 57-69 . - doi : 10.1080/09540091.2012.664122 .
- Fănică Gavril. Algoritmit maksimipainon aiheuttamille poluille // Information Processing Letters. - 2002. - T. 81 , no. 4 . - S. 203-208 . - doi : 10.1016/S0020-0190(01)00222-8 .
- Johan Hastad. Proceedings of 37th Annual IEEE Symposium on Foundations of Computer Science. - 1996. - S. 627-636. - doi : 10.1109/SFCS.1996.548522 .
- W. H. Kautz. Yksikköetäisyyden virheentarkistuskoodit // IRE Trans. Valita. Comput.. - 1958. - T. 7 . - S. 177-180 .
- Dieter Kratsch, Haiko Müller, Ioan Todinca. Tietojenkäsittelytieteen graafiteoreettiset käsitteet . Berlin: Lecture Notes in Computer Science, Voi. 2880, Springer-Verlag, 2003, s. 309-321. - doi : 10.1007/b93953 .
- Hoàng-Oanh Le, Van Bang Le, Haiko Müller. Graafin jakaminen epäyhtenäisiksi indusoiduiksi poluiksi tai sykleiksi // Discrete Appl. Math.. - 2003. - Vol. 131 , no. 1 . - S. 199-212 . - doi : 10.1016/S0166-218X(02)00425-0 .
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: kaaviot, rakenteet ja algoritmit. - Heidelberg: Springer, 2012. - T. 28. - S. 115-144. — (Algoritmit ja kombinatoriikka). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
- Stavros D. Nikolopoulos, Leonidas Palios. Proc. 15. ACM-SIAM-symposium diskreeteistä algoritmeista. - 2004. - S. 850-859.