Graphen einfach erklärt - Graphentheorie Graphs simply explained - Graph theory Explicación sencilla de los gráficos - Teoría de los gráficos Графики объясняются просто - Теория графиков

Soso der Herr Graf lässt sich jetzt auch mal Blicken. Así que el Sr. Graf está haciendo su aparición.

Ouh ne.

Mein Fehler. Error mío.

Ich mein natürlich Graphen. Me refiero a gráficos, por supuesto.

Damit mein ich aber nicht die komischen Kurven da in Mathe. Pero no me refiero a las curvas curiosas de las matemáticas.

Wir kümmern uns heute um die wunderschönen Graphen in der Informatik. Hoy nos fijamos en los bellos grafos de la informática.

Wie die aussehen, sehen wir gleich! Veremos qué aspecto tienen dentro de un momento.

So wat is jetzt so en Graph? ¿Cuál es el gráfico ahora?

Ein Graph is grob gesagt eine grafische Darstellung von Objekten und deren Beziehungen. A grandes rasgos, un gráfico es una representación gráfica de objetos y sus relaciones.

Die Objekte sind dabei einfach so Kreise und werden als Knoten bezeichnet. Los objetos son simples círculos y se denominan nodos.

Diese können zum Beispiel Objekte wie Zahlen oder auch Namen enthalten. Pueden contener objetos como números o nombres, por ejemplo.

Die Beziehungen sind die Linien zwischen diesen Knoten und werden als Kanten bezeichnet. Las relaciones son las líneas entre estos nodos y se denominan aristas.

Solche Darstellungen kennt ihr jetzt schon von den Automaten und von Binärbäumen. Ya conoces este tipo de representaciones por los autómatas y los árboles binarios.

Dazu haben wir auch ganz viele schöne Videos für euch auf unserer Website! También tenemos muchos vídeos estupendos en nuestra página web.

Ein Graph kann beispielsweise dazu verwendet werden, um Flugverbindungen zwischen Städten Un gráfico puede utilizarse, por ejemplo, para determinar las conexiones aéreas entre ciudades.

darzustellen. que se mostrará.

Die Knoten stellen dabei die jeweilige Stadt dar und die Kanten die jeweilige Strecke zwischen Los nodos representan la ciudad respectiva y las aristas representan la ruta respectiva entre

den Städten.

Im Groben können wir zwischen gerichteten und ungerichteten Graphen unterscheiden. A grandes rasgos, podemos distinguir entre grafos dirigidos y no dirigidos.

Bei einem gerichteten Graph kann mit einer Kante nur in eine Richtung gehen. En un grafo dirigido, una arista sólo puede ir en una dirección.

Eine Kante wird dabei durch einen Pfeil dargestellt. Una arista se representa mediante una flecha.

Bei einem gerichteten Graphen heißen zwei Knoten stark verbunden, falls es einen Weg En un grafo dirigido, dos nodos se denominan fuertemente conectados si existe un camino

von einem Knoten zum anderen und auch wieder zurück gibt. de un nodo a otro y viceversa.

Durch einen gerichteten Graph kann man perfekt Aktionen skizzieren. Un grafo dirigido es perfecto para esbozar acciones.

Das aufrufen der Website von Simple Club könnte man beispielsweise so machen: Por ejemplo, puedes acceder al sitio web de Simple Club de la siguiente manera:

Wir brauchen für jedes Objekt einen Knoten. Necesitamos un nodo para cada objeto.

Also zum Beispiel Person,PC, Browser und Simple Club Website. Por ejemplo, persona, PC, navegador y sitio web de Simple Club.

Die verbinden wir jetzt alle sinnvoll mit Pfeilen. Ahora los conectamos con flechas.

Jetzt können wir nur immer in eine Richtung gehen, da es ja zum Beispiel keinen Sinn macht Ahora sólo podemos ir en una dirección, ya que no tiene sentido, por ejemplo

von Browser zu Pc zu gehen. para pasar del navegador al PC.

Probiert den Durchgang ruhig mal selber aus! Pruebe usted mismo el pasaje.

Knick Knack. Knick Knack.

Ihr versteht.

Bei einem ungerichteten Graphen kann eine Kante in beide Richtungen durchlaufen werden. En un grafo no dirigido, una arista puede recorrerse en ambas direcciones.

Da zeichnet man einfach ne ganz normale Linie zwischen die Knoten. Basta con trazar una línea normal entre los nodos.

Zwei Knoten heißen dann verbunden, wenn eine Kante zwischen ihnen besteht. Se dice que dos nodos están conectados si existe una arista entre ellos.

Ein ungerichteter Graph ist ein Spezialfall von einem gerichteten Graphen. Un grafo no dirigido es un caso especial de un grafo dirigido.

Ein ungerichteter Graph kann also immer als gerichteter Graph dargestellt werden, da man Por lo tanto, un grafo no dirigido siempre puede representarse como un grafo dirigido, ya que

eine Kante ja einfach durch zwei entgegengesetzte Pfeile darstellen kann. una arista puede representarse simplemente mediante dos flechas opuestas.

Andersrum funktioniert das allerdings nicht, da man einen Pfeil beim ungerichteten Graph

ja nicht zeichnen kann. no sabe dibujar.

Dats not possible! ¡No es posible!

Für einen ungerichteten Graphen können wir zum Beispiel das Städtebeispiel von vorhin Para un grafo no dirigido, por ejemplo, podemos utilizar el ejemplo de la ciudad de antes

hernehmen. Toma.

Die Kanten markieren dabei die Flugstrecken zwischen den Städten. Los bordes marcan las rutas de vuelo entre las ciudades.

Die Kante kann man jetzt in beide Richtungen lesen, da man ja zwischen den Städten hin El borde puede leerse ahora en ambas direcciones, ya que puedes desplazarte entre las ciudades.

und her fliegen kann. puede volar de un lado a otro.

Wir merken uns: Beim gerichteten Graph verläuft die Kante nur in eine Richtung. Recuerda: en un grafo dirigido, la arista sólo va en una dirección.

Beim ungerichteten Graphen kann sie in beide Richtungen verlaufen. Con grafos no dirigidos, puede funcionar en ambas direcciones.

Es gibt natürlich noch viel mehr zu wissen! Por supuesto, hay mucho más que saber.

Es gibt zum Beispiel noch für jeden Knoten einen Grad. Por ejemplo, sigue habiendo un grado para cada nodo.

Der Grad bestimmt einfach wie viele Kanten von diesem Knoten ausgehen. El grado simplemente determina cuántas aristas se originan en este nodo.

Für A und D wäre der Grad also 1, da nur eine Kante an die anschließt. Por tanto, el grado de A y D sería 1, ya que sólo una arista conecta con la otra.

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!