Kaktus graf - Cactus graph
I grafteori är en kaktus (ibland kallad ett kaktusträd ) en ansluten graf där två enkla cykler har högst en toppunkt gemensamt. På motsvarande sätt är det en ansluten graf där varje kant tillhör högst en enkel cykel, eller (för icke-kaktus) där varje block (maximal subgraf utan snitt-vertex ) är en kant eller en cykel.
Egenskaper
Kaktusar är yttre plana grafer . Varje pseudoträd är en kaktus. En icke -privat graf är en kaktus om och bara om varje block antingen är en enkel cykel eller en enda kant.
Familjen av grafer där varje komponent är en kaktus stängs nedåt under grafiska mindre operationer. Denna graf familj kan kännetecknas av en enda förbjuden moll , den fyra vertex diamantgraf som bildas genom att avlägsna en kant från komplett graf K 4 .
Triangulär kaktus
En triangulär kaktus är en speciell typ av kaktusgraf så att varje cykel har längd tre och varje kant tillhör en cykel. Till exempel är vänskapsgraferna , grafer som bildas från en samling trianglar sammanfogade vid en enda gemensam toppunkt, triangulära kaktusar. Förutom att vara kaktusgrafer är de trekantiga kaktusarna också blockgrafer och lokalt linjära grafer .
Triangulära kaktusar har egenskapen att de förblir anslutna om någon matchning tas bort från dem; för ett givet antal hörn har de minst möjliga kanter med den här egenskapen. Varje träd med ett udda antal hörn kan förstoras till en triangulär kaktus genom att lägga till kanter på det, vilket ger en minimal förstoring med egenskapen att förbli ansluten efter att en matchning har tagits bort.
Den största triangulära kaktusen i någon graf kan hittas under polynomtid med hjälp av en algoritm för matroidparitetsproblemet . Eftersom triangulära kaktusgrafer är plana grafer kan den största triangulära kaktusen användas som en approximation till den största plana subgrafen, ett viktigt delproblem vid planarisering . Som en approximationsalgoritm har denna metod approximationsförhållandet 4/9, det mest kända för det maximala plana subgrafproblemet.
Algoritmen för att hitta den största triangulära kaktusen är associerad med en sats av Lovász och Plummer som kännetecknar antalet trianglar i denna största kaktus. Lovász och Plummer betraktar par av partitioner av hörnens och kanterna på den givna grafen i delmängder, med egenskapen att varje triangel i grafen antingen har två hörn i en enda klass av toppunktspartitionen eller alla tre kanterna i en enda klass av kantpartition; de kallar ett par partitioner med den här egenskapen giltig . Då är antalet trianglar i den största triangulära kaktusen lika med max, över par med giltiga partitioner och , av
- ,
var är antalet hörn i den givna grafen och är antalet hörnklasser som möts av kantklassen .
Nyligen bevisades en tät yttergräns som visade att med tanke på alla plandiagram finns det alltid en kaktussubgraf som innehåller åtminstone en bråkdel av de triangulära ytorna . Detta resultat innebär en direkt analys av 4/9 - approximationsalgoritmen för maximalt plan subgrafproblem utan att använda min -max -formeln ovan.
Rosas gissning
En viktig gissning relaterad till den triangulära kaktusen är Rosas gissning , uppkallad efter Alexander Rosa , som säger att alla triangulära kaktusar är graciösa eller nästan graciösa. Mer exakt
Alla triangulära kaktusar med t ≡ 0, 1 mod 4 block är graciösa, och de med t ≡ 2, 3 mod 4 är nära graciösa.
Algoritmer och applikationer
Vissa anläggningsproblem som är NP-hårda för allmänna grafer, liksom några andra grafproblem, kan lösas på polynomtid för kaktusar.
Eftersom kaktusar är specialfall av yttre plana grafer kan ett antal kombinatoriska optimeringsproblem på grafer lösas för dem på polynomtid .
Kaktusar representerar elektriska kretsar som har användbara egenskaper. En tidig applicering av kaktusar var associerad med representationen av op-ampere.
Kaktusar har också nyligen använts i jämförande genomik som ett sätt att representera förhållandet mellan olika genom eller delar av genomer.
Om en kaktus är ansluten, och var och en av dess hörn hör till högst två block, kallas den en julkaktus . Varje polyhedral graf har en julkaktusundergraf som innehåller alla dess hörn, ett faktum som spelar en väsentlig roll i ett bevis av Leighton & Moitra (2010) att varje polyhedral graf har en girig inbäddning i det euklidiska planet , en tilldelning av koordinater till hörnen för vilka giriga vidarebefordran lyckas dirigera meddelanden mellan alla hörnpar.
I topologisk grafteori är graferna vars cellulära inbäddningar alla är plana exakt underfamiljen till kaktusgraferna med den extra egenskap som varje toppunkt tillhör högst en cykel. Dessa grafer har två förbjudna minderåriga, diamantgrafen och vänskapsdiagrammet med fem vertex .
Historia
Kaktusar studerades först under namnet Husimi -träd , tilldelade dem av Frank Harary och George Eugene Uhlenbeck för att hedra tidigare arbete med dessa grafer av Kôdi Husimi . Samma Harary - Uhlenbeck -papper reserverar namnet "kaktus" för grafer av denna typ där varje cykel är en triangel, men nu är det tillåtet att använda cykler av alla längder.
Under tiden kom namnet Husimi -trädet vanligtvis att hänvisa till grafer där varje block är ett komplett diagram (ekvivalent, skärningsgraferna för blocken i någon annan graf). Denna användning hade lite att göra med Husimis arbete, och den mer relevanta termen blockdiagram används nu för denna familj; på grund av denna oklarhet har denna fras dock blivit mindre frekvent för att referera till kaktusgrafer.