Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:15 So 11.07.2004 | | Autor: | andreas99 |
Hi,
ich hab hier eine Aufgabe aus der Graphentheorie welche ich nicht sicher lösen kann. Weil das zu viel Text ist und auch noch ein kleines Bildchen dabei hab ich es einfach als Bild hochgeladen:
]-->[Dateianhang nicht öffentlich]
a) und b) hängen natürlich vom benutzten Algorithmus ab.
Bei c) hab ich zuerst einfach mal einen Kruskal versucht und damit einen minimal spannenden Baum über alle Knoten bekommen. Jetzt hab ich die Wege entfernt wo keine zu vernetzenden Filialen dranhängen. Als Gesamtgewicht ergibt sich 19. Jetzt hab ich noch etwas per Hand weiter probiert und sogar noch Wege gefunden deren Gesamtgewicht nur 17 beträgt. Nur mit Kruskal alleine kann es also nicht getan sein. Brauche ich in diesem Fall den Algorithmus von Floyd-Warshall?
Alternativ hab ich mir auch überlegt man könnte für alle zu vernetzenden Filialen einen Djikstra one-to-one mit allen anderen zu vernetzenden Filialen machen. Daraus baue ich einen neuen Graphen und finde dort den minimal spannenden Baum mit Hilfe von Kruskal. Aber irgendwie scheint mir das zu umständlich. Außerdem war das eine Klausuraufgabe und diese sollte in einigen Minuten auf Papier lösbar sein.
Gruß
Andreas
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
Hallo Andreas,
ich hab dazu eine Frage: Was ist damit gemeint, die Filialen zu vernetzen? Soll ein Strassen-/Telefon-/sonstiges Netz aufgebaut werden, oder geht es um Transportwege?
Ich waehle z.B. folgende Verbindungen:
[mm] S_1 [/mm] - [mm] S_3 [/mm] - [mm] S_6
[/mm]
[mm] S_7 [/mm] - [mm] S_5 [/mm] - [mm] S_3 [/mm] - [mm] S_6
[/mm]
Wenn es um Strassenbau/Telefonleitungen oder so geht, dann sind die Kosten fuer diese beiden Verbindungen 13, wenn es aber um Transport geht, dann muss ja [mm] S_3 [/mm] - [mm] S_6 [/mm] auch zweimal gezaehlt werden, und die Kosten sind 16.
Im ersten Fall ist also ein minimal spannender Baum gesucht, im anderen Fall eine Familie kuerzester Verbindungen. Nach deinen Ansaetzen ist wohl erstes gemeint, oder?
Uebrigens haengt natuerlich auch c) vom bei a) und b) benutzten Algorithmus ab, da ja "mittels dieses Algorithmus" eine Loesung bestimmt werden soll.
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:11 Di 13.07.2004 | | Autor: | andreas99 |
Hi,
ich hab die Klausur heute geschrieben und den Teil Graphen eigentlich ganz gut hinbekommen. Leider war der Teil zur Wahrscheinlichkeitsberechnung nicht so dolle. :-(
Vermutlich werde ich also die Klausur noch einmal mitschreiben dürfen und stehe also demnächst wieder vor änlichen Problemen. Naja, warten wir erst mal ab...
Ich werde wegen der Frage auch noch mal den Professor ansprechen und hier dann nochmal zu einem späteren Zeitpunkt versuchen über die Aufgabe zu diskutieren. Die Sachen die du in deiner Antwort nachgefragt hast zieh ich mir im Detail morgen rein. Heute kann ich keine Graphen mehr sehen 
Nachdem die Zeit für diese Aufgabe im Matheraum abgelaufen war hab ich es noch an einer anderen Stelle im Usenet gefragt. Damit keine doppelten Diskussionen entstehen hier mal den Link darauf:
http://makeashorterlink.com/?N3CF429C8
Gruß
Andreas
|
|
|
|
