Kaktusz (gráfelmélet)

A gráfelméletben a "kaktusz" (néha kaktuszfának is nevezik ) olyan összefüggő gráf , amelyben bármely két egyszerű ciklusnak legfeljebb egy közös csúcsa van. Ezzel egyenértékűen egy ilyen gráf bármely éle legfeljebb egy egyszerű ciklushoz tartozik. Ezzel egyenértékűen (egy nem triviális kaktusz esetében) bármely blokk (maximális részgráf csukló nélkül ) él vagy ciklus.

Tulajdonságok

A kaktuszok külső síkbeli grafikonok . Minden álfa kaktusz.

Az a gráfcsalád, amelyben minden komponens egy-egy kaktusz , a gráf molljának felvételével zárul . Ezt a gráfcsaládot úgy írhatjuk le, hogy megadjuk az egyetlen tiltott minort , egy négy csúcsú "gyémántot" , amely a K 4 teljes gráf élének eltávolításával jön létre [1] .

Algoritmusok és alkalmazások

Egyes objektum-elhelyezési problémák, amelyek általános gráfoknál NP- nehézek, mint néhány más gráffeladat, polinomiális időben megoldhatók kaktuszok esetében [2] [3] .

Mivel a kaktuszok a külső síkbeli gráfok speciális esetei , sok kombinatorikus optimalizálási probléma a gráfokon megoldható polinomiális időben [4] .

A kaktuszok olyan elektromos áramköröket képviselnek , amelyek hasznos tulajdonságokkal rendelkeznek. A kaktuszok korai alkalmazása a műveleti erősítők [5] [6] [7] bevezetésével függött össze .

A kaktuszok a közelmúltban az összehasonlító genomikában is használatosak.a különböző genomok vagy genomrészek közötti kapcsolatok ábrázolásának eszközeként [8] .

Ha egy kaktusz össze van kötve, és minden csúcsa legfeljebb két blokkhoz tartozik, akkor dekabristának nevezzük [9] . Minden poliéder gráf algráfja egy "decembrist", amely tartalmazza a gráf összes csúcsát, ez a tény lényeges szerepet játszik Leighton és Moitra bizonyításában [10] , hogy minden poliéder gráfban van mohó beágyazás .az euklideszi síkra , amelyben a csúcsokhoz koordinátákat rendelünk, így a mohó hivatkozási algoritmussikerül üzenetet küldeni az összes csúcspár között [11] .

Történelem

A kaktuszt először Husimi fák néven tanulmányozták, amelyet Frank Harari és George Eugene Uhlenbeck adott nekik az ezekkel a grafikonokkal dolgozó japán fizikus, az Orosz Tudományos Akadémia külföldi tagja [ 12] Koji Fushimi tiszteletére.[13] [14] (a gráfokkal foglalkozó orosz nyelvű irodalomban a vezetéknevet Husimi-ként írják át [15] [16] ). Ugyanez a cikk a "kaktusz" nevet használja az ilyen típusú gráfokhoz, amelyekben bármely ciklus háromszög, de mostantól bármilyen hosszúságú ciklus megengedett.

Eközben a Husimi fa nevet kezdték használni olyan gráfokhoz, amelyekben minden blokk egy teljes gráf . Ez a név kevéssé hasonlít Husimi munkásságára, és a megfelelőbb "blokkgráf " kifejezést ma már ebben a családban használják a gráfokra, a Husimi-fa kifejezést pedig ritkábban használják.

Jegyzetek

  1. ↑ El-Mallah, Colbourn, 1988 , p. 354–362.
  2. ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , p. 693–703.
  3. ↑ Zmazek, Zerovnik, 2005 , p. 536–541.
  4. ↑ Korneenko, 1984 , p. 215–217.
  5. ↑ Nishi, Chua [2], 1986 , p. 398–405.
  6. ↑ Nishi, Chua [1], 1986 , p. 381–397.
  7. ↑ Nishi, 1991 , p. 766–769.
  8. ↑ Paten, Diekhans et al., 2010 , p. 410–425.
  9. ↑ Decembrist - egy népszerű beltéri kaktuszfajta
  10. ↑ Leighton, Moitra, 2010 .
  11. ↑ Leighton, Moitra, 2010 , p. 686–705.
  12. ↑ Fushimi Koji. | IS ARAN . Letöltve: 2022. július 1. Az eredetiből archiválva : 2021. június 4.
  13. ↑ Harary, Uhlenbeck, 1953 , p. 315–322.
  14. ↑ Husimi, 1950 , p. 682–684.
  15. ↑ K. A. Zaretsky, „On Husimi trees”, Matem. jegyzetek, 9:3 (1971), 253–262; Math. Jegyzetek, 9:3 (1971), 150–154 . Letöltve: 2020. augusztus 27. Az eredetiből archiválva : 2021. június 4.
  16. ↑ Rasin O. V. Algoritmus a Husimi fák izomorfizmusának ellenőrzésére / O. V. Rasin // Az Uráli Állami Egyetem hírei. - 2004. - 30. sz. - S. 126-136 . Letöltve: 2020. augusztus 27. Az eredetiből archiválva : 2021. június 4.

Irodalom

Linkek