Caterpillar träd - Caterpillar tree
I grafteorin är en larv eller larvträd ett träd där alla hörn är inom avstånd 1 på en central väg.
Larver studerades först i en serie papper av Harary och Schwenk. Namnet föreslogs av A. Hobbs . Som Harary & Schwenk (1973) färgglatt skriver: "En larv är ett träd som förvandlas till en stig när dess kokong av slutpunkter tas bort."
Motsvarande karaktäriseringar
Följande karakteriseringar beskriver alla larvträden:
- Det är träden för vilka borttagning av löv och infallande kanter ger ett kurvdiagram .
- Det är träden där det finns en väg som innehåller varje toppunkt av grad två eller flera.
- Det är träden där varje toppunkt av minst tre har högst två grannar utan blad.
- Det är träden som inte som en undergraf innehåller grafen som bildas genom att varje kant i stjärndiagrammet K 1,3 ersätts med en bana med längd två.
- De är de anslutna graferna som kan ritas med sina hörn på två parallella linjer, med kanter representerade som icke-korsande linjesegment som har en slutpunkt på varje linje.
- De är träden vars kvadrat är ett hamiltonschema . Det vill säga, i en larv finns det en cyklisk sekvens av alla hörnen där varje intilliggande hörnpar i sekvensen är på avstånd en eller två från varandra, och träd som inte är larver har inte en sådan sekvens. En cykel av denna typ kan erhållas genom att dra larven på två parallella linjer och sammanfoga sekvenserna av hörn på en rad med baksidan av sekvensen på den andra linjen.
- De är träden vars linjediagram innehåller en hamiltonisk väg ; en sådan väg kan erhållas genom ordning av kanterna i en tvåradig ritning av trädet. Mer generellt är antalet kanter som måste läggas till linjediagrammet för ett godtyckligt träd så att det innehåller en hamiltonisk väg (storleken på dess Hamiltonian-färdigställande ) lika med det minsta antalet kantskilda larver som kanterna på trädet kan brytas ner i.
- De är de anslutna graferna för vägbredd ett.
- De är de anslutna triangelfria intervallgraferna .
- De är n-vertex-grafer vars angränsningsmatriser kan skrivas på ett sådant sätt att de i den övre triangulära delen bildar en bana med längd n-1 som börjar i det övre högra hörnet och går ner eller vänster.
Generaliseringar
En k -träd är en korda-graf med exakt n - k maximal klickarna , var och en innehållande k + 1 hörn; i ett k -träd som inte i sig är en ( k + 1) -klick , separerar varje maximal klick antingen grafen i två eller flera komponenter, eller så innehåller den en enda bladpunkt, en toppunkt som tillhör endast en enda maximal klick. En k -bana är ett k -träd med högst två löv, och en k -larv är ett k -träd som kan delas upp i en k -bana och några k -blad, var och en intill en separator k -klick av k -väg. I denna terminologi är en 1-larv samma sak som ett larvträd, och k- larver är de kant-maximala graferna med vägbredden k .
En hummergraf är ett träd där alla hörn är inom avstånd 2 från en central väg .
Uppräkning
Larver ger ett av de sällsynta grafuppräkningsproblemen för vilka en exakt formel kan ges: när n ≥ 3 är antalet larver med n omärkta hörn
För n = 1, 2, 3, ... är antalet n -vertex larver
Beräkningskomplexitet
Att hitta en spännande larv i en graf är NP-komplett . Ett relaterat optimeringsproblem är Minimum Spanning Caterpillar Problem (MSCP), där en graf har dubbla kostnader över kanterna och målet är att hitta ett larvträd som spänner över inmatningsdiagrammet och har den minsta totalkostnaden. Här definieras kostnaden för larven som summan av kostnaderna för dess kanter, där varje kant tar en av de två kostnaderna baserat på dess roll som en bladkant eller en intern. Det finns ingen f (n)- approximationsalgoritm för MSCP om inte P = NP . Här är f (n) vilken polynomtid som helst som kan beräknas med n, antalet hörn i en graf.
Det finns en parametrerad algoritm som hittar en optimal lösning för MSCP i begränsade trädbreddsgrafer . Så både Spanning Caterpillar Problem och MSCP har linjära tidsalgoritmer om en graf är en yttre plan, en serie-parallell eller en Halin-graf .
Ansökningar
Caterpillar träd har använts i kemisk grafteori för att representera strukturen hos bensenoida kolvätemolekyler . I denna representation bildar man en larv där varje kant motsvarar en 6-kolring i molekylstrukturen, och två kanter infaller vid en hörn när motsvarande ringar tillhör en sekvens av ringar som är anslutna från ände till ände i strukturera. El-Basil (1987) skriver, "Det är fantastiskt att nästan alla grafer som spelade en viktig roll i det som nu kallas" kemisk grafteori "kan ha samband med larvträd." I detta sammanhang är larvträd också kända som benzenoidträd och Gutman -träd , efter Ivan Gutmans arbete i detta område.