Prim Graph Archive - Blogofant

Voraussetzungen für einen Baum, Definition eines Baumes Ein Baum in der Graphentheorie muss zwei Voraussetzungen erfüllen: Der Baum muss zusammenhängend sein, dies bedeutet es dürfen nicht mehrere Bäume entstehen. Bei mehreren Bäumen spricht man von einem Wald. Es darf keinen Kreis (oftmals auch Zyklus genannt) geben, das heißt der gesamte Graph muss kreisfrei sein. Ein Knoten, welcher meist als Startknoten gilt, wird Wurzel genannt. Dabei ist es allerdings egal ob die Wurzel oben oder unten ist. Hierbei spricht man auch von einem Wurzelbaum. Zudem ist ein Graph mit weniger als zwei Blätter kein Baum > Jeder Baum besitzt zumindest zwei Blätter. Eine Unterscheidung sowie Definition von Graphen sowie deren Bestandteile gibt es im Blogbeitrag über Nodes, Edges, Arcs & Vertex. Algorithmus für Kreisfreiheit Der DFS Algorithmus kann einen Graphen auf Kreise untersuchen: Falls ein Konten einen benachbarten Knoten (außer dessen Eltern, also den Knoten von welchem er aktiviert wurde) hat, der bereits besucht wurde, so existiert ein Kreis. Ansonsten gilt der Graph als kreisfrei. Wald, Baum und Blatt Ein ungerichteter Graph der kreisfrei ist heißt Wald. Wenn der gesamte Graph zusammenhängend ist, spricht man von einem Baum. Jeder Baum ist zudem bipartit, da er sich in zwei Mengen teilen lässt. Dies kann mittels abwechselnd farbigen Ebenen gut demonstriert werden. Die Wurzel bekommt Farbe A, die nächste Ebene (E1) Farbe B, die nächste Ebene (E2, welche nur zur Ebene 1 verbunden ist) wieder die Farbe A. Somit wechseln sich die Farben nach Ebenen ab, sodass zwei Farbmengen entstehen. Aufgrund der Definition, dass ein Baum kreisfrei sein muss, ergibt sich zwingend, dass ein Baum bipartit ist. Ein Blatt ist ein einzelner Knoten eines Baumes mit deg1. Die einzelnen Ebenen eines Baumes werden auch als Höhe bezeichnet. Dabei bezeichnet die Höhe das Maximum der Länge aller Wege vom Wurzelknoten zu einem beliebigen anderen Knoten. Beweis: Baum ist bipartit Ein Graph gilt als bipartit, wenn er keine Kreise von ungerader Länge besitzt. Ein Baum besitzt allerdings per Definition keine Kreise, sodass er bipartit sein muss. Binärbäume Binärbäume haben einen Knotengrad kleiner gleich drei. Dies bedeutet, dass ein Konten mit einem Vorgänger maximal zwei Nachfolger aufweisen kann. Bei zwei Möglichkeiten wird dies gerne als binär (also 0 oder 1) bezeichnet, wobei binär in diesem Falle 1 Blatt oder 2 Blätter ausgehend von dem Knoten bezeichnet. Die Anzahl der Blätter eines Binärbaums ist 2^h wobei h der Höhe entspricht. Die Anzahl der Knoten ist 2^(h+1)-1 und ein vollständiger Binärbaum hat maximal 2^i Knoten. Vollständig bedeutet, dass alle Blätter die gleiche Tiefe besitzen. Anzahl der Kanten eines Baumes Ein Baum (Graph G (V,E)) mit |V|n besitzt genau n-1 Kanten (|E| n-1). Würde der Baum mehrere Kanten besitzen, dann würde ein Kreis entstehen und die Voraussetzungen für einen Baum würden verletzt sein. Würden weniger Kanten existieren, wäre der Baum nicht zusammenhängend, wodurch ebenso die Definition eines Baumes verletzt sein würde. Spannbaum und Teilgraphen Ein spannender Baum ist ein Teilgraph von G(V,E) und wird mit T(V',E') bezeichnet. Der spannende Baum besteht also aus der Knotenmenge V', welche lediglich eine Teilmenge von der gesamten Knotenmenge V des Graphen ist, sowie der Kantenmenge E', welche ebenso lediglich eine Teilmenge ist. Die Definition eines spannenden Baumes besagt allerdings, dass jeder Knoten, nicht jedoch jede Kante besucht werden muss. Dies bedeutet, dass V' V ist, sodass alle Knoten im Teilgraphen verwendet werden. Zudem muss der Graph ein Baum sein. Graph muss ein Baum seinTeilgraph muss alle Knoten des Graphen enthalten, sodass wenn G(V,E) gilt T(V, E') beziehungsweise wenn T(V',E') muss V'V entsprechen. Minimaler Spannbaum (MST - Minimum spanning tree) Der minimale Spannbaum findet sich in vielen praktischen Anwendungen wieder. Ziel ist es nicht nur jeden Knoten wie beim Spannbaum zu besuchen, sondern auch die billigsten Kanten zu benützen. Die billigsten Kanten unterliegen gewissen Kosten (dem Kantengewicht), welche z.B. Wegkosten, Zeitkosten oder sonstige Kosten darstellen können. Der minimale Spannbaum kann mit zwei Algorithmen gut gelöst werden: Einerseits dem Algorithmus von Kruskal sowie dem Algorithmus von Prim. Beide Algorithmen liefern den kostengünstigsten spannenden Baum. Aufgrund diesen Algorithmen können auch viele weitere Probleme gelöst werden, zum Beispiel das Problem des Handlungsreisenden (Travelling Salesman Problem, TSP). Algorithmus von Prim Beim Algorithmus von Prim wird zuerst ein Startknoten ausgewählt. Von diesem Knoten aus, wird die kostengünstigste Kante verwendet. Danach befinden sich zwei Knoten in Graphen. Von diesen beiden Knoten ausgehend, sieht man sich alle Nachbarn an, und nimmt jene Kante mit den geringsten Kosten, welche von den beiden bestehenden Knoten erreichbar ist. Der Algorithmus von Prim funktioniert also iterativ, wobei in jedem Schritt der kostengünstigste Nachbar von allen bereits bestehenden (in die Lösung aufgenommenen) Knoten. Dies entspricht der billigsten Weise den Baum zu erweitern. Bei diesem Algorithmus besteht zu jedem Zeitpunkt nur ein Baum. Algorithmus von Kruskal Dieser Algorithmus nimmt zuerst die gesamte Kantenmenge und sortiert sie nach deren Kantengewichten. Dabei wird jeder Kante ein Namen gegeben um sie besser zu unterscheiden. In einem ersten Schritt wird die kostengünstigsten Kante verwendet. Danach die zweit kostengünstigste Kante, usw. Einzige Bedingung ist, dass sich keine Kreise bilden dürfen. Dies bedeutet, dass sich zwischenzeitlich mehre Bäume (ein Wald) entstehen können. Allerdings wird jede Kante angesehen, sodass am Ende durch den Algorithmus von Kurskal ein einzelner Baum entsteht. Sollte die gerade angesehene Kante zu einem Kreis führen, wird diese übersprungen und es wird mit der nächst teureren fortgefahren.

Verschlagwortet: Prim Graph

Baum – Graphen

Werbung / Advertisement

Top Ratings

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Werbung / Advertisement

Neueste Beiträge

Werbung / Advertisement

Werbung / Advertisement