miniatur|Ein Kaktusgraph 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.
Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein. 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. Die Familie aller Kaktusgraphen kann durch einen verbotenen Minor charakterisiert werden. Dieser Minor entspricht dem vollständigen Graphen in welchem eine Kante entfernt wurde.
Einzelnachweise
Kategorie:Graphenklasse