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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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
Weiter geht es mit dem sogenannten Knotengrad. Dieser beschreibt, wie viele Kanten in einen Knoten ein- beziehungsweise von einem Knoten ausgehen.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
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.
Grundbegriffe der Graphentheorie — häufigste Fragen
(ausklappen)
Grundbegriffe der Graphentheorie — häufigste Fragen
(ausklappen)-
Was ist die Graphentheorie?Graphentheorie ist das Teilgebiet der Mathematik und Informatik, das Graphen untersucht, also Strukturen aus Knoten und Kanten. Dabei betrachtet man zum Beispiel, ob Kanten gerichtet oder ungerichtet sind, ob Kanten Gewichte tragen und wie Knoten über Wege miteinander verbunden sind.
-
Wo findet man Graphen im Alltag?Graphen findet man im Alltag überall dort, wo Dinge durch Beziehungen oder Verbindungen vernetzt sind. Ein Verkehrsnetz kann man als Graph modellieren, indem Städte Knoten und Straßen Kanten sind. Auch soziale Netzwerke lassen sich so darstellen, wenn Personen Knoten und Kontakte Kanten sind.
-
Was ist ein Digraph?Ein Digraph ist ein gerichteter Graph, bei dem jede Kante eine Richtung hat und als Pfeil dargestellt wird. Dadurch kann man eine Verbindung nur in Pfeilrichtung nutzen, also zum Beispiel von A nach B, aber nicht automatisch auch von B nach A.
-
Was bedeutet es, wenn ein Graph schlingenfrei ist?Ein schlingenfreier Graph ist ein Graph ohne Schlingen, also ohne Kanten, die von einem Knoten wieder zu demselben Knoten zurückführen. Eine „Schlinge“ ist damit eine Selbstverbindung wie
oder 
, die in einem schlingenfreien Graphen nicht vorkommt.
Graphen verstehen
Die Grundbegriffe der Graphentheorie gehören zum Themenfeld Graphen und beschreiben einfache Netzwerke aus Knoten und Kanten. Du ordnest in diesem Themenfeld Verbindungen, Richtungen und Gewichte in Graphen und vergleichst verschiedene Arten von Netzwerken. So erkennst du, wie Beziehungen in einem Graphen aufgebaut sind und wie sich Wege und Verknüpfungen darstellen lassen. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.