Optimierungen und gewichtete Graphen

Arbeitsgrundlage: Graphentheorie 19 - Optimierungen.docx

Du hast gelernt, systematisch alle Lösungen eines Problems aufzulisten. Das kann helfen, eine geeignete Lösung zu finden. Oft möchte man die beste oder optimale Lösung suchen, aber welche ist die beste Lösung?

Dies hängt natürlich auch von den Kriterien ab. Zum Beispiel kann man bei der Wegsuche den kürzesten Weg bezüglich der Entfernung oder bezüglich der Zeit suchen. Oder den Weg mit minimaler Anzahl an Kreuzungen.

Gewichtete Graphen

Es gibt ungerichtete bzw. gerichtete Graphen mit gewichteten Kanten (z.B. Wegstrecken, Kosten, ...).

Ein Straßennetz optimieren

Nachfolgend ist ein Straßennetz als Graph dargestellt. Ziel ist es den kürzesten Weg von A nach B zu finden, also den Weg der minimalen Länge. Dazu braucht man auch die Längen der direkten Verbindungen zwischen zwei Ortschaften. In einem Graphen werden diese neben den Kanten angegeben. In solchen Graphen misst man die Länge des Weges nicht als die Anzahl der durchlaufenden Kanten, sondern als die Summe der Länge der durchlaufenden Kanten.

Beispiel: Der Weg ADE ist somit 15 + 40 = 55 km lang.

Optimierungsprobleme

Eine Aufgabenstellung mit mehreren Lösungen, in welcher man jeder Lösung dank einem Kriterium einen Wert zuordnen kann, nennt man Optimierungsproblem. In der Fachsprache nennt man die Werte der Lösungen die Kosten der Lösungen. Wenn man eine Lösung mit den minimalen Kosten suchen, spricht man von einem Minimierungsproblem. Sucht man die Lösung mit den maximalen Kosten, von einem Maximierungsproblem.

Aufgabe 3: Saarländische Städte

Erstellen Sie den gewichteten Graphen der saarländischen Städte.