Mathematik HTL 4/5, Schulbuch

273 7.2 Graphen Ich lerne Graphen kennen und ich lerne gewisse Situationen durch sie zu modellieren. Ich lerne in einem zusammenhängenden bewerteten Graphen ein Minimalgerüst zu finden. Ich lerne in einem zusammenhängenden bewerteten Graphen den kürzesten Weg von einer Ecke zu jeder anderen zu finden. Ich lerne zu entscheiden, ob es in einem zusammenhängenden Graphen eine Eulertour gibt und, wenn ja, eine solche zu ermitteln. Minimalgerüste Einige Dörfer sollen mit einer Wasserleitung versorgt werden. Eines der Dörfer hat bereits einen Anschluss an die Wasserleitung. Für je zwei Dörfer, die direkt mit einer Wasserleitung verbunden werden können, sind die Kosten für deren Errichtung ermittelt worden. Es soll ein Leitungsnetz bestimmt werden, durch das alle Dörfer mit Wasser versorgt werden und dessen Errichtung möglichst wenig kostet. Diese Informationen können wir gut veranschau- lichen, wenn wir jedes Dorf durch einen Punkt in der Ebene darstellen und die Strecke zwi- schen zwei Punkten einzeichnen, falls eine direkte Leitung zwischen diesen Dörfern mög- lich ist. Die Kosten (in Millionen Euro) für die entsprechende Wasserleitung schreiben wir über diese Strecken. Wir haben dann die Daten durch einen bewer- teten Graphen dargestellt. Die Dörfer sind sei- ne Ecken, die Strecken zwischen zwei Ecken heißen Kanten und die zu den Kanten geschriebe- nen Zahlen sind die Bewertungen dieser Kanten. In unserem Beispiel gibt es 6 Ecken (Dörfer) und 9 Kanten (mögliche direkte Leitungen zwischen Dörfern). Die Bewertung einer Kante gibt an, wie viele Millionen Euro der Bau der entsprechenden Leitung kosten würde. Zum Beispiel kostet der Bau einer Wasserleitung zwischen den Dörfern c und d 1,2 Millionen Euro. Damit jedes Dorf mit Wasser versorgt wird, müssen wir Kanten so auswählen, dass man entlang der ausgewählten Kanten von jedem Dorf in jedes andere kommt. Dazu könnten wir zum Bei- spiel alle Kanten auswählen. Die Auswahl soll aber so getroffen werden, dass die Kosten mög- lichst klein sind, also die Summe der Bewertungen der ausgewählten Kanten möglichst klein ist. Da es nur 6 Ecken und 9 Kanten gibt, könnten wir alle Möglichkeiten für eine Wasserleitung, die alle Dörfer versorgt, angeben, für jede Möglichkeit die Kosten berechnen und dann eine mit minimalen Kosten auswählen. Allerdings wäre der Aufwand dafür schon ziemlich groß. Die Graphentheorie sucht daher nach Verfahren („Algorithmen“), die für Graphen formulierte Probleme mit möglichst geringem Auf- wand lösen. Bevor wir einen Algorithmus für unser Problem angeben, vereinbaren wir einige Begriffe und Bezeichnungen: Ein Graph ist durch eine endliche Menge von Ecken und eine Menge von Kanten zwischen je zwei Ecken des Graphen gegeben. Sind a und b Ecken, dann schreiben wir [a, b] für die Kante zwischen a und b. Die Ecken a und b heißen dann die Eckpunkte der Kante [a, b]. a e d c f b 0,9 1,2 1,9 0,8 1,0 1,2 1,5 2,1 1,8 [a,b] b a Graph, Ecke, Kante Nur zu Prüfzwecke – Eigentum des Verlags öbv