Grundbegriffe der Graphentheorie
Du willst wissen was Graphen sind? Der Knotengrad und gewichtete und gerichtete Graphen sind dir auch kein Begriff? Genau das erklären wir dir hier anhand von vielen Beispielen.
Inhaltsübersicht
Graphentheorie – Graph G = (V, E)
Beginnen wir mit den Bestandteilen eines Graphen. Ein Graph G besteht aus einer Menge an Knoten V und einer Menge aus Kanten E. Die Knoten werden mit Kanten verbunden, wobei eine Kante immer genau zwei Knoten miteinander verknüpft. Wie du einfach darstellen kannst welche Knoten miteinander verbunden sind zeigen wird dir in unseren Videos zur Adjazenzmatrix und zur Inzidenzmatrix .
Gerichtete und ungerichtete Graphen
Allgemein gilt es zwischen gerichteten und ungerichteten Graphen zu differenzieren. Der Unterschied liegt in der Art der Kanten, die die Knoten verbinden. Ist eine Verbindung zweier Knoten ein Pfeil, so ist der Graph gerichtet und die Kante darf nur in einer Richtung genutzt werden. Wie du siehst, ist es dir im gerichteten Graphen beispielsweise nicht erlaubt, vom Knoten B zum Knoten A zu gehen, da die Kante nur in die entgegengesetzte Richtung zeigt.
Wird eine Kante im Graphen hingegen als einfache Verbindung zwischen zwei Knoten dargestellt, ist der Graph ungerichtet und es muss nicht auf die Richtung geachtet werden.
Stark und schwach zusammenhängende Graphen
Ein entscheidendes Merkmal von Graphen ist der Zusammenhang. Was bedeutet das? Schauen wir uns das doch einfach an einem Beispiel an.
Ein ungerichteter Graph gilt als zusammenhängend, wenn es zu jedem beliebigen Knotenpaar einen Weg vom einem zum anderen Knoten gibt. Jeder Knoten ist somit erreichbar.
Nicht zusammenhängende Graphen erkennt man an isolierten Knoten oder ganzen Knotengruppen.
Beim gerichteten Graphen musst du auf die Kantenrichtung achten. Wie du siehst führt in unserem Beispiel kein Weg zum rechten oberen Knoten. Würde man die Richtungen der Kanten ignorieren wäre aber trotzdem jeder Knoten erreichbar. Einen solchen Graphen nennt man schwach zusammenhängend.
Stark zusammenhängend wäre der Graph, wenn es eine zusätzliche gerichtete Kante zu dem unerreichbaren Knoten gäbe.
Gewichtete Graphen
Als nächstes zeigen wir dir, wie ein gewichteter Graph aussieht.
Dieser Graph zeigt beispielsweise verschiedene Städte in Deutschland. Stell dir vor die Kanten des Graphen beschreiben die Route, die du von einer Stadt zur anderen fahren musst. Noch kannst du nicht entscheiden welche Strecke länger ist. Wir fügen also Kantengewichte hinzu, die in unserem die Abstände in Kilometern darstellen.
Jetzt kannst du ganz einfach erkennen, dass die Strecke von Berlin nach München länger ist, als die Strecke von Berlin nach Hannover.
Knotengrad bei ungerichteten Graphen
Bei einem ungerichteten Graphen ist der Grad eines Knoten die Anzahl der Kanten, die mit dem Knoten verbunden sind. Alle diese Knoten werden in der Graphentheorie als benachbart bezeichnet. In unserem Beispiel siehst du einen ungerichteten Graphen. Im Knoten steht jeweils der Grad.
Knotengrad bei gerichteten Graphen
Beim gerichteten Graphen hingegen wird für jeden Knoten zwischen Eingangsgrad und Ausgangsgrad unterschieden, sprich wie viele Knoten in den Knoten hinein beziehungsweise aus dem Knoten herausführen. Der Knotengrad spielt eine wichtige Rolle um das Königsberger Brückenproblem zu lösen.
In den Knoten steht jeweils zuerst der Eingangsgrad, und dann der Ausgangsgrad. Schau dir den Knoten rechts oben an. Es führen zwei Pfeile in ihn hinein und keiner heraus, also ist der Eingangsgrad 2 und der Ausgangsgrad 0. Einen Knoten ohne Eingangskanten nennt man Quelle. Ein Knoten ohne Ausgangskanten wird Senke genannt.
Nun kennst du alle wichtigen Grundlagen für Graphen und deinem Einstieg in die Graphentheorie sollte nichts mehr im Wege stehen.