Hallo,

die Aufgabenstellung ist so:

Alice loves foreign languages and wants to plan her course schedule for the following years. She is interested in the following courses: L15, L16, L22, L31, L32, L169, and L141. The course pre-requisites are:

- L15: (none)
- L16: L15
- L22: (none)
- L31: L15
- L32: L16, L31
- L169: L32
- L141: L22, L16

Find the sequence of courses that allows Alice to satisfy all the pre-requisites (use a graph).

Im Anhang findet man jetzt meine halb-fertige Lösung dazu. Aber wo man 2 Voraussetzungen braucht (das was nach den Zahlen immer hinter dem Doppelpunkt steht bei der Liste), weiß ich nicht was für Pfeile ich setzen soll... kann mir da jemand weiterhelfen? Wenn ich Pfeile von jeweils beiden Voraussetzungen setzen würde, würde man ja nicht erkennen, dass jeweils noch ein weiterer Kurs eigentlich notwendig wäre, deshalb verwirrt mich das.

Zitat von lisali

Wenn ich Pfeile von jeweils beiden Voraussetzungen setzen würde, würde man ja nicht erkennen, dass jeweils noch ein weiterer Kurs eigentlich notwendig wäre, deshalb verwirrt mich das.

Wieso nicht? Der entsprechende Knoten hat halt dann mehrere eingehende Kanten. Der Graph müsste also wie folgt aussehen:


Grüße,
Matthias

Weil ich da jetzt z.B. denken würde, dass ich auch nur L22 bräuchte, um zu L141 zu kommen und nicht noch die L16 als Kurs...

Zitat von lisali

Weil ich da jetzt z.B. denken würde, dass ich auch nur L22 bräuchte, um zu L141 zu kommen und nicht noch die L16 als Kurs...

Versteh ich nicht. Du musst doch nur schauen, welche Vorgänger ein Knoten im Graphen hat. Die entsprechenden Kurse müssen alle vor dem zum aktuellen Knoten gehörenden Kurs besucht werden. Der Graph modelliert also die Beziehung „ist direkte Voraussetzung für“ und nicht „ist einzige direkte Voraussetzung für“.

Grüße,
Matthias

Oder einfacher ausgedrückt: Jeder Pfeil an einer Blase ist Vorraussetzung für diese.

Hmm, ja, klar... jeder Pfeil impliziert eine Voraussetzung für eine Blase. Aber wenn ich 2 Voraussetzungen habe und ich habe z.B. A, B und C.

Und ich sage, dass A + B für C gebraucht wird... dann würde ich es rein logisch gesehen so zeichnen:

(a)--->(b)--->(c)

Und nicht:

(c)
^ ^
/ \
(a)----(b)

(edit: beide Pfeile sollen nach oben zu c zeigen von jeweils a und b)

Versteht ihr was ich sagen will?

Wenn du es so zeichnest und dabei sagst, dass jeder Pfeil eine Vorraussetzung für eine Blase ist, so würde ich aus deiner ersten Skizze schließen, das B Vorrausetzung für C ist und A Vorraussetzung für B. C hat also eine direkete Vorraussetzung B und eine indirekte Vorraussetzung A (weil ohne A kein B).
Bei der Version von Sven sieht man, dass C zwei direkte Vorraussetzungen hat (A+B), die allerdings keine Vorraussetzung für sich brauchen. C hat dort also keine indirtekte Vorraussetzung.

Du kannst solche Skizzen übrigens am besten in Codetags setzen

Hier nochmal ein etwas komplexeres Beispiel:

Code :

1 2 3 4 5 6 7

[F] //Direkte Vorraussetzung [D]+[E], indirekt [A]+[B]+[C]      /   \     [D] [E] //Direkte V. [B] bzw [C], indirekt [A] bzw keine    /       \   [B]     [C] //Direkte V. [A] bzw keine  / [A]