Theoretische Informatik

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.

Graphen: gerichtet und ungerictet
direkt ins Video springen
Gerichtete und ungerichtete Graphen

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.

Graphenthorie: Kantengewichte
direkt ins Video springen
Gewichtete Graphen

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

Weiter geht es mit dem sogenannten Knotengrad. Dieser beschreibt, wie viele Kanten in einen Knoten ein- beziehungsweise von einem Knoten ausgehen.

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.

Knotengrad, Quelle und Senke
direkt ins Video springen
Knotengrad bei ungerichteten und gerichteten Graphen

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.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.