thumb|300px|Egy 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. 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.”.
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. 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 K1,3 csillaggráf (karom) éleinek 2 hosszú útra cserélésével kapott gráfot. 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.. 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.. 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... Olyan összefüggő gráfok, melyekben az útszélesség 1. Összefüggő háromszögmentes intervallumgráfok..
Általánosítások Egy k-fa olyan merev körű gráf, melynek pontosan maximális klikkje van, melyek mindegyike csúcsot tartalmaz; az olyan k-fában, ami maga nem , 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. .
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. 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:
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, ... .
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.
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.
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. í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....
Jegyzetek
További információk
Kategória:Fák (gráfelmélet) Kategória:Matematikai kémia