Basislösung Beweis < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:46 Sa 13.06.2015 | | Autor: | Mesos |
| Aufgabe | | Beweise, dass das Verfahren zur Bestimmung einer Basislösung tatsächlich eine BL, also einen aufspannenden Baum im Transportgraph liefert! |
Ja, also ich habe die Aufgabe und keine Ahnung wie ich sowas angehen soll bzw versteh ich nichtmal richtig was gefragt ist.
Könnte mir da bitte jemand wenigstens einen Einstieg verpassen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
ich glaube man soll hier beweisen, dass die Verfahren, die wir in der VO gelernt haben (NW-Eckregel etc.), tatsächlich immer eine Basislösung generieren. Da gibt es dann zwei Dinge zu beweisen:
1.) Der Graph hat nur eine einzelne Zusammenhangskomponente. Das lässt sich dadurch beweisen, dass sowohl die Zeilen als auch die Spaltensummen nicht null sein können, es muss also jeder Knoten mindestens ein Mal besucht werden.
2.) Der Graph ist kreisfrei. Das er das ist wissen wir bereits. Ich glaube das liegt daran, dass immer die maximal mögliche Menge transportiert wird und dadurch Kreise ausgeschlossen sind. Wie man das beweisen soll weiß ich aber nicht, da steh ich selbst gerade an.
SG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 17.06.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
