Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphentheorie - Coggle Diagram
Graphentheorie
-
EULER UND KANTENZÜGE
Kantenfolge (eine Folge von Kanten hintereinander, Kanten können beliebig oft genommen werden)
offener Kantenzug (unterschiedlicher Start und Endpunkt aber NICHT ALLE Kanten im Graph werden genutzt)
geschlossener Kantenzug (gleicher Start und Endpunkt aber NICHT ALLE Kanten im Graph werden genutzt)
Eulerwege (unterschiedlicher Start und Endpunkt, ALLE Kanten im Graphen vorhanden, 2 Knoten MÜSSEN einen ungeraden Grad haben)
Eulerkreise (gleicher Start- und Endpunkt, ALLE Kanten im Graph vorhanden, ALLE Knoten haben einen geraden Grad)
-
BRIEFTRÄGER-PROBLEM
-
kürzester Weg durch eine Stadt, jede Straße muss min. einmal benutzt werden
Vorgehen:
- Gradzahlen der Knoten prüfen
- immer zwei ungerade Knoten durch zusätzliche Kanten verbinden, sodass nur noch gerade Knoten im Graph sind, DABEI die KÜRZESTEN Kantensummen nehmen
Eulerkreis als Lösungsansatz, die Summe aller nacheinander durchlaufenen Kanten ist der kürzeste Weg
SPANNBÄUME
Spannbäume allgemein: Ein Teilgraph in einem Graphen, der alle Knoten verbindet, sodass er zusammenhängend ist, es werden nicht alle Kanten benötigt
Es gibt in einem Graphen mehrere mögliche Spannbäume. Berechnung ( Anzahl der Knoten ^Anzahl der Knoten -2 )
Minimaler Spannbaum: Der Teilgraph, mit dem geringsten Gesamt-Kantengewicht
Kruskal Algorithmus: Immer die nächsten kleinsten/günstigsten Kanten zum Teilgraph hinzufügen, falls sich dadurch ein Kantenkreis bildet, die Kante rausstreichen. Weiter Vorgehen, bis alle Knoten im Teilgraph enthalten sind
