Algorithmische Graphentheorie - Frage

[Czelly]

Hallo liebe Community,

Ich bin auf dieser Forum gestoßen und nachdem ich mir ein paar Beiträge durchgelesen habe, hab ich schnell erkannt, dass es hier viele Mitglieder gibt welche wesentlich mehr Verständniss von vielen Dingen haben als ich und die mir vielleicht bei dem ein oder anderen Problem helfen könnten.

Ich habe in meinem Studium eine Aufgabe bekommen zur Graphentheorie und zum Algorithmus von Dijkstra. Ich habe diese Aufgabe selbst gelöst aber ich werde sie euch dennoch hier schreiben um vielleicht meine Frage besser nachvollziehen zu können.

Zur Herstellung des Produktes "Super", ausgehend vom Rohstoff A, stehen folgende Produktionsschritte zur Verfügung:


Rohstoff A zu Zwischenprodukt 1: 15 Manntage

Rohstoff A zu Zwischenprodukt 2: 3 Manntage

Zwischenprodukt 1 zu Zwischenprodukt 3: 5 Manntage

Zwischenprodukt 1 zu Zwischenprodukt 4: 7 Manntage

Zwischenprodukt 1 zu "Super": 30 Manntage

Zwischenprodukt 2 zu Zwischenprodukt 1: 2 Manntage

Zwischenprodukt 3 zu Zwischenprodukt 5: 8 Manntage

Zwischenprodukt 4 zu Zwischenprodukt 5: 7 Manntage

Zwischenprodukt 5 zu "Super": 2 Manntage


Stellen Sie diese Beziehungen als gerichteten, gewichteten Graph (Knoten: Rohstoffe/Zwischenprodukte/Endprodukte, Kanten: Produktionsschritte, Kantengewichte: Manntage) dar und finden Sie mit dem Algorithmus von Dijkstra:

- einen kürzesten Weg (minimale Zahl der Manntage) von Rohstoff A zu "Super"

- einen kürzesten Weg (minimale Zahl der Manntage) von Rohstoff A zum Zwischenprodukt 4


Geben Sie dabei in jedem Schritt die Distanzen und Vorgänger sowie die Liste der nicht betrachteten Knoten an.

[/PHP]

Wie bereits gesagt habe ich die Aufgabe gelöst aber mir ist dabei eine Frage entstanden welche eventuell relevant für die kommende Prüfung sein könnte. Und zwar: Ist der Graph eigentlich stark bzw. schwach zusammenhängend? Wenn nein, was sind dann die Zusammenhangskomponenten?

Ich habe bereits danach gegoogelt und mich auch durch Wikipedia gelesen aber irgendwie verstehe ich es nicht.

Ich habe im Anhang eine Skizze von diesem Beispiel angehängt. Vielleicht hilft sie ja dem ein oder anderen.

Wäre spitze wenn mir jemand helfen könnte.

Vielen Dank schon einmal im Vorraus.

Liebe Grüße

[flashpixx]

Ist der Graph eigentlich stark bzw. schwach zusammenhängend?

kann man doch wunderbar nach Definition zeigen Zusammenhang von Graphen ? Wikipedia

Du hast einen gerichteten Graphen, somit:

Ein gerichteter Graph G=(V,E) heißt (stark) zusammenhängend von einem Knoten v aus, falls es zu jedem Knoten w aus V einen gerichteten Weg in G gibt, mit v als Startknoten und w als Endknoten. G heißt stark zusammenhängend, falls G von jedem Knoten v aus V zusammenhängend ist.

Ein gerichteter Graph heißt (schwach) zusammenhängend, falls der zugehörige ungerichtete Graph (also der Graph, der entsteht, wenn man jede gerichtete Kante durch eine ungerichtete Kante ersetzt) zusammenhängend ist.

Wenn nein, was sind dann die Zusammenhangskomponenten?

Ein induzierter Teilgraph K=(VK,EK) von G heißt starke Zusammenhangskomponente von G, falls K stark zusammenhängend ist und kein stark zusammenhängender induzierter Teilgraph von G existiert, der K echt enthält.

Ich habe bereits danach gegoogelt und mich auch durch Wikipedia gelesen aber irgendwie verstehe ich es nicht.

Dann muss Du auch erklären, was Du nicht verstehst. Gerade der Wikiartikel ist extrem schön verständlich. Schau Dir die Definitionen an, gehe sie Wort für Wort durch und mache Dir an Deinem Beispiel klar was die Definition hast.

Da Du aber immer von einem gerichteten Graphen sprichst, das Bild aber einen ungerichteten Graphen zeigt, ist eine Erklärung nicht so möglich.

Das Bild trifft doch direkt die Definition:

Ein ungerichteter Graph G=(V,E) heißt zusammenhängend, falls es zu je zwei beliebigen Knoten v und w aus V einen ungerichteten Weg in G gibt, mit v als Startknoten und w als Endknoten.

Egal welche Knoten v und w ich nehme, ich finde immer einen ungerichteten Weg zwischen diesen. Das ganze jetzt formal zu beweisen ist natürlich etwas anspruchsvoller. Anschaulich gesprochen bedeutet die Definition, dass Du von jedem Knoten zu jedem anderen Knoten kommst (bei gerichteten Graphen muss das nicht immer so sein)

Bearbeitet 4. April 2010 von flashpixx

[Czelly]

Hallo,

Vielen dank für diesen Beitrag. Ich werde morgen in aller Ruhe mir diese Definition ansehen und durchgehen...vielleicht wenn ich mir wirklich alles detailiert ansehe erkenne ich dann auch die Lösung. Wenn nicht werde ich hier wieder meine Frage stellen.

Aber was mich gerade beunruhigt...

Du hast folgendes geschrieben:

Da Du aber immer von einem gerichteten Graphen sprichst, das Bild aber einen ungerichteten Graphen zeigt, ist eine Erklärung nicht so möglich.

Ich verstehe überhaupt nicht was du damit meinst. Meine Skizze welche im Anhang ist, ist kein gerichteter sondern ein ungerichteter Graph? Wieso denn das? Wie müsste der Graph bzw. meine Skizze dann bitte aussehen um ein gerichteter Graph zu sein?

Ich bitte um eine Antwort!

[flashpixx]

Meine Skizze welche im Anhang ist, ist kein gerichteter sondern ein ungerichteter Graph? Wieso denn das? Wie müsste der Graph bzw. meine Skizze dann bitte aussehen um ein gerichteter Graph zu sein?

Du beziehst Dich doch auf eine Aufgabe in der es lautet:

Stellen Sie diese Beziehungen als gerichteten, gewichteten Graph

darum sollte die Skizze auch ein gerichteter Graph sein. Außerdem sind die Definitionen für gerichtete bzw ungerichtete Graphen etwas unterschiedlich

[Czelly]

Das bedeutet ich habe den Graphen falsch gezeichnet?

Aber wieso. Was ist der Unterschied? Wie müsste der gerichtete Graph aussehen?

Ich muss das Beispiel heute noch abgeben also wäre es super wenn du mir helfen könntest und mir sagst, was falsch ist..ich blicke da irgendwie gerade nicht durch. Ich dacht mein Bsp wäre richtig

Liebe Grüße,

EDIT:

Stimmt es in etwa so:

Gerichteter Graph:

Geht immer nur in eine Richtung. z.B: von Punkt A nach Punkt B

Ungerichteter Graph:

Geht in beide Richtungen. z.B: von Punkt A nach Punkt B und Punkt B nach Punkt A?

Wenn das so ist, ist der Algorithmus von Dijkstra überhaupt anwendbar bei einem gerichteten Graphen?

Bearbeitet 4. April 2010 von Czelly

[flashpixx]

Das bedeutet ich habe den Graphen falsch gezeichnet?

Wenn Deine Skizze das Bild zur Aufgabenstellung sein soll, ja.

Aber wieso. Was ist der Unterschied? Wie müsste der gerichtete Graph aussehen?

In einem gerichteten Graphen sind eben die Richtung vorgegeben wie die Wege "gelaufen" werden.

Warum schaust Du Dir nicht an, wie erst einmal un-/gerichtete Graphen aussehen?

Graph (Graphentheorie) ? Wikipedia

Ich dacht mein Bsp wäre richtig

Wenn die Skizze die Darstellung der Aufgabenstellung sein soll, dann nicht. Vor allem stimmt dann nicht zwingend die Lösung, wenn Du es einmal per gerichteten und einmal per ungerichteten Graphen auswertest.

Wenn das so ist, ist der Algorithmus von Dijkstra überhaupt anwendbar bei einem gerichteten Graphen?

Natürlich in jedem Navi ist dieser Algorithmus implementiert und Straßen sind bekanntlich gerichtete Kanten.

[Czelly]

Hallo,

Vielen dank für deine Antwort!

Ich habe dir im Anhang die Lösung der Aufgabe (sprich meine Lösung) mal angehängt. Ich würde es verstehen wenn du keine Lust hast dir das alles anzusehen aber ich benötige diese Aufgabe unbedingt vollständig und auch richtig.

Ich habe in diesem .zip Archiv die Datei skizze.jpg mit meiner Zeichnung und die 3_aufgabe.doc wo ich den Algorithmus beschreibe.

Es wäre mir wirklich eine Wahnsinnige Hilfe wenn du mir sagen könntest ob aufgrund meiner falschen Skizze nun auch die gesamte Aufgabe zum Wegwerfen ist und ich heute noch einmal alles neu schreiben müsste

Liebe Grüße

3.Aufgabe.zip

[flashpixx]

Ich würde sagen, dass alles falsch ist, denn alle Bilder sind ungerichtete Graphen, so dass schon mal diese nach der Aufgabenstellung falsch sind.

Inwieweit jetzt die Lösung, d.h. der ermittelte Weg im Graph falsch ist, müsste ich selbst ausrechnen.

Zur Darstellung: Word ist für die Graphdarstellung nicht die beste Wahl. Du solltest Graphviz oder LaTeX mit TikZ and PGF examples verwenden

[Czelly]

Hallo,

Okay vielen dank für die Hilfe!

Das bedeutet ich kann alles nochmal machen!

Ich habe nur ein Problem damit zu verstehen wie der gerichtete Graph dann auf meiner Skizze aussehen soll! Was stimmt an der Skizze, welche ich im 1 Post eingefügt habe denn nicht?

Ist es der Strich von B zu E welcher Weg muss da bei einem gerichteten Graphen es ja immer nur in eine Richtung geht und wenn man somit einmal schon bei D war man nicht mehr zu B zurück kann?

Oder muss die Skizze komplett anders ausehen?

[flashpixx]

Ich habe nur ein Problem damit zu verstehen wie der gerichtete Graph dann auf meiner Skizze aussehen soll!

Schau Dir bitte den Wikipedia Artikel an

Graph (Graphentheorie) ? Wikipedia

Dort sind Beispiele !

[Czelly]

Die habe ich mir bereits angesehen und daraus ist auch meine obrige Frage entstanden..ich will nur auf nummer sicher gehen nicht das ich noch einmal von vorne anfangen kann!

Liebe Grüße