Kaktus (grafteori)

I grafteorin är en "kaktus" (kallas ibland ett kaktusträd ) en sammankopplad graf där två enkla cykler som mest har en gemensam vertex. På motsvarande sätt hör vilken kant som helst i en sådan graf till högst en enkel cykel. På motsvarande sätt (för en icke-trivial kaktus) är varje block (maximalt subgraf utan gångjärn ) en kant eller en cykel.

Egenskaper

Kaktusar är ytterplanära grafer . Alla pseudoträd är en kaktus.

Familjen av grafer där varje komponent är en kaktus stängs under operationerna att ta den mindre av grafen . Denna familj av grafer kan beskrivas genom att specificera den enda förbjudna moll , en "diamant" med fyra hörn, bildad genom att ta bort en kant från hela grafen K 4 [1] .

Algoritmer och applikationer

Vissa objektplaceringsproblem som är NP-hårda för generella grafer, liksom vissa andra grafproblem, kan lösas i polynomtid för kaktusar [2] [3] .

Eftersom kaktusar är specialfall av ytterplanära grafer kan många kombinatoriska optimeringsproblem på grafer lösas i polynomtid [4] .

Kaktusar representerar elektriska kretsar som har användbara egenskaper. En tidig applicering av kaktusar förknippades med introduktionen av operationsförstärkare [5] [6] [7] .

Kaktusar har också nyligen använts i jämförande genomik.som ett sätt att representera relationer mellan olika genom eller delar av genom [8] .

Om en kaktus är sammankopplad och var och en av dess hörn tillhör högst två block, kallas den en Decembrist [9] . Varje polyedrisk graf har som subgraf en "decembrist" som inkluderar alla hörn i grafen, ett faktum som spelar en väsentlig roll i Leighton och Moitras bevis [10] att vilken polyedrisk graf som helst har en girig inbäddningin i det euklidiska planet , där koordinater tilldelas hörnen så att den giriga hänvisningsalgoritmenlyckas skicka meddelanden mellan alla par av hörn [11] .

Historik

Kaktusar studerades först under namnet Husimi-träd , som gavs till dem av Frank Harari och George Eugene Uhlenbeck för att hedra den japanska fysikern som arbetade med dessa grafer, en utländsk medlem av Ryska vetenskapsakademin [12] Koji Fushimi[13] [14] (i den ryskspråkiga litteraturen om grafer är efternamnet transkriberat som Husimi [15] [16] ). Samma artikel använder namnet "kaktus" för grafer av denna typ, där vilken cykel som helst är en triangel, men cykler av vilken längd som helst är nu tillåtna.

Under tiden började namnet Husimi-trädet användas för grafer där varje block är en komplett graf . Detta namn påminner inte mycket om Husimis verk, och den mer passande termen " blockgraf " används nu för grafer i denna familj, och termen Husimi-träd används mer sällan.

Anteckningar

  1. ↑ El-Mallah, Colbourn, 1988 , sid. 354–362.
  2. ↑ Ben-Moshe, Bhattacharya, Shi, 2005 , sid. 693–703.
  3. ↑ Zmazek, Zerovik, 2005 , sid. 536–541.
  4. ↑ Korneenko, 1984 , sid. 215–217.
  5. ↑ Nishi, Chua [2], 1986 , sid. 398–405.
  6. ↑ Nishi, Chua [1], 1986 , sid. 381–397.
  7. ↑ Nishi, 1991 , sid. 766–769.
  8. ↑ Paten, Diekhans et al., 2010 , sid. 410–425.
  9. ↑ Decembrist - en populär inomhustyp av kaktus
  10. ↑ Leighton, Moitra, 2010 .
  11. ↑ Leighton, Moitra, 2010 , sid. 686–705.
  12. ↑ Fushimi Koji. | ÄR ARAN . Hämtad 1 juli 2022. Arkiverad från originalet 4 juni 2021.
  13. ↑ Harary, Uhlenbeck, 1953 , sid. 315–322.
  14. ↑ Husimi, 1950 , sid. 682–684.
  15. ↑ K. A. Zaretsky, "Om Husimi-träd", Matem. notes, 9:3 (1971), 253-262; Matematik. Notes, 9:3 (1971), 150-154 . Hämtad 27 augusti 2020. Arkiverad från originalet 4 juni 2021.
  16. ↑ Rasin O. V. Algoritm för att kontrollera isomorfismen hos Husimi-träd / O. V. Rasin // Nyheter från Ural State University. - 2004. - Nr 30. - S. 126-136 . Hämtad 27 augusti 2020. Arkiverad från originalet 4 juni 2021.

Litteratur

Länkar