Kaktus (teorie grafů)

V teorii grafů je „kaktus“ (někdy nazývaný strom kaktusu ) spojený graf , ve kterém jakékoli dva jednoduché cykly mají nanejvýš jeden společný vrchol. Ekvivalentně jakákoli hrana v takovém grafu patří maximálně do jednoho jednoduchého cyklu. Ekvivalentně (pro netriviální kaktus) je každý blok (maximální podgraf bez pantů ) hranou nebo cyklem.

Vlastnosti

Kaktusy jsou vnější rovinné grafy . Každý pseudostrom je kaktus.

Rodina grafů , ve kterých je každá komponenta kaktus , je uzavřena operacemi zabírání menší části grafu . Tuto rodinu grafů lze popsat zadáním jediného zakázaného moll , „kosočtverce“ se čtyřmi vrcholy, vytvořeného odstraněním hrany z úplného grafu K 4 [1] .

Algoritmy a aplikace

Některé problémy s umístěním objektů, které jsou NP-těžké pro obecné grafy, stejně jako některé jiné problémy s grafy, lze pro kaktusy vyřešit v polynomiálním čase [2] [3] .

Protože kaktusy jsou speciální případy vnějších rovinných grafů , mnoho kombinatorických optimalizačních problémů na grafech lze vyřešit v polynomiálním čase [4] .

Kaktusy představují elektrické obvody , které mají užitečné vlastnosti. Raná aplikace kaktusů byla spojena se zavedením operačních zesilovačů [5] [6] [7] .

Kaktusy byly také nedávno použity ve srovnávací genomice.jako prostředek k reprezentaci vztahů mezi různými genomy nebo částmi genomů [8] .

Pokud je kaktus připojen a každý jeho vrchol patří nejvýše dvěma blokům, nazývá se Decembrist [9] . Každý polyedrický graf má jako podgraf „decembristu“, který zahrnuje všechny vrcholy grafu, což je skutečnost, která hraje zásadní roli v Leightonově a Moitrově důkazu [10] , že jakýkoli polyedrický graf má chamtivé vložení .do euklidovské roviny , ve které jsou vrcholům přiřazeny souřadnice, takže chamtivý referenční algoritmususpěje při odesílání zpráv mezi všemi dvojicemi vrcholů [11] .

Historie

Kaktusy byly poprvé studovány pod názvem Husimi trees , který jim dali Frank Harari a George Eugene Uhlenbeck na počest japonského fyzika, který s těmito grafy pracoval, zahraničního člena Ruské akademie věd [12] Koji Fushimi[13] [14] (v ruskojazyčné literatuře o grafech se příjmení přepisuje jako Husimi [15] [16] ). Stejný článek používá název „kaktus“ pro grafy tohoto typu, ve kterých je jakýkoli cyklus trojúhelník, ale nyní jsou povoleny cykly libovolné délky.

Mezitím se název Husimi strom začal používat pro grafy, ve kterých je každý blok úplným grafem . Tento název se jen málo podobá Husimiho práci a pro grafy v této rodině se nyní používá vhodnější výraz " blokový graf " a méně často se používá výraz Husimi strom .

Poznámky

  1. ↑ El-Mallah, Colbourn, 1988 , s. 354–362.
  2. ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , str. 693–703.
  3. ↑ Zmazek, Žerovník, 2005 , str. 536–541.
  4. ↑ Korneenko, 1984 , str. 215–217.
  5. ↑ Nishi, Chua [2], 1986 , str. 398–405.
  6. ↑ Nishi, Chua [1], 1986 , str. 381–397.
  7. ↑ Nishi, 1991 , str. 766–769.
  8. ↑ Paten, Diekhans a kol., 2010 , str. 410–425.
  9. ↑ Decembrist – oblíbený pokojový druh kaktusu
  10. ↑ Leighton, Moitra, 2010 .
  11. ↑ Leighton, Moitra, 2010 , str. 686–705.
  12. ↑ Fushimi Koji. | JE ARAN . Získáno 1. července 2022. Archivováno z originálu dne 4. června 2021.
  13. ↑ Harary, Uhlenbeck, 1953 , str. 315–322.
  14. ↑ Husimi, 1950 , str. 682–684.
  15. ↑ K. A. Zaretsky, „Na stromech Husimi“, Matem. poznámky, 9:3 (1971), 253–262; Matematika. Notes, 9:3 (1971), 150-154 . Získáno 27. srpna 2020. Archivováno z originálu dne 4. června 2021.
  16. ↑ Rasin O. V. Algorithm for checking isomorphism of Husimi trees / O. V. Rasin // News of the Ural State University. - 2004. - č. 30. - S. 126-136 . Získáno 27. srpna 2020. Archivováno z originálu dne 4. června 2021.

Literatura

Odkazy