Graphen einfach erklärt - Graphentheorie
Soso der Herr Graf lässt sich jetzt auch mal Blicken.
Ouh ne.
Mein Fehler.
Ich mein natürlich Graphen.
Damit mein ich aber nicht die komischen Kurven da in Mathe.
Wir kümmern uns heute um die wunderschönen Graphen in der Informatik.
Wie die aussehen, sehen wir gleich!
So wat is jetzt so en Graph?
Ein Graph is grob gesagt eine grafische Darstellung von Objekten und deren Beziehungen.
Die Objekte sind dabei einfach so Kreise und werden als Knoten bezeichnet.
Diese können zum Beispiel Objekte wie Zahlen oder auch Namen enthalten.
Die Beziehungen sind die Linien zwischen diesen Knoten und werden als Kanten bezeichnet.
Solche Darstellungen kennt ihr jetzt schon von den Automaten und von Binärbäumen.
Dazu haben wir auch ganz viele schöne Videos für euch auf unserer Website!
Ein Graph kann beispielsweise dazu verwendet werden, um Flugverbindungen zwischen Städten
darzustellen.
Die Knoten stellen dabei die jeweilige Stadt dar und die Kanten die jeweilige Strecke zwischen
den Städten.
Im Groben können wir zwischen gerichteten und ungerichteten Graphen unterscheiden.
Bei einem gerichteten Graph kann mit einer Kante nur in eine Richtung gehen.
Eine Kante wird dabei durch einen Pfeil dargestellt.
Bei einem gerichteten Graphen heißen zwei Knoten stark verbunden, falls es einen Weg
von einem Knoten zum anderen und auch wieder zurück gibt.
Durch einen gerichteten Graph kann man perfekt Aktionen skizzieren.
Das aufrufen der Website von Simple Club könnte man beispielsweise so machen:
Wir brauchen für jedes Objekt einen Knoten.
Also zum Beispiel Person,PC, Browser und Simple Club Website.
Die verbinden wir jetzt alle sinnvoll mit Pfeilen.
Jetzt können wir nur immer in eine Richtung gehen, da es ja zum Beispiel keinen Sinn macht
von Browser zu Pc zu gehen.
Probiert den Durchgang ruhig mal selber aus!
Knick Knack.
Ihr versteht.
Bei einem ungerichteten Graphen kann eine Kante in beide Richtungen durchlaufen werden.
Da zeichnet man einfach ne ganz normale Linie zwischen die Knoten.
Zwei Knoten heißen dann verbunden, wenn eine Kante zwischen ihnen besteht.
Ein ungerichteter Graph ist ein Spezialfall von einem gerichteten Graphen.
Ein ungerichteter Graph kann also immer als gerichteter Graph dargestellt werden, da man
eine Kante ja einfach durch zwei entgegengesetzte Pfeile darstellen kann.
Andersrum funktioniert das allerdings nicht, da man einen Pfeil beim ungerichteten Graph
ja nicht zeichnen kann.
Dats not possible!
Für einen ungerichteten Graphen können wir zum Beispiel das Städtebeispiel von vorhin
hernehmen.
Die Kanten markieren dabei die Flugstrecken zwischen den Städten.
Die Kante kann man jetzt in beide Richtungen lesen, da man ja zwischen den Städten hin
und her fliegen kann.
Wir merken uns: Beim gerichteten Graph verläuft die Kante nur in eine Richtung.
Beim ungerichteten Graphen kann sie in beide Richtungen verlaufen.
Es gibt natürlich noch viel mehr zu wissen!
Es gibt zum Beispiel noch für jeden Knoten einen Grad.
Der Grad bestimmt einfach wie viele Kanten von diesem Knoten ausgehen.
Für A und D wäre der Grad also 1, da nur eine Kante an die anschließt.
B und C hätten dagegen einen Grad von 2, weil zwei
Kanten da anschließen.
Falls den Kanten jetzt noch weitere Informationen zugeordnet sind, spricht man von einem markierten
Graphen.
Die Kanten haben dann bestimmte Kosten.
Man könnte also in dem Städtegraphen noch einfügen, wie lange ein Flug zwischen den
Städten dauert.
Also wenn wir jetzt mal davon ausgehen, dass der Flug pünktlich ist.
Haha…
Der war gut.
Soo soweit zur Theorie.
Ab in die Praxis!
Wir wollen jetzt selber mal nen gerichteten Graph aufbauen.
Wir skizzieren zum Beispiel die Buchung eines Flugs.
Dafür brauchen wir die Objekte Person,Handy,Pc, Website, Reisebüro und Flug.
Als erste zeichen wir mal Pfeile von Person nach Handy,Pc und Reisebüro.
Wir können ja entweder selber den Flug buchen oder übers Reisebüro.
Vom Pc oder vom Handy kommen wir auf die Website um den Flug zu buchen.
Zum Flug kommen wir dann vom Reisebüro oder von der Website aus.
Klar soweit?
Als nächstes zeichnen wir einen ungerichteten Graphen.
Dafür wollen wir ein Zugliniennetz mit deutschen Städten zeichnen.
Zuerst zeichnen wir mal als Objekte die Städte Berlin,München,Hamburg und Köln.
Da zeichnen wir zwischen den Knoten jetzt die Kanten ein.
Somit hat man zwischen allen Städten eine Zugverbindung auf der man in beide Richtungen
fahren kann.
So, wie war das jetzt mit dem Grad?
Im Städtebeispiel hat jeder Knoten jetzt nen Grad von 3, da zu jedem Knoten ja drei
Kanten führen.
Ganz easy.
Natürlich können wir jetzt auch noch die Reisedauer als Kosten an unsere Kanten schreiben.
Jetzt haben wir schon einen markierten Graphen.
Nice!
Na genug für heute?
Jou find ich auch.
Also schnell nochmal zusammenfassen.
Ein Graph ist eine grafische Darstellung von Objekten und deren Beziehungen.
Ein Graph besteht außerdem aus Kanten und Knoten.
Man unterscheidet zwischen gerichteten und ungerichteten Graphen.
Ein ungerichteter Graph kann über die Kanten in beiden Richtungen durchlaufen werden.
Ein gerichteter Graph kann über die Pfeilkanten nur in eine Richtung durchlaufen werden.
Ein ungerichteter Graph kann immer als gerichteter Graph dargestellt werden.
Ein Grad beschreibt wie viele Kanten an einem Knoten anliegen.
Ein markierter Graph enthält zusätzlich noch Informationen an den Kanten.
Diese heißen dann Kosten einer Kante.
So es war mir wieder einmal eine Ehre mit euch!
Als nächstes schauen wir uns an, was Pfade und Zyklen sind!
Wir sehen uns gleich!
