Wichtige Begriffe der Graphentheorie
Aufspannende Bäume
Ein spannender bzw. aufspannender Baum ist ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle seine Knoten enthält. Spannende Bäume existieren somit nur in zusammenhängenden Graphen.
In kantengewichteten Graphen lässt sich als Gewicht eines spannenden Graphen die Summe seiner Kantengewichte definieren. Minimal spannende Bäume lassen sich mit Kruskal oder Prim bestimmen.
Kürzeste Wege
In einem kantengewichteten Graphen lässt sich der kürzeste Weg durch den Algorithmus von Dijkstra bestimmen.
Wälder
Ein Wald ist ein Graph, der aus einer Menge von Bäumen besteht, d.h. er ist nicht zusammenhängend und es gibt keine Kreise.
Mehrwegebäume
Ein Mehrwegebaum hat mehrere Elemente in einem Knoten gespeichert. B-Bäume sind Mehrwegebäume.
Konvexe Hülle
Gegeben ist eine Menge von Punkten in R2. Die konvexe Hülle ist der Graph, der sich bildet, wenn man ein Gummiband um alle Punkte legen und straff ziehn würde.
Man teilt in untere und obere konvexe Hülle auf.
Berechnung der unteren konvexen Hülle:
Zunächst werden alle Punkte aufsteigend nach ihrem x-Wert geordnet. Haben mehrere Punkte den gleichen x-Wert, so nimmt man für die untere konvexe Hülle den untersten Punkt, also dem mit dem kleinsten y-Wert, und den obersten Punkt für die obere konvexe Hülle.
Nun verbindet man die geordneten Punkte Q1, Q2, ... , Qn nacheinander. Bildet sich eine Einbuchtung nach innen, werden die inneren Punkte aus der konvexen Hülle entfernt.
Wir nehmen einen Stack zur Hilfe.
Q1 und Q2 werden in den Stack geschoben. Mit Q3 bildet sich eine Ecke nach unten. Q3 kommt also in den Stack. Q2, Q3 und Q4 bilden auch eine Ecke nach unten. Also kommt Q4 auch in den Stack. Bei Q5, Q6 und Q7 genauso.
Jetzt sind Q1, Q2, ... , Q7 im Stack. Nun kommt Q8. Q6, Q7 und Q8 bilden eine Ecke mit der Spitze nach oben. Deshalb wird Q7 aus dem Stack gelöscht. Dasselbe gilt für Q6 und Q5. Q3, Q4 und Q8 bilden wieder eine Ecke nach unten also kann Q8 jetzt auf den Stack gelegt werden.
Im Stack stehen die Punkte, die bis jetzt in der unteren konvexen Hülle enthalten sind: Q1, Q2, Q3, Q4 und Q8.
Berechnung der oberen konvexen Hülle:
Die obere konvexe Hülle wird im Prinzip genauso gestimmt. Man geht allerdings von rechts nach links und nimmt die Punkte deren Kanten in der konvexe Hülle nur Ecken mit der Spitze nach oben bilden.