Graphen einfach erklärt - Graphentheorie 1
Informatik - simpleclub
https://www.youtube.com/watch?v=frG2kBMZQDc

Transkript (automatisch erstellt)

0:00 Soso der Herr Graf lässt sich jetzt auch mal Blicken. Ouh ne.
0:04 Mein Fehler. Ich mein natürlich Graphen.
0:07 Damit mein ich aber nicht die komischen Kurven da in Mathe. Wir kümmern uns heute um die wunderschönen Graphen in der Informatik.
0:13 Wie die aussehen, sehen wir gleich! So wat is jetzt so en Graph?
0:22 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.
0:31 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.
0:40 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!
0:47 Ein Graph kann beispielsweise dazu verwendet werden, um Flugverbindungen zwischen Städten darzustellen.
0:53 Die Knoten stellen dabei die jeweilige Stadt dar und die Kanten die jeweilige Strecke zwischen den Städten.
0:59 Im Groben können wir zwischen gerichteten und ungerichteten Graphen unterscheiden. Bei einem gerichteten Graph kann mit einer Kante nur in eine Richtung gehen.
1:07 Eine Kante wird dabei durch einen Pfeil dargestellt. Bei einem gerichteten Graphen heißen zwei Knoten stark verbunden, falls es einen Weg
1:15 von einem Knoten zum anderen und auch wieder zurück gibt. Durch einen gerichteten Graph kann man perfekt Aktionen skizzieren.
1:22 Das aufrufen der Website von Simple Club könnte man beispielsweise so machen: Wir brauchen für jedes Objekt einen Knoten.
1:28 Also zum Beispiel Person,PC, Browser und Simple Club Website. Die verbinden wir jetzt alle sinnvoll mit Pfeilen.
1:34 Jetzt können wir nur immer in eine Richtung gehen, da es ja zum Beispiel keinen Sinn macht von Browser zu Pc zu gehen.
1:42 Probiert den Durchgang ruhig mal selber aus! Knick Knack.
1:44 Ihr versteht. Bei einem ungerichteten Graphen kann eine Kante in beide Richtungen durchlaufen werden.
1:49 Da zeichnet man einfach ne ganz normale Linie zwischen die Knoten. Zwei Knoten heißen dann verbunden, wenn eine Kante zwischen ihnen besteht.
1:56 Ein ungerichteter Graph ist ein Spezialfall von einem gerichteten Graphen. Ein ungerichteter Graph kann also immer als gerichteter Graph dargestellt werden, da man
2:05 eine Kante ja einfach durch zwei entgegengesetzte Pfeile darstellen kann. Andersrum funktioniert das allerdings nicht, da man einen Pfeil beim ungerichteten Graph
2:14 ja nicht zeichnen kann. Dats not possible!
2:17 Für einen ungerichteten Graphen können wir zum Beispiel das Städtebeispiel von vorhin hernehmen.
2:22 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
2:29 und her fliegen kann. Wir merken uns: Beim gerichteten Graph verläuft die Kante nur in eine Richtung.
2:35 Beim ungerichteten Graphen kann sie in beide Richtungen verlaufen. Es gibt natürlich noch viel mehr zu wissen!
2:41 Es gibt zum Beispiel noch für jeden Knoten einen Grad. Der Grad bestimmt einfach wie viele Kanten von diesem Knoten ausgehen.
2:49 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
3:12 Kanten da anschließen. Falls den Kanten jetzt noch weitere Informationen zugeordnet sind, spricht man von einem markierten
3:20 Graphen. Die Kanten haben dann bestimmte Kosten.
3:23 Man könnte also in dem Städtegraphen noch einfügen, wie lange ein Flug zwischen den Städten dauert.
3:28 Also wenn wir jetzt mal davon ausgehen, dass der Flug pünktlich ist. Haha…
3:31 Der war gut. Soo soweit zur Theorie.
3:33 Ab in die Praxis! Wir wollen jetzt selber mal nen gerichteten Graph aufbauen.
3:37 Wir skizzieren zum Beispiel die Buchung eines Flugs. Dafür brauchen wir die Objekte Person,Handy,Pc, Website, Reisebüro und Flug.
3:45 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.
3:53 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.
4:01 Klar soweit? Als nächstes zeichnen wir einen ungerichteten Graphen.
4:06 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.
4:14 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
4:21 fahren kann. So, wie war das jetzt mit dem Grad?
4:24 Im Städtebeispiel hat jeder Knoten jetzt nen Grad von 3, da zu jedem Knoten ja drei Kanten führen.
4:30 Ganz easy. Natürlich können wir jetzt auch noch die Reisedauer als Kosten an unsere Kanten schreiben.
4:34 Jetzt haben wir schon einen markierten Graphen. Nice!
4:37 Na genug für heute? Jou find ich auch.
4:39 Also schnell nochmal zusammenfassen. Ein Graph ist eine grafische Darstellung von Objekten und deren Beziehungen.
4:43 Ein Graph besteht außerdem aus Kanten und Knoten. Man unterscheidet zwischen gerichteten und ungerichteten Graphen.
4:50 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.
4:59 Ein ungerichteter Graph kann immer als gerichteter Graph dargestellt werden. Ein Grad beschreibt wie viele Kanten an einem Knoten anliegen.
5:06 Ein markierter Graph enthält zusätzlich noch Informationen an den Kanten. Diese heißen dann Kosten einer Kante.
5:17 So es war mir wieder einmal eine Ehre mit euch! Als nächstes schauen wir uns an, was Pfade und Zyklen sind!
5:22 Wir sehen uns gleich!