Hernyógráf

Egy hernyó

Nem tévesztendő össze a következővel: Hernyó.

A gráfelmélet területén a hernyó (hernyógráf, hernyófa) olyan fa, melynek az összes csúcsa egy központi úttól legfeljebb egy él távolságra található.

A hernyókat először Harary és Schwenk tanulmányozták egy cikksorozatban. A név A. Hobbs leleménye.^[1][2] (Harary & Schwenk 1973) színes leírása szerint, „a hernyó olyan fa, ami metamorfózisa során úttá alakul át, ha a végpontgubóit eltávolítják.”^[1]

Ekvivalens karakterizációk

A következő karakterizációk mind jellemzik a hernyófákat:

• Olyan fák, melyek leveleit és az azokból kiinduló éleket eltávolítva útgráfot kapunk.^[2][3]
• Olyan fák, melyekben létezik minden 2 vagy magasabb fokszámú csúcsot tartalmazó út.
• Olyan fák, melyben minden legalább 3 fokszámú csúcsnak van legalább két olyan szomszédja, ami nem levél.
• Olyan fák, melyek nem tartalmazzák részgráfként a K_1,3 csillaggráf (karom) éleinek 2 hosszú útra cserélésével kapott gráfot.^[3]
• Olyan összefüggő gráfok, melyek lerajzolhatók úgy, hogy csúcsaik két párhuzamos egyenesen vannak, az élek pedig egymást nem metsző szakaszok, melyek végpontja valamelyik egyenesen van.^[3][4]
• Olyan fák, melyek négyzete Hamilton-féle. Tehát egy hernyóban létezik a csúcsok olyan körbeérő sorozata, melyben a sorozat szomszédos csúcsai 1 vagy 2 távolságra vannak egymástól; az olyan fákra, melyek nem hernyók, ez nem igaz. A sorozat előállítható például úgy, hogy a gráfot két párhuzamos egyenesre rajzoljuk föl, és az egyik egyenesen lévő csúcsok sorozatához hozzáfűzzük a másik egyenesen lévő csúcssorozat megfordítását.^[3]
• Olyan fák, melyek élgráfja Hamilton-utat tartalmaz; az út megkapható az említett két egyeneses felrajzolás éleinek rendezésével. Általánosabban, az élek száma, amit egy tetszőleges fa élgráfjához kell adni, hogy Hamilton-utat tartalmazzon (a Hamilton-kiegészítés mérete) megegyezik a fa közös élt nem tartalmazó hernyókra való „hernyófelbontásában” lévő hernyók minimális számával..^[5]
• Olyan összefüggő gráfok, melyekben az útszélesség 1.^[6]
• Összefüggő háromszögmentes intervallumgráfok.^[7]

Általánosítások

Egy k-fa olyan merev körű gráf, melynek pontosan n − k maximális klikkje van, melyek mindegyike k + 1 csúcsot tartalmaz; az olyan k-fában, ami maga nem (k + 1)-klikk, minden maximális klikk vagy szétválasztja a gráfot két vagy több komponensre, vagy egyetlen levelet tartalmaz, mely levélcsúcs az egyetlen maximális klikkhez tartozik. Egy k-út olyan k-fa, aminek legalább két levele van, egy k-hernyó pedig olyan k-fa, ami felbontható egy k-útra és valahány k-levélre, melyek mindegyike szomszédos a k-út elvágó csúcshalmaz k-klikkjével. Ezt a terminológiát követve az 1-hernyó megegyezik a hernyógráffal, a k-hernyók pedig a k útszélességű élmaximális gráfok.^[6]

Egy homár vagy homárgráf (lobster) olyan fa, melynek minden csúcsa legfeljebb 2 él távolságra van egy központi úttól.^[8] Ez eggyel több, mint a hernyó esetében.

Leszámlálás

A hernyógráfok a gráfleszámlálási problémák azon ritka esetei közé tartoznak, melyekhez precíz képlet rendelhető: ha n ≥ 3, az n címkézetlen csúccsal rendelkező hernyók száma:^[1]

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Az n csúcsú hernyók száma n = 1, 2, 3, …-ra:

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (A005418 sorozat az OEIS-ben).

Számítási bonyolultság

Egy gráf feszítő hernyójának megtalálása (Spanning Caterpillar Problem) NP-teljes. Ezzel összefüggő optimalizációs probléma a minimális feszítő hernyó megtalálása (Minimum Spanning Caterpillar Problem, MSCP), ahol egy gráf élei duális költséggel rendelkeznek (levél- vagy út-költség) és a cél olyan hernyó megtalálása, ami kifeszíti a bemeneti gráfot és a lehető legalacsonyabb költséggel rendelkezik. Itt a hernyó költsége alatt az élek költségeinek összegét értjük, ahol minden élhez két külön költségérték tartozik, attól függően, hogy levél él vagy belső él. Nem létezik f(n)-approximációs algoritmus az MSCP megoldására, hacsak nem igaz, hogy P = NP. Itt f(n) alatt bármely polinom időben számítható függvényét értjük n-nek, a gráf csúcsszámának.^[9]

Létezik parametrizált algoritmus az MSCP optimális megoldására korlátozott favastagságú gráfokban. Mind a Spanning Caterpillar Problem, mind az MSCP megoldására léteznek lineáris idejű algoritmusok, ha a gráf külsíkgráf, soros-párhuzamos gráf vagy Halin-gráf.^[9]

Alkalmazásai

A hernyógráfokat a kémiai gráfelméletben a benzolszerű szénhidrogén-molekulák szerkezetének ábrázolására használják. Ebben a reprezentációban a hernyó minden éle a molekuláris szerkezet egy 6 szénláncú gyűrűjének felel meg, két él akkor találkozik egy csúcsban, ha a megfelelő két gyűrű összekapcsolódik a struktúrákban. (El-Basil 1987) írja: „Csodálatos, hogy szinte minden gráfnak, ami fontos szerepet kapott abban, amit most »kémiai gráfelméletnek« nevezünk, köze lehet a hernyógráfokhoz”. Ebben a kontextusban a hernyógráfokat benzenoid fáknak és Gutman-fáknak is nevezik, Ivan Gutman munkássága nyomán.^[2][10][11]

Jegyzetek

1. Harary, Frank & Schwenk, Allen J. (1973), "The number of caterpillars", Discrete Mathematics 6 (4): 359–365, DOI 10.1016/0012-365x(73)90067-8.
2. El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry 1 (2): 153–174, DOI 10.1007/BF01205666.
3. Harary, Frank & Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika 18: 138–140, DOI 10.1112/S0025579300008494.
4. Harary, Frank & Schwenk, Allen J. (1972), "A new crossing number for bipartite graphs", Utilitas Math. 1: 203–209.
5. Raychaudhuri, Arundhati (1995), "The total interval number of a tree and the Hamiltonian completion number of its line graph", Information Processing Letters 56 (6): 299–306, DOI 10.1016/0020-0190(95)00163-8.
6. Proskurowski, Andrzej & Telle, Jan Arne (1999), "Classes of graphs with restricted interval models", Discrete Mathematics and Theoretical Computer Science 3: 167–176, <http://www.emis.ams.org/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf>. Hozzáférés ideje: 2016-06-11 Archivált másolat. [2011. június 6-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. június 11.).
7. Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory 17 (1): 117–127, DOI 10.1002/jgt.3190170112.
8. Weisstein, Eric W.: Lobster (angol nyelven). Wolfram MathWorld
9. Khosravani, Masoud (2011), Searching for optimal caterpillars in general and bounded treewidth graphs, University of Auckland, <https://researchspace.auckland.ac.nz/handle/2292/8360?show=full>
10. Gutman, Ivan (1977), "Topological properties of benzenoid systems", Theoretica Chimica Acta 45 (4): 309–315, DOI 10.1007/BF00554539.
11. El-Basil, Sherif (1990), "Caterpillar (Gutman) trees in chemical graph theory", in Gutman, I. & Cyvin, S. J., Advances in the Theory of Benzenoid Hydrocarbons, vol. 153, Topics in Current Chemistry, pp. 273–289, DOI 10.1007/3-540-51505-4_28.

További információk

• Weisstein, Eric W.: Caterpillar (angol nyelven). Wolfram MathWorld