de:non-linear_data_structure:graph [jltk

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Einführung ======
Mit einem Graphen kann man verschiedene Objekte und deren Beziehung untereinander darstellen.
Die Galerie unten zeigt eine Menge unterschiedlicher Graphen, die aber alle grundlegende Gemeinsamkeiten haben.

<gallery lighthouse nocrop center 150x150 3>
:0_global:non-linear_data_structure:graph:socialnetwork.png
:0_global:non-linear_data_structure:graph:graph_cities.png
:0_global:non-linear_data_structure:graph:graph_example1.png
:0_global:non-linear_data_structure:graph:Haus_vom_Nikolaus.jpeg
https://upload.wikimedia.org/wikipedia/commons/7/78/U-Bahn_Wien.png
https://upload.wikimedia.org/wikipedia/commons/b/bc/CPT-Graphs-directed-weighted-ex1.svg
</gallery>

**Aufgabe:** 
  - Beschreibe, welche Gemeinsamkeiten alle in der Galerie dargestellten Graphen haben. 
  - Versuche allgemein zu beschreiben, aus welchen Elementen ein Graph besteht. 



===== Aufbau von Graphen =====
{{ :de:non-linear_data_structure:graph:haus_vom_nikolaus_beschriftung.png?400|}}Das //Haus vom Nikolaus// lässt sich auch als Graph interpretieren. Die fünf Ecken (Knoten) des Hauses werden mit Linien (Kanten) untereinander verbunden. 


Beim Haus vom Nikolaus spielt es keine Rolle, ob die Linie z.B. von A nach B oder von B nach A gezeichnet wird. Man sagt, der Graph ist ungerichtet. 

Man kann das Haus vom Nikolaus somit durch eine Menge //V// von Kanten (Vertex) und einer Menge //E// von Kanten (//Edge//) beschreiben:
\begin{align*}
V&=\{A,B,C,D,E\}\\
E&=\{(A,B),(A,C),(A,E),(B,C),(B,E),(C,D),(C,E),(D,E)\}
\end{align*} 



Die Kanten eines Graphens können mit einem Gewicht versehen werden. Repräsentieren die Knoten z.B. Orte, so kann das Kantengewicht für den Abstand dieser Orte stehen.

<callout type="info" icon="true">
=== Aufbau eines Graphen ===
Ein Graph besteht aus **Knoten** (//Vertex//). Knoten können mit **Kanten** (//Edge//) untereinander verbunden sein.

Ein Kante kann zusätzlich noch eine Gewichtung (Zahl) besitzen.

Spielt bei einem Graphen die Richtung einer Kante keine Rolle, so spricht man von einem //ungerichteten Graphen//.
</callout>

==== Adjazenzmatrix ====
Um die Verbindungen der Knoten zu verwalten, wird eine [[wpde>Adjazenzmatrix]] verwendet. Funken ist die Adjazenzmatrix für das Haus vom Nikolaus dargestellt.

Eine 1 bedeutet, dass die beiden Knoten miteinander verbunden sind, eine 0, dass die beiden Kanten nicht miteinander verbunden sind.

{{ 0_global:non-linear_data_structure:graph:adjacencymatrix.svg |}}
/* latex Quelltext
\begin{array}{r|c}
&{
	\begin{array}{ccccc}A&B&C&D&E\end{array}
}\\\hline 
{
	\begin{array}{ccccc}1\\2\\3\\4\\5\end{array}
}
&{
       \begin{pmatrix}
		0&1&1&0&1\\
		1&0&1&0&1\\
		1&1&0&1&1\\
		0&0&1&0&1\\
		1&1&1&1&0
	\end{pmatrix}
}
\end{array}
*/


**Aufgabe 2:**
Stelle die Adjazenzmatrix für den folgenden Graphen auf:
{{ 0_global:non-linear_data_structure:graph:graph_example1.png?250 |}}


----

====== Projekte ======

  - **Haus vom Nikolaus**\\ Im Projekt [[de:non-linear_data_structure:graph:haus_vom_nikolaus|Haus vom Nikolaus]] lernst du den Umgang mit Graphen aus programmiertechnischer Sicht.
  - **Soziale Netzwerke**\\ Im Projekt [[de:non-linear_data_structure:graph:social_Network|Soziale Netzwerke]] lernst du die Klassen //Graph//, // Vertex// und //Edge// kennen.
  - **Graphen durchlaufen und in Graphen suchen**\\ Im Projekt [[de:non-linear_data_structure:graph:searching_graph|Graphen durchlaufen]] lernst du die beiden Suchmethoden //Tiefensuche// und //Breitensuche// kennen.
  - **Routing**\\ Im Projekt [[de:non-linear_data_structure:graph:routing]] lernst du Algorithmen kennen, mit denen du den kürzesten Weg in einem Graphen ermitteln kannst.


===== Aufgaben =====