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
- ↑ El-Mallah, Colbourn, 1988 , s. 354–362.
- ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , str. 693–703.
- ↑ Zmazek, Žerovník, 2005 , str. 536–541.
- ↑ Korneenko, 1984 , str. 215–217.
- ↑ Nishi, Chua [2], 1986 , str. 398–405.
- ↑ Nishi, Chua [1], 1986 , str. 381–397.
- ↑ Nishi, 1991 , str. 766–769.
- ↑ Paten, Diekhans a kol., 2010 , str. 410–425.
- ↑ Decembrist – oblíbený pokojový druh kaktusu
- ↑ Leighton, Moitra, 2010 .
- ↑ Leighton, Moitra, 2010 , str. 686–705.
- ↑ Fushimi Koji. | JE ARAN . Získáno 1. července 2022. Archivováno z originálu dne 4. června 2021. (neurčitý)
- ↑ Harary, Uhlenbeck, 1953 , str. 315–322.
- ↑ Husimi, 1950 , str. 682–684.
- ↑ 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. (neurčitý)
- ↑ 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. (neurčitý)
Literatura
- Ehab El-Mallah, Charles J. Colbourn. Složitost některých problémů s odstraněním okrajů // IEEE Transactions on Circuits and Systems. - 1988. - T. 35 , no. 3 . — S. 354–362 . - doi : 10.1109/31.1748 .
- Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. Algoritmy a výpočty, 16th Int. Symp., ISAAC 2005. - Springer-Verlag, 2005. - Vol. 3827. - S. 693-703. — ( Poznámky k přednáškám z informatiky ). - doi : 10.1007/11602613_70 .
- Blaz Zmazek, Janez Zerovnik. Devátá mezinárodní konference o vizualizaci informací (IV'05). - 2005. - S. 536-541. — ISBN 0-7695-2397-8 . - doi : 10.1109/IV.2005.48 .
- N.M. Korneenko. Kombinatorické algoritmy na třídě grafů // Proceedings of the National Academy of Sciences of Belarus SÉRIE FYZIKÁLNÍCH A TECHNICKÝCH VĚD. - 1984. - Vydání. 3 . - S. 109-111 .
- Tetsuo Nishi, Leon O. Chua. Topologický důkaz Nielsen-Willsonovy věty // IEEE Transactions on Circuits and Systems. - 1986. - T. 33 , no. 4 . — S. 398–405 . - doi : 10.1109/TCS.1986.1085935 .
- Tetsuo Nishi, Leon O. Chua. Jedinečnost řešení pro nelineární odporové obvody obsahující CCCS nebo VCVS, jejichž řídící koeficienty jsou konečné // IEEE Transactions on Circuits and Systems. - 1986. - T. 33 , no. 4 . — S. 381–397 . - doi : 10.1109/TCS.1986.1085934 .
- Tetsuo Nishi. Sborník příspěvků z IEEE International Symposium on Circuits and Systems, Singapur. - 1991. - S. 766-769.
- Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh, David Haussler. Výzkum v počítačové molekulární biologii // Poznámky k přednáškám z informatiky. - 2010. - T. 6044 . — S. 410–425 . - ISBN 978-3-642-12682-6 . - doi : 10.1007/978-3-642-12683-3_27 .
- Tom Leighton, Ankur Moitra. Některé výsledky o nenasytném vkládání do metrických prostorů // Diskrétní a výpočetní geometrie . - 2010. - T. 44 , č. 3 . — S. 686–705 . - doi : 10.1007/s00454-009-9227-6 .
- Frank Harary, George E. Uhlenbeck. O počtu stromů Husimi, I // Proceedings of the National Academy of Sciences . - 1953. - T. 39 , čís. 4 . — S. 315–322 . - doi : 10.1073/pnas.39.4.315 .
- Kodi Husimi. Poznámka k Mayersově teorii shlukových integrálů // Journal of Chemical Physics. - 1950. - T. 18 , čís. 5 . — S. 682–684 . - doi : 10.1063/1.1747725 .
Odkazy