Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Graphen einfach erklärt - Graphentheorie 1
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 51 Zeilen
- 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!