5 - Graphen

Knoten werden nummeriert

Kanten eines Graphen können gerichtet oder ungerichtet sein

• gerichtete Kante kann nur in eine Richtung durchlaufen werden

• wenn Kanten gerichtet: gerichteter Graph, orientierter Graph oder Diagraph

Kanten eines Graphen können gewichtet oder ungewichtet sein

• Gewicht einer Kante beschreibt Kosten, um die Kante zu durchlaufen

Schleife: Kante mit glechen Start- und Zielknoten

parallele Kante: Wenn mehrere Kanten vom Start- zum Zielknoten führen

Pfad: Folge von Knoten, in der zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind

Zyklus: Pfad, bei dem Start- und Endknoten identisch

Graph mit mindestens einem Zyklus

• zyklisch

ansonsten: antizyklisch

zusammenhängend: ungerichteter Graph, bei dem es einen Pfad von jedem beliebigen Knoten zu jedem anderen Knoten gibt

stark zusammenhängend: gerichteter Graph, bei dem es gerichteten Pfad von jedem beliebigen Knoten zu jedem anderen Knoten gibt

schwach zusammenhängend: gerichteter Graph, bei dem zugehöriger ungerichteter Graph zusammenhängend ist

beschreibt, welche Knoten eines Graphen durch Kante verbunden sind

besitzt für jeden Knoten eine Zeile und Spalte

Eintrag in der i-ten Zeile und j-ten Spalte beschreibt Kante vom i-ten zum j-ten Knoten

bei ungewichteten Graphen: alle Einträge entweder 0 (keine Kante) oder 1 (Kante)

bei gewichteten Graphen entspricht Eintrag Kantengewicht

zur Bestimmung der Eigenschaften des Graphen

• Adjazenmatrix eines ungerichteten Graphs ist symmetrisch

• Sind alle Einträge entlang der Hauptdiagonalen 0, so ist der Graph schleifenfrei

• Ist Graph (stark) zusammenhängend, so ist Matrix irreduzibel, d.h. kann durch Tauschen von Spalten und Zeilen nicht in eine untere Blockdreiecksstruktur überführt werden

• Aus den Potenzen der Adjazenmatrix kann Pfadlänge zwischen zwei Knoten berechnet werden

vollständige Adjazenmatrix hat Speicherkomplexität von 0(n2), wobei n der Anzahl der Knoten entspricht

Zur Speicherung werden spezielle Darstellungen für dünnbesetzte Matrizen verwendet

Möglichkeit, Graphen zu repräsentieren/speichern

Für jeden Knoten: Liste der Nachfolger

Für Listen der Nachfolger: einfach verkettete Listen

Listen der Nachfolger für jeden Knoten: Speicherung als Array

In Anwendugen: Teilordnung von Elementen durch Beziehungen zwischen zwei Elementen

• Darstellung durch azyklischen, gerichteten Graphen

• Knoten entsprechen Elementen und Kanten beschreiben Beziehung der Form

Topologisches Sortieren: Vollständige Ordnung (lineare Anordnung) der Elemente/Knoten gesucht

• nicht eindeutig -> mehrere Anordnungen für einen Graphen möglich

• Sortierung kann Graphen auf Zyklenfreiheit prüfen

Baum ist azyklischer, zusammenhängender Graph

Spannbaum: Teilgraph eines ungerichteten Graphen, der Baum ist und alle Knoten eines Graphen enthält

• existieren nur für zusammenhängende Graphen

• unterschiedliche Varianten

Gewicht des Graphen: Summe aller Kantengewichte in gewichtetem Graphen

Spannbaum ist minimal, wenn:

• für Graphen kein Spannbaum mit geringerem Gewicht existiert

Algorithmus von Boruvka

Algorithmus von Prim

Algorithmus von Kruskal

• 1) Initialisiere leeren Spannbaum

• 2) Speichere Kanten des Graphen in Liste und sortiere sie nach aufsteigendem Kantengewicht

• 3) Solange Liste nicht leer

  • a) Entferne die Kante mit kleinstem Kantengewicht aus der Liste

  • b) Wenn dadurch kein Kreis entsteht, füge die Kante dem Spannbaum hinzu

Traversierungsverfahren bilden Grundlage für komplexere Algorithmen

• Tiefensuche

  • Pfad vollständig in Tiefe durchlaufen, bevor abzweigende Pfade durchlaufen werden

• Breitensuche

  • Alle Nachfolger besuchen, die vom Ausgangsknoten erreicht werden, bevor Folgeknoten durchlaufen werden

Implementierung

• Implementierung entweder rekursiv oder iterativ (mit Stack)

• Liste entdeckter Knoten muss verwaltet werden

Verfahren A (iterativ, explizite Speicherverwaltung)

Verfahren B (rekursiv, implizite Speicherverwaltung)

Implementierung

• iterativ mit Warteschlange

• Liste entdeckter Knoten muss verwaltet werden

Verfahren

bei ungewichteten Graphen (alle Gewichte=1) ist kürzester Pfad derjenige, mit geringster Knotenanzahl

Verfahren zur Berechnung des kürzesten Pfads

• Dijkstra-Algorithmus

• A*-Algorithmus

• Bellman-Ford-Algorithmus

zählt zu Greedy-Algorithmen

Idee: Kante folgen, die kürzesten Pfad vom Startknoten verspricht

Verfahren

A*-Algorithmus

• Dijkstra-Algorithmus muss ggf. sehr viele Knoten durchlaufen

• A*-Algorithmus erweitert Dijkstra um Heuristik (Schätzfunktion), die Abstand zum Zielknoten schätzt, um zielgerichteter zu suchen

Bellman-Ford-Algorithmus

• Dijkstra-Algorithmus kann nicht mit negativen Kantengewichten umgehen

• -> Anwendung Bellman-Ford-Algorithmus