Kaktus (grafteori)
I grafteori er en "kaktus" (nogle gange kaldet et kaktustræ ) en sammenhængende graf , hvor to simple cyklusser højst har et fælles toppunkt. Tilsvarende hører enhver kant i en sådan graf til højst én simpel cyklus. Tilsvarende (for en ikke-triviel kaktus) er enhver blok (maksimal subgraf uden hængsler ) en kant eller en cyklus.
Egenskaber
Kaktusser er ydre planære grafer . Ethvert pseudotræ er en kaktus.
Familien af grafer, hvor hver komponent er en kaktus, er lukket under operationerne med at tage den mindre af grafen . Denne familie af grafer kan beskrives ved at specificere den eneste forbudte mol , en "ruber" med fire hjørner, dannet ved at fjerne en kant fra hele grafen K 4 [1] .
Algoritmer og applikationer
Nogle objektplaceringsproblemer, der er NP-hårde for generelle grafer, kan ligesom nogle andre grafproblemer løses i polynomisk tid for kaktus [2] [3] .
Fordi kaktusser er specielle tilfælde af ydreplanære grafer , kan mange kombinatoriske optimeringsproblemer på grafer løses i polynomisk tid [4] .
Kaktusser repræsenterer elektriske kredsløb , der har nyttige egenskaber. En tidlig anvendelse af kaktusser var forbundet med introduktionen af operationsforstærkere [5] [6] [7] .
Kaktusser er også for nylig blevet brugt i komparativ genomik.som et middel til at repræsentere forhold mellem forskellige genomer eller dele af genomer [8] .
Hvis en kaktus er forbundet, og hver af dens hjørner ikke tilhører mere end to blokke, kaldes den en Decembrist [9] . Enhver polyedrisk graf har som en undergraf en "decembrist", der inkluderer alle hjørnerne af grafen, et faktum, der spiller en væsentlig rolle i Leighton og Moitras bevis [10] på, at enhver polyhedral graf har en grådig indlejringind i det euklidiske plan , hvor koordinater er tildelt til hjørnerne, således at den grådige henvisningsalgoritmelykkes med at sende beskeder mellem alle par af hjørner [11] .
Historie
Kaktusser blev først studeret under navnet Husimi-træer , givet til dem af Frank Harari og George Eugene Uhlenbeck til ære for den japanske fysiker, der arbejdede med disse grafer, et udenlandsk medlem af det russiske videnskabsakademi [12] Koji Fushimi[13] [14] (i den russisksprogede litteratur om grafer er efternavnet transskriberet som Husimi [15] [16] ). Den samme artikel bruger navnet "kaktus" til grafer af denne type, hvor enhver cyklus er en trekant, men cyklusser af enhver længde er nu tilladt.
I mellemtiden begyndte navnet Husimi-træet at blive brugt til grafer, hvor hver blok er en komplet graf . Dette navn minder ikke meget om Husimis arbejde, og det mere passende udtryk "blokgraf " bruges nu om grafer i denne familie, og udtrykket Husimi-træ bruges sjældnere.
Noter
- ↑ El-Mallah, Colbourn, 1988 , s. 354-362.
- ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , s. 693-703.
- ↑ Zmazek, Zerovik, 2005 , s. 536-541.
- ↑ Korneenko, 1984 , s. 215-217.
- ↑ Nishi, Chua [2], 1986 , s. 398-405.
- ↑ Nishi, Chua [1], 1986 , s. 381-397.
- ↑ Nishi, 1991 , s. 766-769.
- ↑ Paten, Diekhans et al., 2010 , s. 410-425.
- ↑ Decembrist - en populær indendørs type kaktus
- ↑ Leighton, Moitra, 2010 .
- ↑ Leighton, Moitra, 2010 , s. 686-705.
- ↑ Fushimi Koji. | ER ARAN . Hentet 1. juli 2022. Arkiveret fra originalen 4. juni 2021. (ubestemt)
- ↑ Harary, Uhlenbeck, 1953 , s. 315-322.
- ↑ Husimi, 1950 , s. 682-684.
- ↑ K. A. Zaretsky, "Om Husimi-træer", Matem. notes, 9:3 (1971), 253-262; Matematik. Notes, 9:3 (1971), 150-154 . Hentet 27. august 2020. Arkiveret fra originalen 4. juni 2021. (ubestemt)
- ↑ Rasin O. V. Algoritme til kontrol af isomorfi af Husimi-træer / O. V. Rasin // Nyheder fra Ural State University. - 2004. - Nr. 30. - S. 126-136 . Hentet 27. august 2020. Arkiveret fra originalen 4. juni 2021. (ubestemt)
Litteratur
- Ehab El-Mallah, Charles J. Colbourn. Kompleksiteten af nogle problemer med kantsletning // IEEE-transaktioner på kredsløb og systemer. - 1988. - T. 35 , no. 3 . — S. 354–362 . - doi : 10.1109/31.1748 .
- Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. Algoritmer og beregninger, 16. Int. Symp., ISAAC 2005. - Springer-Verlag, 2005. - Vol. 3827. - S. 693-703. — ( Forelæsningsnotater i Datalogi ). - doi : 10.1007/11602613_70 .
- Blaz Zmazek, Janez Zerovnik. Niende internationale konference om informationsvisualisering (IV'05). - 2005. - S. 536-541. — ISBN 0-7695-2397-8 . - doi : 10.1109/IV.2005.48 .
- N.M. Korneenko. Kombinatoriske algoritmer på klassen af grafer // Proceedings of the National Academy of Sciences of Belarus SERIES OF FYSICAL AND TECHNICAL SCIENCES. - 1984. - Udgave. 3 . - S. 109-111 .
- Tetsuo Nishi, Leon O. Chua. Topologisk bevis på Nielsen-Willson-sætningen // IEEE-transaktioner på kredsløb og systemer. - 1986. - T. 33 , no. 4 . — S. 398–405 . - doi : 10.1109/TCS.1986.1085935 .
- Tetsuo Nishi, Leon O. Chua. Enestående løsning til ikke-lineære resistive kredsløb, der indeholder CCCS'er eller VCVS'er, hvis styringskoefficienter er endelige // IEEE-transaktioner på kredsløb og systemer. - 1986. - T. 33 , no. 4 . — S. 381–397 . - doi : 10.1109/TCS.1986.1085934 .
- Tetsuo Nishi. Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore. - 1991. - S. 766-769.
- Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh, David Haussler. Research in Computational Molecular Biology // Lecture Notes in Computer Science. - 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. Nogle resultater om grådige indlejringer i metriske rum // Diskret og beregningsgeometri . - 2010. - T. 44 , no. 3 . — S. 686–705 . - doi : 10.1007/s00454-009-9227-6 .
- Frank Harary, George E. Uhlenbeck. Om antallet af Husimi-træer, I // Proceedings of the National Academy of Sciences . - 1953. - T. 39 , no. 4 . — S. 315–322 . - doi : 10.1073/pnas.39.4.315 .
- Kodi Husimi. Notat om Mayers teori om klyngeintegraler // Journal of Chemical Physics. - 1950. - T. 18 , no. 5 . — S. 682–684 . - doi : 10.1063/1.1747725 .
Links