Kaktusgraph
Zur Navigation springen
Zur Suche springen
In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus, manchmal auch Husimi-Baum) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt.[1]
Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein.[2] In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind.
Eigenschaften
- Ein Graph G ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Zyklen seiner zyklomatischen Zahl entspricht.
- Kaktusgraphen sind außerplanare Graphen.
- Jeder planare 3-zusammenhängende Graph besitzt einen aufspannenden Kaktusgraphen, der die Eigenschaft hat, dass das Entfernen eines beliebigen Knoten den Graphen in maximal zwei Zusammenhangskomponenten teilt.[3]
- Die Familie aller Kaktusgraphen kann durch einen verbotenen Minor charakterisiert werden. Dieser Minor entspricht dem vollständigen Graphen in welchem eine Kante entfernt wurde.[4]