Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Graph zeichnen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Graph zeichnen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Hellboy256
Grünschnabel

Dabei seit: 17.04.2010
Beiträge: 8

Graph zeichnen

Zitatantwort auf diesen Beitrag erstellen

Gegeben ist ein Fluss mit einer unendlichen Menge an Wasse. Weiters stehen 2 Eimer zur verfuegung, einer mit 5 litern und einer mit 3 litern.
1. Es ist moeglich mit beiden Eimern Wasser aus dem Fluss zu entnehemen und das Wasser aus einem Eimer in den anderen zu fuellen.
2. Nun soll mit den beiden Eimern exakt 4 liter ausgeschoepft werden

Die 1. Beschreibung soll nun mit einem Graphen dargestellt werden und fuer die Loesung der Zweiten soll ein Weg in dem Aufgestellten Graphen gezeigt werden.

Also fuer die Loesung der Zweiten:
Ich fuell den 3l Eimer voll und schuette ihn in den 5liter, anschliessend nochmal bis der 5liter voll ist und uebrig bleibt mir im 3liter Eimer 1liter. Der 5liter wird in den Fluss geleert und die 1liter im 3liter Eimer in den 5liter Eimer geschuettet und zum Schluss noch ein ganzer 3liter Eimer in den 5liter Eimer = 4liter

Also den Graph fuer 1 hab ich mal versucht zu zeichnen koennte der stimmen?
Aber wie wuerde denn jetzt der Weg fuer 2 aussehen?

Hellboy256 hat dieses Bild (verkleinerte Version) angehängt:

12.06.2010 16:07

Nehmen Sie Hellboy256 in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

RE: Graph zeichnen

Wenn du einen Graphen erstellst, der das Problem modellieren soll müssen dir zwei Dinge klar sein:

a) Was stellen die Knoten dar?
b) Was bedeutet es wenn eine Kante von Knoten A nach Knoten B geht?

Für den zweiten Teil der Aufgabe kannst du Dich auch gleich fragen was ein Weg durch den Graphen darstellt?

14.06.2010 12:52

Nehmen Sie ed209 in Ihre Freundesliste auf

Hellboy256
Grünschnabel

Dabei seit: 17.04.2010
Beiträge: 8

RE: Graph zeichnen

Also die Knoten repraesentieren die beiden Koerbe und den Fluss. Ein Weg von Korb zum Fluss und wieder zurueck soll das Wasserholen simulieren.
Wenn ich jetzt vom ersten Korb zum Fluss und wieder zurueck gehe, anschliessend zum Korb 2 und wieder zu Korb 1, das ganze nochmal und dann den Korb 2 leeren, Korb 1 in Korb 2 fuellen und dann nochmal den Weg von Korb 1 zum Fluss wieder zurueck und in den Korb 2??

14.06.2010 19:25

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Das ist sehr difus. Vergiss mal für eine Zeit die Zeichnung die du schon gemacht hab und versuch Regeln für den Graphen zu finden, nach der Form:

Jeder Knoten im Graph ist ein ....
Wenn eine Kante von A nach B geht, dann bedeutet das, daß ..........

Was für eine Definition für Graphen benutzt ihr. Bei der Art von Graphen die ich vermute die Ihr Benutzen sollt, vermisse ich nämlich noch was.
Schreib mal die Definition für Graphen auf die ihr benutzt.

Und was bedeutet "Weg in dem Aufgestellten Graphen"?

Gruß,
ED

14.06.2010 19:48

Hellboy256
Grünschnabel

Dabei seit: 17.04.2010
Beiträge: 8

Jeder Knoten im Graph ist ein Eimer oder Fluss??
Wenn eine Kante von A nach B geht bedeutet das, dass Wasser umgeschuettet wird??

Also die Aufgabe zur ersten (einfach nur das Modell repraesentieren) ist so formuliert:
Draw a graph that represents a model of this exercise!

14.06.2010 20:18

bitwizzard
Grünschnabel

Dabei seit: 07.06.2010
Beiträge: 3

RE: Graph zeichnen

irgendwie fehlt eine reihenfolge des ablaufs,evtl könnten eine nummerierung der pfeile helfen oder du schreibst bedingungen mit an die pfeile

mir ist eine ähnlichkeit zu den 'Türmen von Hanoi' aufgefallen...
http://de.wikipedia.org/wiki/Türme_von_Hanoi

bitwizzard hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von bitwizzard: 16.06.2010 08:24.

16.06.2010 08:05

Nehmen Sie bitwizzard in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Zitat:

Original von Hellboy256
Jeder Knoten im Graph ist ein Eimer oder Fluss??

Hier hast du eine Inkonsistenz: Knoten sind mal Eimer und mal Flüsse.
Ich bin mir nicht ganz sicher, auf welchem Stand ihr seid und wie ihr das Problem lösen sollt.
Aber ich vermute es läuft auf einen Zustandsgraphen heraus, bei dem die Knoten den aktuellen Zustand der Eimer beschreiben sollen.

Bitte schreib mal die Definition eines Graphens hier rein, die ihr benutzt.

16.06.2010 13:13

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Graph zeichnen