Hallo,
ich suche die in der Literatur übliche Bezeichnung für folgenden Graphen (mal angenommen es gibt sie):
Kurz: Ausgehend von einem vollständigen Graphen mit geradzahliger Knotenzahl 2k entfernt man k Kanten derart, daß jeder Knoten mit 2(k-1) anderen Knoten adjazent ist. Bsp. für k=2:
o o
| \/ |
| /\ |
o o
Genauer: Man nimmt als Knotenmenge z.B. Vk={ i,-i | 1k={ (u,v) | u,v∈ Vk mit u-v }.
Hat das Teil irgendeinen Namen („fast vollständiger Graph“ *g*) ?
Gruss
Enno
Nachtrag
Hallo,
Hintergrund ist - ich suche die Anzahl aller nichtleeren knotendisjunkten Pfade durch so einen Graphen (für beliebige Start- und Endknoten). Die Pfade lassen sich als Folgen von Knoten sehen, mit der Eigenschaft:
o Kein Knoten kommt mehr als einmal vor.
o u und -u sind nie aufeinanderfolgend (bei der obigen Wahl der Knoten als ganze Zahlen).
Bsp für k=3.
(1,2,-1,3) (1,2,3) (1,2,3,-1,-2,-3) sind z.B. gültige Pfade
(1,-1,2,3) (2,-3,3,1) (1,-1,2,-2,3,-3) dagegen nicht.
Gruss
Enno
Hallo Enno,
man nennt solche Graphen mehrfach zusammenhängende Graphen.
Ganz gute Beschreibung:
http://de.wikipedia.org/wiki/Zusammenh%E4ngender_Graph
Auszug:
G heißt k-fach kantenzusammenhängend, wenn es keine maximal k-1 elementige Kantenmenge in G gibt, die G trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen). Als Kantenzusammenhangszahl eines Graphen G bezeichnet man das größte k, sodass G k-fach kantenzusammenhängend ist.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
danke den Zusammenhang hatte ich schon entdeckt, da ich erst dachte den Satz von Menger zur Bestimmung einer Obergrenze der knotendisjunkten Wege verwenden zu können. Aber evtl. würde das Problem ja allgemein für diese Graphenklasse gelöst, ich werde auf jeden Fall noch einmal gezielt mittels dieser Bezeichnung suchen.
Für k=3 hat jmd. in einer anderen Newgruppe den hübschen Zusammenhang zu Wegen auf den Seiten eines Würfels entdeckt (u und -u sind dabei gegenüberliegende Seiten). Man kann damit gut die Anzahl der Wege begründen. Der allgemeine Fall scheint mir allerdings ziemlich hartnäckig zu sein.
Gruss
Enno