imported>DeWikiMan: + Normdaten; + lang-Par.; + Bez. Husimi-Baum, s. Diskussion:Kaktusgraph#Husimi-Baum

2024-09-01T18:06:09Z

+ Normdaten; + lang-Par.; + Bez. Husimi-Baum, s. Diskussion:Kaktusgraph#Husimi-Baum

Neue Seite

[[Datei:Cactus graph.svg|miniatur|Ein Kaktusgraph]]
In der [[Graphentheorie]] bezeichnet ein '''Kaktusgraph''' (zum Teil auch nur '''Kaktus''', manchmal auch '''Husimi-Baum''') einen [[Zusammenhang (Graphentheorie)|zusammenhängenden]] [[Graph (Graphentheorie)|Graphen]], in dem sich jedes Paar seiner [[Kreis (Graphentheorie)|Kreise]] höchstens einen gemeinsamen [[Knoten (Graphentheorie)|Knoten]] teilt.<ref>
{{cite journal
| last1 = Geller
| first1 = Dennis
| last2 = Manvel
| first2 = Bennet
| year = 1969
| title = Reconstruction of cacti
| language = en
| journal = Canad. J. Math.
| volume = 21
| pages = 1354–1360
| doi = 10.4153/CJM-1969-149-3
| url = http://cms.math.ca/cjm/v21/cjm1969v21.1354-1360.pdf
}}
</ref>

Den Begriff Kaktusgraph (engl. ''cactus'') führten [[Frank Harary]] und [[George Eugene Uhlenbeck]] ein.<ref>{{cite journal |last1=Harary |first1=Frank |last2=Uhlenbeck|authorlink=Frank Harary|first2=George E. |title=On the number of Husimi trees, I |language=en |journal=[[Proceedings of the National Academy of Sciences]] |volume=39 |year=1953 |pages=315–322 |id=Mathematical Reviews 0053893 |doi=10.1073/pnas.39.4.315 |issue=4}} </ref> 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 [[Zyklomatische Zahl|zyklomatischen Zahl]] <math>\mu (G)</math> entspricht.
* Kaktusgraphen sind [[Planarer Graph|außerplanare]] Graphen.
* Jeder [[Planarer Graph|planare]] [[K-Zusammenhang|3-zusammenhängende]] Graph besitzt einen aufspannenden Kaktusgraphen, der die Eigenschaft hat, dass das Entfernen eines beliebigen Knoten den Graphen in maximal zwei [[Zusammenhang (Graphentheorie)|Zusammenhangskomponenten]] teilt.<ref>{{cite journal
| last1 = Leighton | first1 = Tom
| last2 = Moitra | first2 = Ankur
| issue = 3
| journal = Discrete & Computational Geometry
| pages = 686–705
| title = Some Results on Greedy Embeddings in Metric Spaces
| language = en
| volume = 44
| doi = 10.1007/s00454-009-9227-6
| url = http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf
| year = 2010}}
</ref>
* Die Familie aller Kaktusgraphen kann durch einen verbotenen [[Minor (Graphentheorie)|Minor]] charakterisiert werden. Dieser Minor entspricht dem [[Vollständiger Graph|vollständigen Graphen]] <math>K_4</math> in welchem eine Kante entfernt wurde.<ref>{{cite journal |last1=El-Mallah |first1=Ehab |last2=Colbourn |first2=Charles J. |title=The complexity of some edge deletion problems |language=en |journal=IEEE Transactions on Circuits and Systems |volume=35 |issue=3 |year=1988 |pages=354–362 |doi=10.1109/31.1748}}</ref>

== Einzelnachweise ==
<references/>

{{Normdaten|TYP=s|GND=4736715-5}}
[[Kategorie:Graphenklasse]]

Kaktusgraph - Versionsgeschichte

imported>DeWikiMan: + Normdaten; + lang-Par.; + Bez. Husimi-Baum, s. Diskussion:Kaktusgraph#Husimi-Baum