Inducerad väg

En inducerad bana av längd fyra i en kub . Att hitta den längsta inducerade vägen i en hyperkub kallas orm-in-the-box- problemet.

Inom det matematiska området för grafteorin är en inducerad väg i en oriktad graf G en väg som är en inducerad subgraf till G. Det vill säga, det är en sekvens av hörn i G så att var och en av två angränsande hörn i sekvensen är förbundna med en kant i G , och var och en av två icke-angränsande hörn i sekvensen är inte förbundna med någon kant i G . En inducerad bana kallas ibland en orm , och problemet med att hitta långa inducerade banor i hyperkubgrafer kallas orm-in-the-box- problemet.

är en inducerad cykel en cykel som är en inducerad subgraf av G ; inducerade cykler kallas också ackordlösa cykler eller (när cykelns längd är fyra eller fler) hål . Ett antihål är ett hål i komplementet till G , dvs ett antihål är ett komplement till ett hål.

Längden på den längsta inducerade vägen i en graf har ibland kallats grafens omvägsnummer ; för glesa grafer , att ha ett begränsat omvägsnummer motsvarar att ha ett begränsat träddjup . Det inducerade vägnumret för en graf G är det minsta antalet inducerade banor som grafens hörn kan delas in i, och det närbesläktade bantäckningsnumret för G är det minsta antalet inducerade banor som tillsammans inkluderar alla hörn hos G. Omkretsen på en graf är längden på dess kortaste cykel, men denna cykel måste vara en inducerad cykel eftersom vilket ackord som helst kan användas för att producera en kortare cykel ; av liknande skäl är den udda omkretsen av en graf också längden på dess kortaste udda inducerade cykel.

Exempel

Maximala längder på ormar ( L s ) och spolar ( L c ) i problemet med ormar-i-lådan för dimensioner n från 1 till 4

Illustrationen visar en kub, en graf med åtta hörn och tolv kanter och en inducerad bana med längd fyra i denna graf. En enkel fallanalys visar att det inte längre kan finnas inducerad väg i kuben, även om den har en inducerad cykel av längd sex. Problemet med att hitta den längsta inducerade vägen eller cykeln i en hyperkub, som först ställdes av Kautz (1958), är känt som orm-in-the-box- problemet, och det har studerats omfattande på grund av dess tillämpningar inom kodningsteori och teknik. .

Karakterisering av graffamiljer

Många viktiga graffamiljer kan karakteriseras i termer av de inducerade vägarna eller cyklerna för graferna i familjen.

  • Trivialt är de anslutna graferna utan inducerad bana av längd två de kompletta graferna och de anslutna graferna utan inducerad cykel är träden .
  • En triangelfri graf är en graf utan inducerad cykel av längd tre.
  • Kograferna är exakt de grafer utan inducerad väg av längd tre .
  • Ackordsgraferna är graferna utan inducerad cykel av längd fyra eller mer .
  • De jämna hålsfria graferna är de grafer som inte innehåller några inducerade cykler med ett jämnt antal hörn.
  • De trivialt perfekta graferna är de grafer som varken har en inducerad väg av längd tre eller en inducerad cykel av längd fyra.
  • Enligt den starka perfekta grafsatsen är de perfekta graferna graferna utan udda hål och inget udda antihål.
  • De ärftliga avståndsgraferna är de grafer där varje inducerad väg är den kortaste vägen, och de grafer där varannan inducerad väg mellan samma två hörn har samma längd.
  • Blockgraferna är de grafer i vilka det finns högst en inducerad bana mellan vilka två hörn som helst, och de anslutna blockgraferna är de grafer i vilka det finns exakt en inducerad bana mellan varannan hörn .

Algoritmer och komplexitet

Det är NP-komplett att bestämma, för en graf G och parameter k , om grafen har en inducerad väg av minst k längd . Garey & Johnson (1979) tillskriver detta resultat ett opublicerat meddelande från Mihalis Yannakakis . Detta problem kan dock lösas i polynomtid för vissa graffamiljer, såsom asteroid-trippelfria grafer eller grafer utan långa hål.

Det är också NP-komplett för att bestämma om hörnen i en graf kan delas upp i två inducerade banor eller två inducerade cykler. Som en konsekvens är det NP-hårt att bestämma det inducerade vägnumret för en graf.

Komplexiteten i att approximera de längsta inducerade väg- eller cykelproblemen kan relateras till att hitta stora oberoende uppsättningar i grafer, genom följande minskning. Från valfri graf G med n hörn, bilda en annan graf H med dubbelt så många hörn som G , genom att addera till G n ( n − 1)/2 hörn med två grannar vardera, en för varje par av hörn i G . Om G sedan har en oberoende uppsättning av storleken k , måste H ha en inducerad bana och en inducerad cykel av längden 2 k , bildad genom att alternerande hörn av den oberoende mängden i G med hörn av I. Omvänt, om H har en inducerad bana eller cykel av längden k , bildar varje maximal uppsättning icke-angränsande hörn i G från denna väg eller cykel en oberoende uppsättning i G med storleken åtminstone k /3. Således är storleken på den maximala oberoende mängden i G inom en konstant faktor av storleken på den längsta inducerade vägen och den längsta inducerade cykeln i H . Enligt resultaten av Håstad (1996) om inapproximability av oberoende uppsättningar, såvida inte NP=ZPP, finns det därför inte en polynomisk tidsalgoritm för att approximera den längsta inducerade vägen eller den längsta inducerade cykeln inom en faktor O( n 1 / 2-ε ) av den optimala lösningen.

Hål (och antihål i grafer utan ackordlösa cykler med längd 5) i en graf med n hörn och m kanter kan detekteras i tid (n+m 2 ).

Atomcykler

Atomcykler är en generalisering av ackordlösa cykler, som inte innehåller några n -ackord. Givet någon cykel definieras ett n -ackord som en väg med längden n som förbinder två punkter på cykeln, där n är mindre än längden på den kortaste vägen på 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 upp i mindre cykler. I värsta fall kan atomcyklerna i en graf räknas upp i O( m 2 ) tid, där m är antalet kanter i grafen.

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Induced_path&oldid=1120617554 "