Mathematik HTL 4/5, Schulbuch

274 Diskrete Mathematik Eine Bewertung eines Graphen ordnet jeder Kante genau eine reelle Zahl zu, ist also eine Funktion von der Menge der Kanten in die Menge der reellen Zahlen. Die Zahl, die einer Kante durch die Bewertung zugeord- net wird, nennt man die Bewertung dieser Kante. Ein bewerteter Graph ist ein Graph zusammen mit einer Bewertung dieses Graphen. Häufig zeichnet man die Ecken eines Graphen als Punkte der Ebene und die Kanten als Strecken zwischen diesen Punkten. Die Bewertung einer Kante wird zu dieser Kante geschrieben. Ein (n + 1)-Tupel von paarweise verschiedenen Ecken (a 0 , a 1 , …, a n ) eines Graphen ist ein Weg von a 0 nach a n in diesem Graphen, wenn je zwei aufeinander fol- gende Ecken die Eckpunkte einer Kante dieses Gra- phen sind. Ein Graph heißt zusammenhängend , wenn es von jeder seiner Ecken einen Weg zu jeder anderen gibt. Ein Graph U ist ein Untergraph eines Graphen G, wenn alle Ecken bzw. Kanten von U auch Ecken bzw. Kanten von G sind. Beispiele:  Der durch die Menge {a, b, c, d, e} von Ecken und die Menge {[a, b], [a, e], [b, c], [c, a], [c, d], [d, a]} von Kanten gegebene Graph G ist zusammen- hängend. (c, d), (c, a, d) und (c, b, a, d) sind Wege von c nach d in G. Der durch die Menge {a, b, c} von Ecken und die Menge {[a, b]} von Kanten gegebene Graph ist ein Untergraph von G. Dieser Untergraph ist nicht zusammenhängend, weil es in ihm keinen Weg von a nach c gibt.  In einer Firma gibt es Arbeiterinnen und Maschinen. Um darzustellen, welche Arbeiterin welche Maschine bedienen kann, betrachtet man jede Arbeiterin und jede Maschine als Ecke. Die Eckpunkte einer Kante sind jeweils eine Arbeiterin und eine Maschine, welche von dieser Arbeiterin bedient werden kann. Solche Graphen verwendet man, um das folgende Zuteilungsproblem zu lösen: Wie sollen die Arbeite- rinnen auf die Maschinen verteilt werden, sodass jede Arbeiterin beschäftigt ist und an einer Maschine arbeitet, die sie bedienen kann? Wir formulieren nun das Problem der kostengünstigsten Wasserleitung (von Seite 273) neu und geben ein Verfahren zu seiner (schnellen) Lösung an. Gegeben ist ein zusammenhängender bewerteter Graph G mit Eckenmenge E, Kantenmenge K und Bewertung w: K ¥ R . Wir suchen ein Minimalgerüst dieses bewerteten Graphen, das ist ein Untergraph von G mit derselben Eckenmenge E und einer Kantenmenge L a K so, dass der Unter- graph zusammenhängend ist und die Summe der Bewertungen der Kanten in L möglichst klein ist. 17 b a bewerteter Graph Weg a 3 a 2 b a 1 a 0 c d e zusammen- hängender Graph Untergraph a b c e a b d c A 1 M 1 M 2 M 3 M 4 M 5 A 2 A 3 A 4 A 5 Minimalgerüst Nur zu Prüfzwecken – Eigentum des Verlags öbv