A matematika, azon belül a gráfelmélet területén egy kaktuszgráf (cactus) (néha kaktuszfa – cactus tree) olyan összefüggő gráf, melynek bármely két körének legfeljebb egy közös csúcsa van. Ezzel egyenértékű definíció szerint olyan összefüggő gráf, melynek minden éle legfeljebb egy egyszerű körhöz tartozik, vagy (nemtriviális kaktuszoknál) melyek minden blokkja (kétszeresen összefüggő komponense) él vagy kör.
Tulajdonságok A kaktuszok külsíkgráfok. Minden pszeudofa kaktusz. Egy nemtriviális gráf pontosan akkor kaktusz, ha minden kétszeresen összefüggő komponense vagy él, vagy egyszerű kör. Azon gráfok családja, melyek minden összefüggő komponense kaktuszgráf, a gráfminorképzés műveletére nézve zárt. A család egyetlen tiltott minorával meghatározható, ez a K4 teljes gráfból egyetlen él eltávolításával kapott gyémántgráf.
Háromszögű kaktusz A háromszögű kaktuszgráfok olyan speciális kaktuszok, melyek minden köre három hosszúságú. Ezek a kaktuszgráfok egyben blokkgráfok is. A legnagyobb háromszögű kaktuszt tetszőleges gráfban polinom időben meg lehet keresni matroidparitás-probléma egy algoritmusa segítségével. Mivel a háromszögű kaktuszok síkba rajzolhatók, a legnagyobb háromszögű kaktusz felhasználható a legnagyobb síkbarajzolható részgráf keresésekor, ami a planarizáció fontos részproblémája. Approximációs algoritmusként az elért approximációs arány 4/9, ami a legnagyobb síkbarajzolható részgráf problémájánál ismert legjobb arány.
Algoritmusok és alkalmazások
Néhány probléma, köztük létesítmény-elhelyezési problémák, melyek általános gráfokon NP-nehéz bonyolultságúak, kaktuszgráfokon polinom időben megoldhatók. Mivel a kaktuszok a külsíkgráfok speciális esetei, egyes kombinatorikus optimalizálási problémák polinom időben megoldhatók rajtuk. Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 A kaktuszok által reprezentált elektromos áramkörök hasznos tulajdonságokkal rendelkeznek. A kaktuszok egyik korai alkalmazása a műveleti erősítők ábrázolásában volt. A kaktuszokat az összehasonlító genomikában a különböző genomok vagy genomrészek közötti kapcsolatok ábrázolására használják. Ha egy kaktuszgráf összefüggő, és minden csúcsa legfeljebb két blokkhoz tartozik, akkor karácsonyi kaktusznak nevezik. Minden poliédergráfban található olyan karácsonyi kaktusz részgráf, ami az összes csúcsot tartalmazza; ez a tény jelentős szerepet kapott bizonyításában, miszerint minden poliédergráfnak van az euklideszi síkba történő mohó beágyazása.. A topologikus gráfelméletben azok a gráfok, melyek celluláris beágyazásai mind síkbarajzolhatók a kaktuszgráfoknak pontosan azzal a részhalmazával egyezik meg, melyekben minden csúcs legfeljebb egy körhöz tartozik. Ezeknek a gráfoknak két tiltott minoruk van, a gyémántgráf és az öt csúcsú barátsággráf (pillangó).
Történet A kaktuszgráfokat Husimi-fák néven tanulmányozta Frank Harary és George Uhlenbeck, Kôdi Husimi korábbi, megegyező témájú munkái előtt tisztelegve. Ugyanebben a Harary–Uhlenbeck-cikkben még csak azokat a gráfokat nevezte közülük kaktusznak, melyek minden köre háromszög volt, a jelenleg elterjedt definíció tetszőleges hosszúságú köröket megenged. Eközben a Husimi-fa kifejezést elkezdték azokra a gráfokra alkalmazni, melyek minden blokkja teljes gráf; az összekeverhetőség elkerülése érdekében azokra a blokkgráf, a Husimi-fákra inkább a kaktuszgráf kifejezést kezdték használni.Lásd pl. , Robert E. Jamison egy 1983-as értékelését egy másik cikkről, ami a blokkgráfokat Husimi-fáknak nevezi; Jamison a hibát Mehdi Behzad és Gary Chartrand könyvének tulajdonítja.
Fordítás
Jegyzetek
További információk Application of Cactus Graphs in Analysis and Design of Electronic Circuits
Kategória:Gráfcsaládok Kategória:Síkgráfok