Kaktusgraph
Zur Navigation springen
Zur Suche springen
In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus) 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[Bearbeiten | Quelltext bearbeiten]
- 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]
Einzelnachweise[Bearbeiten | Quelltext bearbeiten]
- ↑ Dennis Geller, Bennet Manvel: Reconstruction of cacti. In: Canad. J. Math. 21. Jahrgang, 1969, S. 1354–1360, doi:10.4153/CJM-1969-149-3 (math.ca [PDF]).
- ↑ Frank Harary, George E. Uhlenbeck: On the number of Husimi trees, I. In: Proceedings of the National Academy of Sciences. 39. Jahrgang, Nr. 4, 1953, Mathematical Reviews 0053893, S. 315–322, doi:10.1073/pnas.39.4.315.
- ↑ Tom Leighton, Ankur Moitra: Some Results on Greedy Embeddings in Metric Spaces. In: Discrete & Computational Geometry. 44. Jahrgang, Nr. 3, 2010, S. 686–705, doi:10.1007/s00454-009-9227-6 (mit.edu [PDF]).
- ↑ Ehab El-Mallah, Charles J. Colbourn: The complexity of some edge deletion problems. In: IEEE Transactions on Circuits and Systems. 35. Jahrgang, Nr. 3, 1988, S. 354–362, doi:10.1109/31.1748.