Caterpillar (grafteori)

En larve eller larvetræ  er et træ , hvor alle toppunkter er i en afstand på højst 1 fra den centrale sti.

Caterpillar-grafer blev først studeret i en række artikler af Harari og Schwenk. Navnet blev foreslået af Arthur Hobbs [1] [2] . Som Harari og Schwenk [3] veltalende skrev : "En larve er et træ, der bliver til en sti, hvis kokonen fjernes fra de terminale hjørner" [1] .

Tilsvarende beskrivelser

Følgende karakteristika beskriver larvegrafer:

• Det er træer, hvor man fjerner blade sammen med kanter giver en sti [2] [4] .
• Disse er træer, hvor der er en sti, der indeholder alle hjørner af grad to eller mere.
• Det er træer, hvor ethvert toppunkt af grad tre eller mere har højst to naboer, der ikke er blade.
• Det er træer, der ikke som undergrafer indeholder den graf, der er dannet ved at erstatte hver kant af stjernen K 1,3 med en bane med to kanter [4] .
• Disse er forbundne grafer, der kan tegnes ved at placere hjørnerne på to parallelle linjer med ikke-skærende kanter, og placere endespidserne af hver kant på forskellige linjer [4] [4] [5] .
• Disse er træer, hvis kvadrat er en Hamilton-graf . Et kvadrat betyder her eksistensen af ​​en cyklisk sekvens af alle knudepunkter, således at hvert par af tilstødende knudepunkter i sekvensen er et eller to fra hinanden. Træer, der ikke er larver, har ikke denne rækkefølge. En cyklus af denne art kan opnås ved at tegne en larve med spidser på to parallelle linjer. Derefter nummererer vi hjørnerne på den ene ret linje i den ene retning, og på den anden lige linje - i den modsatte retning [4] .
• Disse er træer, hvis linjegrafer indeholder en Hamiltonsk sti . Sådan en sti kan opnås ved at bestille kanterne i en larvetegning med to lige linjer. Mere generelt er antallet af kanter, der skal tilføjes til linjegrafen, for at et vilkårligt træ kan indeholde en Hamiltonsk sti (størrelsen af ​​dets Hamiltonske komplement ) lig med det mindste antal kantadskillende larver, som træet kan opdeles i. [6] .
• Disse er sammenhængende grafer med enhedsbanebredde [7] .
• Disse er sammenhængende intervalgrafer uden trekanter [8] .

Generaliseringer

Et K - træ er en akkordgraf, der indeholder præcis n − k maksimale kliker , som hver indeholder k + 1 hjørner. I et k - træ, som ikke i sig selv er en ( k + 1)-klik , opdeler hver maksimal klik enten grafen i to eller flere komponenter eller indeholder et ( k- )bladspids, der kun hører til én maksimal klike. En k -sti er et k -træ med højst to blade, og en k -larve er et k - træ, der kan opdeles i k -stier og flere k -blade, der hver støder op til k -klikens separator . - sti. I denne terminologi er en 1-larve det samme som en larvegraf, og k -larver er kantmaksimale grafer med stibredde k [ 7] .

En krabbe  er et træ , hvor alle toppunkter er i en afstand på ikke over 2 fra den centrale sti [9]

Optælling

Larver er et sjældent tilfælde af graftællingsproblemer , når den nøjagtige formel er kendt - hvis n  ≥ 3, er antallet af larver med n toppunkter [1] .

For n = 1, 2, 3, … er antallet af larver med n toppunkter

Beregningsmæssig kompleksitet

At finde en kontraherende larve er et NP-komplet problem . Det tilsvarende optimeringsproblem er minimum contraction caterpillar problem (MPCT), hvor priserne er angivet på kanterne, og målet er at finde en larve, der minimerer priserne. Her er prisen på en larve defineret som summen af ​​priserne på dens kanter, og hver kant har to priser, alt efter om det er et blad eller en indvendig kant. Der er ingen f(n) -tilnærmelsesalgoritme for SMSH , medmindre P = NP er opfyldt . Her er f(n) en hvilken som helst funktion af n beregnet i polynomisk tid, og n er antallet af grafens hjørnepunkter [10] .

Der er en parametriseret algoritme, der finder den optimale løsning til GSGM i en graf med en afgrænset træbredde . Således har både det kontraherende larveproblem og det minimalt kontraherende larveproblem lineære tidsalgoritmer, hvis grafen er outerplanar , parallel-sekventiel eller Halins graf [10] .

Ansøgninger

Larver bruges i kemisk grafteori til at repræsentere benzenoidkulbrinters molekylære struktur . I denne fremstilling danner molekylerne larver, hvor hver kant svarer til en ring med 6 carbonatomer, og to kanter falder ind i et toppunkt, hvis de tilsvarende benzenringe tilhører en sekvens af lineært forbundne ringe. El-Bazil skriver: "Det er overraskende, at næsten alle de grafer, der spiller en vigtig rolle i det, der nu kaldes "kemisk grafteori", er forbundet med larvegrafer." I denne sammenhæng er larvegrafer også kendt som benzoidtræer eller Gutmanntræer , efter Ivan Gutmans arbejde på dette område [2] [11] [12] .

Noter

1. ↑ 1 2 3 Harary, Schwenk, 1973 , s. 359-365.
2. ↑ 1 2 3 El-Basil, 1987 , s. 153-174.
3. ↑ Harary, Schwenk, 1973 .
4. ↑ 1 2 3 4 5 Harary, Schwenk, 1971 , s. 138-140.
5. ↑ Harary, Schwenk, 1972 , s. 203-209.
6. ↑ Raychaudhuri, 1995 , s. 299-306.
7. ↑ 1 2 Proskurowski, Telle, 1999 , s. 167-176.
8. ↑ Eckhoff, 1993 , s. 117-127.
9. ↑ Weisstein, Eric W. Lobster  på Wolfram MathWorld- webstedet .
10. ↑ 12 Khosravani , 2011 .
11. ↑ Gutman, 1977 , s. 309-315.
12. ↑ El-Basil, 1990 , s. 273-289.

Litteratur

• Masoud Khosravani. Søger efter optimale larver generelt og grafer med afgrænset træbredde // Ph.D. - University of Auckland, 2011.
• Sherif El Basil. Anvendelser af larvetræer i kemi og fysik // Journal of Mathematical Chemistry. - 1987. - Bind 1 , udgave. 2 . — S. 153–174 . - doi : 10.1007/BF01205666 .
• Ivan Gutman. Benzenoidsystemers topologiske egenskaber // Theoretica Chimica Acta. - 1977. - T. 45 , no. 4 . — S. 309–315 . - doi : 10.1007/BF00554539 .
• Sherif El Basil. Fremskridt i teorien om benzenoide kulbrinter / I. Gutman, SJ Cyvin. - 1990. - T. 153. - S. 273-289. - (Emner i aktuel kemi). - doi : 10.1007/3-540-51505-4_28 .
• Andrzej Proskurowski, Jan Arne Telle. Klasser af grafer med begrænsede intervalmodeller // Diskret matematik og teoretisk datalogi. - 1999. - T. 3 . — S. 167–176 .
• Arundhati Raychaudhuri. Det samlede intervalnummer for et træ og det Hamiltonske fuldførelsesnummer for dets linjegraf // Information Processing Letters . - 1995. - T. 56 , no. 6 . — S. 299–306 . - doi : 10.1016/0020-0190(95)00163-8 .
• Jürgen Eckhoff. Ekstreme intervalgrafer  // Journal of Graph Theory. - 1993. - T. 17 , no. 1 . — S. 117–127 . - doi : 10.1002/jgt.3190170112 .
• Frank Harary , Allen J. Schwenk. Træer med Hamiltonsk firkant // Mathematika. - 1971. - T. 18 . — S. 138–140 . - doi : 10.1112/S0025579300008494 .
• Frank Harary , Allen J. Schwenk. Et nyt krydsningsnummer for todelte grafer // Utilitas Math .. - 1972. - T. 1 . — S. 203–209 .
• Frank Harary , Allen J. Schwenk. Antallet af larver // Diskret matematik. - 1973. - T. 6 , no. 4 . — S. 359–365 . - doi : 10.1016/0012-365x(73)90067-8 .

Links

• Weisstein, Eric W. Caterpillar  (engelsk) på Wolfram MathWorld- webstedet .