Graphentheorie

[[MSMC]Jesus C]

Hi,

ich habe hier mehrere Knoten mit jeweils mehreren Kanten. Bei jeder Kante weiß ich, dass ich bestimmte andere Knoten über diese Kanten erreichen kann. Gibt es hierfür bereits einen bekannten Algorithmus, der mir daraus einen Graphen baut?

Im Studium wurden Graphen bei uns nur soweit behandelt, als dass man bei gegebenen Graphen, den kürzesten Weg zwischen zwei Knoten finden kann, wenn man sich Dijkstra bedient.

 

[killerchicken_inaktiv]

Ich würde sagen, dass das darauf ankommt, was für einen Graphen du willst. Kannst zu zudem nochmal ein wenig genauer sagen, was du über die Kanten weisst? Normalerweise verbindet eine Kante ja genau 2 Knoten - wenn du weisst, dass du mittels einer gewissen Kante eine Menge Knoten erreichen kannst, weisst du ja schon, welche Knoten alle im Graphen sind. Dann sind allerdings alle Kanten im Graphen voneinander ununterscheidbar ohne Zusatzinfos

 

[[MSMC]Jesus C]

Versuchen wir es mit einem praktischen Beispiel:

Gegeben sei:

Jeder Knoten hat zwei Kanten(1,2).

Es sei bekannt welche anderen Knoten über die Kanten erreichbar sind.(U.U. über mehrere Hops aber ohne zurückzugehen)

A:1:-;       2:B,C,D,E
B:1:A;       2:C,D,E
C:1:A,B;     2:D,E
D:1:A,B,C;   2:E
E:1:A,B,C,D; 2:-

Es sei folgender ungerichteter Graph gesucht:

(A)-(B)-(C)-(D)-(E)

Ich hoffe da ist jetzt etwas unmissverständlicher.

 

[killerchicken_inaktiv]

ich interpretiere jetzt also richtign dass A, B, C, D, E Knoten sind.

Knoten A hat keine erste Kante, über die zweite Kante kann er Knoten B, C, D, E erreichen (man weiß aber nicht, in welcher Reihenfolge)?

 

[[MSMC]Jesus C]

Original geschrieben von killerchicken
ich interpretiere jetzt also richtign dass A, B, C, D, E Knoten sind.

Knoten A hat keine erste Kante, über die zweite Kante kann er Knoten B, C, D, E erreichen (man weiß aber nicht, in welcher Reihenfolge)?

Genau.

Edit: Ich hatte mir bisher schon einen Algorithmus überlegt, der aber SAUKOMPLIZIERT ist. Gerade kam mir eine einfacherere Idee:

Unter der Vorraussetzung, dass keine "Kreise" vorhanden sind:

1) Suche einen Knoten mit nur einer Kante
2) Suche einen Knoten der an einer Kante nur den ersten Knoten hat und hänge ihn an den ersten
3) Nimm den zweiten Knoten als ersten und ignoriere alle Einträge über den ursprünglich ersten
4) Gehe zu 2)

Ist etwas platt formuliert und es fehlen noch einige Überprüfungen sowie die Abbruchbedingung, aber sollte so tun...

 

[killerchicken_inaktiv]

Na, dann ists ja nicht besonders schwer

Aus der Konstruktion folgt, dass jeder der Graphen eine Kette von Knoten ist, mit Anfangs-und Endknoten. Ist das nicht der Fall, handelt es sich um einen Ring, in dem alle Knoten gleichberechtigt sind - hier lässt sich aber kein eindeutiger Graph bilden, also kann der Fall ausgeschlossen werden.

Der Algo geht so:

Nimm einen Startknoten (einer der beiden Kanten existiert nicht) als Knoten v
Setze x auf 1.

solange v Kinder hat, die nicht in der Lösungsmenge enthalten sind
____besuche alle von v erreichbaren Knoten u
____falls u eine Kante hat, von der genau x Knoten erreicht werden können und v einer davon ist
________es wird eine Kante von v nach u geben, merke u in der Lösungsmenge
________setze v = u, x = x + 1

sonderlich effizient ist das nicht, hab ich mir gerade aus den Fingern gesogen.

[edit] na also, kamst ja selbst drauf war aber noch nicht da als ich gepostet hab ;P

 

[[MSMC]Jesus C]

Original geschrieben von killerchicken
[edit] na also, kamst ja selbst drauf war aber noch nicht da als ich gepostet hab ;P [/B]

Da kannst du mal sehen wie schnell ich was abgucken und umformulieren kann .

Dankeschön!

 

[killerchicken_inaktiv]

oh, ich merke gerade, die Einrückung in meinem text ist futsch gegangen. ich hab das mal korrigiert und mit ___ ersetzt.

 

[NacktNasenWombi]

http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal

is das nicht das gesuchte?!

 

[killerchicken_inaktiv]

Nein, sicherlich nicht. Die Vorraussetzungen sind total anders - bei Kruskal weisst du, welche Knoten du direkt von Knoten x erreichen kannst.
Hast du die Frage bzw den Thread überhaupt komplett gelesen?

 

[NacktNasenWombi]

ich habe hier mehrere Knoten mit jeweils mehreren Kanten. Bei jeder Kante weiß ich, dass ich bestimmte andere Knoten über diese Kanten erreichen kann. Gibt es hierfür bereits einen bekannten Algorithmus, der mir daraus einen Graphen baut?

= Bildung eines Spannbaumes?

Es sei bekannt welche anderen Knoten über die Kanten erreichbar sind.(U.U. über mehrere Hops aber ohne zurückzugehen)

= Ich kenn den Graph?




Aber darfst mich gerne aufklären wo mein Fehler liegt

 

[killerchicken_inaktiv]

Wie ich bereits sagte, die Vorraussetzungen sind anders. Der Baum ist eben nicht bekannt, es ist nur bekannt, dass von jedem Knoten 2 Kanten weggehen, und zu jeder Kante ist bekannt, welche anderen Knoten erreichbar sind von dieser Kante. Insbesondere unbekannt ist, welcher Knoten _direkt_ erreichbar ist über besagte Kante.