Skapad väg

I grafteorin är en genererad väg i en oriktad graf G en väg som är en genererad subgraf till G . Sålunda är det en sekvens av hörn i G så att två intilliggande hörn i sekvensen är förbundna med en kant i G , och vilka två icke-angränsande hörn av sekvensen som helst inte är förbundna med en kant i G . En genererad bana kallas ibland en orm , och problemet med att hitta den längsta genererade banan i hyperkubgrafer kallas orm-in-the-box- problemet .

Kallas även en genererad cykel är en cykel som är en genererad subgraf av G . De genererade cyklerna kallas också cykler utan ackord eller (om längden på cykeln är minst fyra) hål . Ett antihål är ett hål i komplementet till en graf G , det vill säga ett antihål är komplementet till ett hål.

Längden på den längsta genererade banan i en graf kallas ibland för grafens genomgångsnummer [1] . För glesa grafer är förekomsten av ett begränsat genomgångsnummer ekvivalent med förekomsten av ett begränsat träddjup [2] . Det genererade genomgångsnumret för en graf G är det minsta antalet delmängder av hörn som grafens hörn kan dekomponeras i, så att varje delmängd bildar en genererad bana [3] , och detta koncept är nära relaterat till vägtäckningsnumret - det minsta antalet frånkopplade vägar som genereras subgrafer av G , som täcker alla hörn G [4] . Omkretsen på en graf är längden på dess kortaste cykel, men denna cykel måste vara en genererad cykel, eftersom vilket ackord som helst kan bilda en kortare cykel. Av samma skäl är den udda omkretsen av en graf längden på dess kortaste udda genererade cykel.

Exempel

Figuren visar en kub, en graf med åtta hörn, tolv kanter och en genererad bana med längd fyra. Direkt analys visar att det inte längre finns en genererad väg i kuben, även om det finns en genererad cykel av längd sex. Problemet med att hitta den största genererade vägen eller cykeln i en hyperkub, som först ställdes av Kautz [5] , är känt som problemet med ormen i en låda och har studerats omfattande på grund av dess användning i kodningsteori och konstruktion.

Beskrivning av graffamiljer

Många viktiga familjer av grafer kan beskrivas i termer av de genererade vägarna eller cyklerna för graferna i familjen.

Algoritmer och komplexitet

Problemet med att avgöra om en graf G har en genererad väg med längden minst k är NP-komplett. Gary och Johnson [6] uttryckte detta resultat i ett opublicerat meddelande till Michalis Giannakakis . Detta problem kan dock lösas i polynomtid för vissa familjer av grafer, till exempel grafer utan asteroidtrippel [7] eller grafer utan långa hål [8] .

Det är också ett NP-komplett problem att avgöra om en grafs hörn kan delas upp i två genererade vägar eller två genererade cykler [9] . Som en konsekvens är att bestämma antalet genererade vägar i en graf ett NP-hårt problem.

Komplexiteten i problemet med att approximera den största genererade vägen eller cykeln kan associeras med problemet att hitta de största oberoende uppsättningarna i grafer [10] .

Hål (och antihål i grafer utan cykler med längd 5 utan ackord) i en graf med n hörn och m kanter kan hittas i tiden (n+m 2 ) [11] .

Atomcykler

Atomcykler är en generalisering av cykler utan ackord. Om en cykel ges, definieras ett n -ackord som en väg med längden n som innehåller två cykelpunkter, där n är mindre än längden på den kortaste vägen i cykeln som förbinder dessa punkter. Om en cykel inte har några n -ackord kallas den för en atomcykel eftersom den inte kan brytas ner i mindre cykler [12] . I värsta fall kan atomcykler i en graf räknas upp i O( m 2 ) tid, där m är antalet kanter i grafen.

Anteckningar

  1. ↑ Buckley, Harary, 1988 .
  2. ↑ Nešetřil, Ossona de Mendez, 2012 , Proposition 6.4, s. 122.
  3. ↑ Chartrand et al., 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 .

Litteratur