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.

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

  1. ↑ Buckley, Harary, 1988 .
  2. ↑ Nešetřil, Ossona de Mendez, 2012 , Ehdotus 6.4, s. 122.
  3. ↑ Chartrand et ai., 1994 .
  4. ↑ Barioli, Fallat, Hogben, 2004 .
  5. ↑ Kautz, 1958 .
  6. ↑ Garey, Johnson, 1979 .
  7. ↑ Kratsch, Müller, Todinca, 2003 .
  8. ↑ Gavril, 2002 .
  9. ↑ Le, Le, Müller, 2003 .
  10. ↑ Berman, Schnitger, 1992 .
  11. ↑ Nikolopoulos, Palios, 2004 .
  12. ↑ Gashler, Martinez, 2012 .

Kirjallisuus