Einsendeaufgaben EA-Besprechung SS 2018 EA1 00852 (07.06.2018)

Hochschulabschluss
Bachelor of Engineering
Hallo,

anbei meine ersten Ergebnisse. Muss leider zugeben, dass ich mithilfe des Skripts überhaupt nicht gut voran komme.

Aufgabe 1
a.) Nein, da Voraussetzung ist, dass der Digraph zyklenfrei ist. Bei einem starken Zusammenhang gibt es jedoch auch Zyklen
b.) Ich würde hier Ja sagen, da sonst keiner der Knoten einen Nachfolger besitzt und somit eine topologische Sortierung nicht möglich bzw. nicht notwendig ist.
c.) Ja siehe Aufgabenteil a
d.) Ja, da eine bipatiter Digraph zyklenfrei ist und somit die Voraussetzung für eine topologische Sortierung erfüllt
e.) Komme auf 4 Reihenfolgen

Aufgabe 2
Keine Ahnung

Aufgabe 3
Keine Ahnung. Mich verwirrt hier vor allem, dass obwohl laut Aufgabenstellung 3m³ in 1 eingeleitet werden scheinbar noch 2m³ von 6 zu 4 dazu kommen.

Aufgabe 4
a.) Zeichnen des Digraphen passt. Gibt auch glaube ich eine Übungsaufgabe im moodle dazu mit exakt den gleichen Werten und Knoten
b.) Habe hier Probleme mit der ermittlung der Mengen. Die Beispielerklärung im Skript ist recht kurz gehalten und beinhaltet natürlich nicht den Sonderfall mit den Umladeknoten. Die Kosten muss man ja ledilich übernehmen bzw. falls keine Verbindung zwischen zwei Knoten besteht, verwendet man für die Kosten ein Unendlichzeichen.

Tu nur ich mich mit den Skripten so schwer? Finde die Erläuterung sehr komplex und größtenteils nicht hilfereich. Frage mich wirklich wie man mit den Skripten diese Klausur (SS2017) hätte lösen sollen.

Hoffe ihr könnt mir hier weiterhelfen :)
 
Hallo,

bei 1b) würde ich nein sagen, ich hatte dabei an einen '"Wald" gedacht, die Bäume an sich können topologisch sortiert werden. Auch redet das Skript von mindestens einer Quelle (S.31)

bei 2 a:
Wie der Algorithmus arbeitet, ist mir klar, nur nicht was er berechnet. Je nachdem, mit welchem Knoten ich anfange komme ich zum Teil auf unterschiedliche Ergebnisse, und das sollte ja nicht der Fall sein. Vielleicht habe ich auch bei den Knotengewichten (habe ich im Skript nirgends gefunden) ein Fehler gemacht, und die werden ja summiert (bk) bzw. bilden das Abbruchkriterium.
Bei "meinem" Baum kann es auch dazu kommen, das ohne vorherigen Abbruch nur noch ein Knoten übrigbleibt, der dann natürlich d(i)=1 von Schritt 1 nicht erfüllen kann, dafür ist aber kein Abbruch vorgesehen. (Auch mit einer Kette probiert).

den Rest habe ich mir noch nicht angeschaut, hatte mich an 2a aufgehängt (wobei 2b schon mein nächstes Problem ist, hatte ich im Skript schon nicht wirklich verstanden).
 
Man sollte die Aufgabe auch richtig lesen :-(
Bei 2a hab ich beim x-ten mal lesen meinen Fehler gefunden
Der Algorithmus wählt (beliebigen) Anfangs- oder Endknoten
Wenn das Knotengewicht mindestens so hoch wie die Hälfte aller Knotengewichte des Baumes ist, bricht er ab.
Zu dem einen verbundenen Knoten wird das Knotengewicht das gewählten Knotens hinzu addiert (hier lag mein Fehler)
Der gewählte Knoten wird aus dem Baum entfernt (die Summe der Knotengewichte ändert sich aber nicht).

Beim Abbruch hat der gewählte Knoten mindestens die Hälfte aller möglichen Knotengewichte zusammen bekommen. Über die Interpretation bin ich mir noch nicht sicher

Bei 2b würde ich O(m) sagen.
 
Man sollte die Aufgabe auch richtig lesen :-(
Bei 2a hab ich beim x-ten mal lesen meinen Fehler gefunden
Der Algorithmus wählt (beliebigen) Anfangs- oder Endknoten
Wenn das Knotengewicht mindestens so hoch wie die Hälfte aller Knotengewichte des Baumes ist, bricht er ab.
Zu dem einen verbundenen Knoten wird das Knotengewicht das gewählten Knotens hinzu addiert (hier lag mein Fehler)
Der gewählte Knoten wird aus dem Baum entfernt (die Summe der Knotengewichte ändert sich aber nicht).

Beim Abbruch hat der gewählte Knoten mindestens die Hälfte aller möglichen Knotengewichte zusammen bekommen. Über die Interpretation bin ich mir noch nicht sicher

Bei 2b würde ich O(m) sagen.

Kannst du mir eventuell sagen wie ich die Gewichte/Bewertung = b der einzelnen Knoten berechne? Danke!
 
Hallo,
2 a)
für das Beispiel hatte ich abwechselnd den Knoten die Gewichte 1 und 2 zugewiesen, ob das so richtig ist, keine Ahnung, habe dazu nirgends etwas gefunden.
Bei Schritt 1 wird ein Anfangs- oder Endknoten gewählt (alle anderen haben ja d(i)>1 ).
Im Schritt 2 wird dem Knoten, der mit dem gewählten Knoten verbunden ist, das Knotengewicht von dem gewählten Knoten hinzu addiert (bk:=bk+bi).
Dadurch ändert sich die gesamte Summe der Knotengewichte nicht, obwohl der gewählte Knoten i dann "gestrichen" wird. Die Summe muss im ersten Schritt daher nur einmal berechnet werden (hoffe jedenfalls, dass ich da keinen Gedankenfehler gemacht habe. Der Algorithmus bricht also ab, sobald der Knoten (im Laufe) der Zeit mindestens die Hälfte der Knotengewichte erreicht hat.
Mit der Interpretation tue ich mich allerdings schwer.
2 b)
Inzwischen tendiere ich zu O(n), aber sehr unsicher, mit dem Landauschen Symbol hab ich so meine Probleme.

3 a)
Ist gültiger Fluss; Bedingung: Zu- und abfließende Ströme müssen gleich sein.
3 b)
Komme auf Flussstärke 7
3 c)
V1={1,2,3,4,6} V2={5,7,8,9}
3 d)
Steigerung auf 10 möglich

Bei 4 bin ich noch dran, (Übungs-)Aufgabe B0801 ist ähnlich, aber auf die leicht anderen Pfeile achten.
 
Hallo,

hat jemand mittlerweile die Aufgabe 3 komplett?
a) habe ich das richtig verstanden, dass der Fluss wie folgt fließt:
Knoten 1-3 (Menge 3), 3-4 (3), 4-8 (3), 8-6 (2), 8-9 (1), 6-4 (2), 4-8 (2), 8-9(2). Das heißt die Verbindungen 4-8 und 8-9 werden 2 mal durchlaufen und in Summe ergibt es dann die in der Aufgabe angegebenen Werte.
Damit wären alle Minimalbedingungen erfüllt, kein Maximum überschritten und der Fluss somit zulässig.
b) ist es möglich bei einem Knoten eines Iterationsschritts 2 Quellen anzugeben? D.h. in diesem Fall für Knoten 4 Knoten 3 und 6 als Quellen?
 
Hallo jdizzle
a) praktisch hast du mit dem 2x durchlaufen recht. Aber besser nicht im zeitlichen Ablauf sehen (wie du in deinen Werten).
Um die Zulässigkeit zu überprüfen: Sind Mindest- und Maximalmengen eingehalten? Ja (Hatte mir die Flussmengen der Aufgabenstellung der besseren Übersicht in das Diagramm geschrieben, dann sieht man es sofort) Und ist die Bilanz jedes einzelnen Knotens (außer Quellen und Senken) ausgeglichen? Ja, z.B. Knoten 4: Zu 3 ( von K.3) + 2 (von K.6)=5; Ab 5 (nach Knoten 8), zu und ab sind gleich, also passend.
Ob es technisch Sinn macht, dass das Abwasser im Kreis fließt, darüber würde ich mir hier keine Gedanken machen.
b) will ich erstmal nicht ausschließen; würde ich aber nicht machen. Zum einen fehleranfälliger; zum anderen wüsste ich erstmal nicht, wie die doppelte Angabe bei der Iteration "verarbeitet" werden würde. Was du durch zwei Angaben (ggf. einen Schritt eingespart) hast, verbrauchst du vermutlich an Zeit bei dem umfangreicheren Bearbeiten.
 
zu 4b)
hier habe ich 1-4: 100; 2-4: 50; 3-6: 70; 4-7: 80; 4-6: 70; 6-8: 70
Umladehafen 5 also gar nicht benutzt.
 
Hallo hedgehog,

vielen Dank für die schnelle Antwort.
Könntest du evtl. bitte Screenshots von den Iterationsschritten für Aufgaben 3b/d schicken?
Ich komme nicht darauf wie es ohne die Lösung mit den 2 Quellen aussehen soll.
 
Hallo jdizzle,
ich habe einfach dann dem Knoten eine "Quelle" zugeordnet und die andere erstmal außer acht gelassen und ggf. im nächsten Schritt berücksichtigt.
Vermute (nicht wirklich überprüft; und ob im Skript etwas dazu steht weiß ich jetzt nicht), dass das Ergebnis in Bezug auf die Aufteilung des Flusses auf die verschiedenen Leitungen (nicht der Gesamtfluss, der müsste immer gleich sein) auch von der Reihenfolge, wie die Nachfolgerknoten gewählt werden, abhängen kann.
Hoffe ich habe keinen Fehler drin
 

Anhänge

  • Graphik - EA1 - A3.pdf
    41 KB · Aufrufe: 64
Hallo,
3b) ich komme auf Flussstärke 6
3d) und hier dann entsprechend auf 9m³
 

Anhänge

  • CCF_000026.pdf
    451,8 KB · Aufrufe: 21
Hallo NiMa87,

falls ich nichts übersehen habe, hast du die Reduzierung 8-6 um 1 nicht gemacht, somit könnte 8-9 um 1 erhöht werden und du wärst auch bei 7 (der Fluss 1-2-4 müsste dann auch um 1 größer werden).

hedgehog
 
Zuletzt bearbeitet:
Hallo Philipp,

wild.:haumichwech:
und hoffentlich richtig.

hedgehog
 

Anhänge

  • Graphik - EA1 - A4a.pdf
    28,6 KB · Aufrufe: 28
Zurück
Oben