Graphen | Informationen vernetzen:

anchored to [[111.00_anchor]] belongs to [[111.08_algo_datastructures]]

Basic Definition:

Wenn wir von einem Graphen sprechen meine wir folgende Struktur:

[!Definition] Graphen was sind Graph, womit werden sie aufgebaut? wie mathematisch? #card Ein Graph besteht grundlegend aus Knoten und Kanten. Dabei sind Knoten irgendwelche Datenpunkte, die wir mit Kanten ( als Verbindungselemente ) in Beziehungen zueinander setzen können. Kanten können gerichtet $\{u,v\}$ ( also die Orientierung ist wichtig!) oder ungerichtet $(u,v)$ sein!

Ein Graph ist jetzt $G=(V,E)$ und besteht dabei aus einer Menge von Kanten, wobei $E=E\subset V\times V$ ist. ( also es gibt zwischen allen Knoten Kanten, aber meist ist das nicht der Fall)

![[Pasted image 20221104101944.png]]

Es existieren also gerichtete Graphen und ungerichtete Graphen, welche sich folgend unterscheiden: #card

• gerichtete Graphen haben Kanten mit Orientierung, also wenn wir von A -> B meinen, geht hier nicht B ->, außer wir fügen diese Kante hinzu. Dann wird daraus <->
• ungerichtete Graphen beschreiben nur, ob etwas verbunden ist oder nicht –> hier ist keine Orientierung der Beziehung zwischen Knoten wichtig!

[!Tip] Adjazent was meinen wir damit? #card Wir nennen zwei Knoten adjazent (benachbart), wenn es eine Kante zwischen beiden gibt. Also etwa $(u,v)$ heißt, dass $u\wedge v$ adjazent zueinander sind!

Notationen:

Wenn wir ungerichtete Graphen betrachten, beschreiben wir mit $u\sim v$ :: dass diese beiden benachbart sind, also zwischen beiden eine Verbindung besteht!

Betrachten wir einen gerichteten Graph, beschreiben wir mit $u⟶v$ :: , dass eine Kante von u nach v existiert, also $(u,v)\in E$

Kosten und Gewichte auf Kanten beschreiben wir folgend mit :: $w(u,v)$ für Gewicht und $c(u,v)$ für Kosten

Es gibt Spezialfälle, wo alle Kantengewichte zwei Zustände haben können :: $0$-> keine Kante, $1$ -> eine Kante

Wir sprechen von einem Loop / Selbstschleife, wenn :: $e(u,v),u=v$ ![[Pasted image 20231109151149.png]]

Anwendung von Graphen:

Eigentlich können wir Graphen überall bzw oft anwenden, um Probleme anders darzustellen ( Bäume etwa ).
Weiterhin gibt es viele Anwendungen bei:

• Netzwerken
• Such-Algorithmen
• großer Datenverarbeitung ( Interessen oder Gruppen herausfinden können )
• using graphs for representing a cluster of possible outcomes that ought to form a consens [[462.01_consensus_algorithms]]

Grundbegriffe | Grad:

Wir möchten jetzt die Eigenschaft des Grades eines Knotens $v$ betrachten.

[!Definition] Wir definieren den Ausgangsgrad was beschreibt dieser? #card Wir beschreiben damit, die Menge an Kanten, die von dem Knoten $v$ ausgehen. Anders beschrieben also : $$outdeg(v)=|\{w\in V|(v,w)\in E\}|$$

Wir könnun auch noch den Eingangsgrad betrachten, der analog dazu ist

[!Definition] Eingangsgrad eines Knoten $v$ was meinen wir damit? #card Der Eingangsgrad ist, analog zum Ausgangsgrad, die Menge von Kanten, die zu dem Knoten zeigen Formal beschrieben also: $$indeg(v)=|\{w|(w,v)\in E\}|$$

Wir können jetzt noch die Zusammenführung beider “Grade” betrachten:

[!Definition] Der Grad eines Knoten $v$ was beschreibt er, wie bilden wir ihn? #card Der Grad eines Knoten $v$ beschreibt dessen Ein-, und Ausgehenden Kanten! Es werden also alle Kanten, die in Relation zu diesem Knoten stehen gezählt. Formal definieren wir ihn dann: $$deg(v)indeg(v)+outdeg(v)⟺|\{w|\{v,w\}\in E\}$$

Folgend noch ein Beispiel, was die Nutzung beschreibt:

[!example] Grad von Knoten Betrachte folgenden Knoten ![[Pasted image 20231109152745.png]]

• outdeg von 2 ?
• indeg von 1 ?
• deg von 4 und 3 ? Beantworte die Fragen #card

[!Important] Convention | Number of vertices and edges Wir werden in dieser Vorlesung nur finite Graphen betrachten, also solche bei denen gilt was ? #card $N:=|V|\le \infty$ –> Menge der Knoten $M:=|E|\le \infty$ –> Menge der Kanten ![[Pasted image 20221104103141.png]]

Pfade | Graphen folgen

Wir möchten folgend ein paar Terme definieren, die Pfade auf bzw in Graphen beschreiben können.

[!Definition] Pfade wie definieren wir einen Pfad in Graphen? #card Sei $G=(V,E)$ ein Graph. Wir nennen jetzt die Folge von Knoten $(v_0,v_1,\dots ,v_k$ einen Pfad, wenn für alle $0\le i\le k-1$ Kanten besagte Kanten-Kombination existiert: $(v_i,v_{i+1})$ –> Vereinfacht gesagt heißt das, dass wir von einem Pfad sprechen, wenn wir von einem Knoten zu einem anderen Knoten durch den Graphen traversieren können. Es muss also entsprechende Kanten geben, die das ermöglichen.

Wir können jetzt noch ein Zykel als spezielle Form eines Pfades betrachten:

[!Definition] Zykle - Pfad was meinen wir mit einem Zykel? #card Mit einem Zykel meinen wir einen Pfad $(v_0,v_1,\dots v_k)$, wo der Startpunkt gleich dem Endpunkt ist. Also $v_k=v_0$ –> wir bewegen uns also Zyklisch und haben einen Kreis-PFad in dem Graphen gefunden.

[!Example] Betrachtung eines Graphes. ![[Pasted image 20231112145729.png]] Finde den Pfad und die Zykel #card

Forests | Graphen mit Binärbäumen:

Wir möchten noch den Begriff eines Forests einführen, welcher solche Graphen beschreibt, die in ihrer Form aus mehreren disjunkten Bäumen bestehen.

[!Definition] Bezeichnung eines Graphes als Baum: welche Eigenschaften (3) muss erfüllen? #card Sei hierfür $G=(V,E)$ ein Graph. Er heißt jetzt Baum, wenn folgendes gilt

1. V enthält genau ein $v_0$, mit $indeg(v_0=0)$ –> Also ein Knoten, bei welchem nichts hineingeht und nur abgeht (Das ist die Wurzel unseres Baumes)
2. $\forall v\in V\setminus \{v_0\}:indeg(v)=1$ –> Also jeder weitere Knoten hat immer genau eine Eingehende Kante –> die des parents
3. $G$ ist azyklisch –> hat also keine einzigen Zykel in sich.

[!Important] Erweiterung eines Graphen als Forest: wann sprechen wir von Forests? #card Wir nennen einen Graphen $G=(V,E)$ Forest, wenn gilt, dass $G$ aus mehreren disjunkten Bäumen besteht –> also $G=G_1\bigcup \cdots \bigcup G_k$ wobei $G-i$ ein Baum ist

[!Example] Folgend sind ein paar Forests gelistet: ![[Pasted image 20231112150733.png]]

Acyclic Graphs:

[!Definition] acyclic Graphen #card Mit acyclic Graphen bezeichnen wir solche Graphen, die in gar keinen Cyclus in den Pfaden aufweisen. Das heißt demnach, dass wir nur von einer Richtung in die andere Traversieren können, und so der Anfangs-Knoten in einem Pfad niemals der Ziel-Knoten sein kann.

Da diese Form speziell ist, bekommt sie noch ein Akronym, damit man direkt weiß, worum es geht:

[!Important] DAG - Directed - Acyclic Graph –> Sind Graphen die gerichtet sind, und dabei keinen Zykel aufweisen!

Vollständige Graphen ( Complete graphs):

Mit vollständigen Graphen beschreiben wir solche Graphen $G=(V,E)$, bei denen folgend gilt: #card

• für beliebige Knoten $u,v\in V:\exists \{u,v\}\in E$ –> also jeder Knoten im Graphen ist mit jedem Knoten verbunden.

[!Example] Beispiel für vollständigen Graph ![[Pasted image 20231112170158.png]]

Bipartite Graphen:

Wir sprechen bei einem Graphen $G=(V,E)$ von bipartite, wenn folgend gilt: #card

• Wir können die Menge der Graphen in zwei Gruppen unterteilen.
• Dabei ist wichtig, dass sich die Knoten in einer Gruppe nicht verbinden
• Ein jeder Knoten aus einer Gruppe trifft (alle) Knoten aus der anderen Gruppe
• Formal heißt das: $(V=A\cup B)\wedge \varnothing \ne A\ne V$ und weiterhin für die Knoten $u\in A,v\in B$ und umgekehrt

[!Example] vollständiger, bipartiter Graph ![[Pasted image 20231112170634.png]]

induzierter Graph:

Wir möchten ferner einen Teilgraphen $G^{\prime }=(V^{\prime },E^{\prime })$ von $G=(V,E)$ als induziert bezeichnen, wenn gilt: #card

• $V^{\prime }\subseteq V$ und folgend $\forall \{u,v\}\in E$ mit $u,v\in V^{\prime }$ gilt jetzt auch $\{u,v\}\in E^{\prime }$
• Also wenn wir eine Verbindung zwischen Knoten haben und diese Knoten auch in dem neuen Graphen enthalten sind, müssen sie die alten Verbindungen übernehmen ( um gleich dann induziert genannt zu werden )

[!Example] induzierte Teilgraphen ![[Pasted image 20231112171128.png]] Er ist nicht induziert, weil hier nicht die Kanten zwischen a.g.f,b bezeichnet bzw genannt werden.

Zusammenhängend:

Wir möchten einen **ungerichteten (undirected) ** Graphen $G=(V,E)$ als Zusammenhängend bezeichnen, wenn #card

• zwischen zwei beliebigen Knoten $u,v\in V$ existiert ein Pfad, sodass beide Knoten verbunden werden.
• Die Pfade müssen also die Endpunkte $u,v$ haben an.

Zusammenhangskomponente (ZK):

Nennen wir dann schließlich einen Bereich eines ungerichteten Graphen Zusammenhangskomponente, wenn für den Graphen $G=(V,E)$ gilt: #card

• der maximale, zusammenhängende Teilgraph $G^{\prime }$ bezeichnet jetzt die Zusammenhangskomponente

[Example] Beispiel für Zk: ![[Pasted image 20231112171813.png]]

stark zusammenhängend:

–> Gilt nur für ==gerichtete Graphen==! Wir können jetzt einen Graphen $G=(V,E)$ stark zusammenhängend beschreiben, wenn folgendes gilt:

• $\forall v,u\in V:v\ne u:\exists P(u,v)\wedge P(v,u)$
  • Das heißt also, dass es für jeden Knoten in dem Teilgraph eine Verbindung zwischen beiden Knotengibt. Dabei ist die Verbindung aber beidseitig, wir können also von $u,v$ aber auch $v,u$!

starke Zusammenhangskomponente (SZK):

Wir beschreiben mit einem SZK :: einen maximal stark zusammenhängenden Teilgraph eines gerichteten Graphen $G$

• zusammenhängend, weil alle Punkte miteinander verbunden >> im Bild ersichtlich
• maximal sodass es keinen größeren Verbund gibt, welcher ebenfalls eine Teilmenge des Graphes bildet. ![[Pasted image 20221104103745.png]]

Multi-path-Graphs

Wir können uns einen Graphen anschauen, welcher womöglich mehrere Kanten für eine Verbindung zwischen $u,v$ aufweist. -> Meist sind diese in ungerichteten Graphen vertreten, aber können auch in gerichteten vorkommen.

[!Example] ![[Pasted image 20221104105948.png]]

dense graph(dicht besetzter Graph) :: has very many edges :: based on context, very many is not specifically defined. Used when the number of m of edges is more than logarithmic in the number of vertices, in particular $TETA(n^2)$

sparse graph(dünn besetzter Graph) :: contains few edges each vertex has a very small degree compared to n possible ones. May be called sparse if number of edges is O(n log n) or O(n)(rare)

Graphen Darstellen / Repräsentieren:

Wir können Graphen jetzt grundsätzlich konstruieren und später diverse Vorteile ihres Konzeptes anwenden, brauchen aber weiterhin eine Grundform bzw. Datenstruktur in welcher wir diese Graphen repräsentieren können.

Darstellen als Matrix:

Als erste Lösung könnte man sie in Form einer Matrix bilden:

[!Definition] Adjazenzmatrix für Graph $A$ wie ist diese aufgebaut? #card Wir beschreiben die Matrix, die diese Verbindungen zwischen den einzelnen Knoten darstellt folgend: $A=(a_{i,j})$ , wobei jetzt $a_{i,j}=\{\begin{array}{ll}1& \text{falls }(i,j)\in E\\ 0& \text{sonst}\end{array}$

Betrachten wir folgenden Graphen und stellen ihn als Matrix dar: ![[Pasted image 20231112181035.png]]

$$\left(\begin{array}{cccccc}0& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ & & & & & \end{array}\right)$$

[!Definition] Besonderheit der Matrix bei ungerichteten Graphen Betrachten wir ungerichtete Graphen, dann sehen wir, dass sie Symmetrisch sind

Kosten und Aufwand:

Wenn wir einen $|V|=n,|E|=m$ z betrachten, also einen Graphen der Größe $n$ mit einer Menge von Kanten $|E|=m$.

[!Definition] Platzbedarf für diese Matrix? Wenn wir hier $|V|=n$ Knoten haben, dann müssen wir maximal alle möglichen Knoten, also die Menge, die bei eine vollständigen Graphen auftreten könnte, abdecken können! Es folgt daher ein Platzbedarf von $\mathcal{O}(n^2)$, denn wir brauchen eine Matrix von Größe $|V|\times |V|$ –> jeder Knoten, kann theoretisch mit jedem Knoten verbunden sein.

[!Definition] Zugriffszeit bei einer Adjazenzmatrix: was bildet ein Problem? #card Wir wissen, wo sich bei der Matrix ein Eintrag für die Kanten befindet. Aus diesem Grund ist es ein statisches abrufen mit: $\mathcal{O}(1)$

Ein Problem entsteht, wenn man dünne Graphen hat, also solche die kaum Verbindungen haben. Da ist der Platzbedarf weiterhin mit $\mathcal{O}(n^2)$ beschrieben, obwohl wir beispielsweise nur $\mathcal{O}(n)$ Elemente haben.

Fragen bei Matrizen:

Man kann jetzt folgende Fragen definieren:

• Welche Knoten hat die meisten eingehenden Kanten? –> am beliebtesten
• Welches Knotenpaar ist am weitesten auseinander?
• Welcher Knoten ist zentral

Darstellen als Adjazenzliste:

Alternativ zu einer Matrix können wir die Abhängigkeit von Knoten auch durch Listen darstellen. Das heißt demnach, dass wir für jeden Knoten die Nachbarknoten dieser speichern.

bei gerichteten Graphen müssen wir dabei zwei Repräsentationen betrachten: welche, warum? #card

• $InADJ(v)=\{w\in V|(w,v)\in E\}$ –> also alle die, die in einen Knoten $v$ führen
• $OutADJ(v) = { w\in \V | (v,w) \in E }$ –> also alle die, die von dem Knoten ausgehen

bei einem ungerichteten Graphen können wir die Speicherung der Adjazenzlisten etwas vereinfachen: wie? #card

• wir brauchen nur ob eine Verbindung vorliegt oder nicht. Es gibt also keine Information darüber, wie sie verbunden sind!
• Dadurch folgt $ADJ(v)=\{w\in V|\{v,w\}\in E\}$

Betrachten wir dafür ein Beispiel:

[!Example] Adjazenzliste eines gerichteten Graphen: Wir wollen den folgenden Graphen betrachten: ![[Pasted image 20231112190558.png]] wie sieht dessen OutADJ Liste aus? #card ![[Pasted image 20231112190613.png]]

ein weiteres Beispiel: ![[Pasted image 20221104112300.png]]

[!Important] Platz für Adjazenzlisten: wovon ist er abhängig? #card Wir können den Platz, der für eine Adjazenzliste benötigt wird folgend definieren: $\mathcal{O}(n+m)$

[!Definition] Zugriff auf spezifische Kanten und Geschwindigkeit dieses Zugriffes ? #card Wenn wir auf eine Kante von $(v,w)$ zugreifen möchten, dann müssen wir entsprechend alle Adjazenz-Elemente von $v$ betrachten –> da diese Speichert, wohin von $v$ verbunden wird. Aus diesem Grund ist die Zugriffszeit notiert mit $\mathcal{O}(outdeg(v))$, wobei: $outdeg(v)=|\{w\in V|(v,w)\in E\}|$ meint, also die Größe der Liste, von den ausgehenden Verbindungen des Knoten $v$

Folgerung für Adjazenzlisten:

Wie wir sehen können ist der Zugriff auf eine Adjazenliste nur so groß, wie die Menge der verbundenen Knoten, also $\mathcal{O}(outddeg(v))$. Weiterhin ist der Platzbedarf verhältnismäßig klein und vorallem dynamisch zur Menge von Elementen, also $\mathcal{O}(n+m)$.

Aufgrund dieser Eigenschaften können wir folgern:

[!Definition] Platzverbrauch und Vergleich zu Matrixdarstellung #card -> die Platzverwendung ist hier deutlich effizienter, weil die Größe dynamisch mit der Menge von Knoten und Kanten linear steigt und nicht wie bei Matrizen explodiert. Es kann hier jedoch sein, dass der Zugriff langsamer ist, weil wir unter Umständen eine gewisse Menge von Einträgen durchsuchen müssen, um unsere Lösung zu finden.

When to use matrix or list:

if the graph (knowingly) is rather small - couple of 100 vertices at most - its does not matter much which representation to choose from, because the time wont differ much.

However if a graph is dense we can observe that for both representations ::both take about the same amount of storage, yet a matrix is faster for calculation and so preferred over the adjacencylist.

if graph is sparse use an adjacency list

• there are circumstances where it is good to use adjacency matrices, because given issues could be solved using linear algebra
  • Consider the following example:
    • in an unweighted graph represented by an adjacency matrix, how can you compute the number of paths of length 2 between two vertices, using linear algebra

Weitere Betrachtungen:

• [[111.22_Graphen_SSSP_dijkstra]]
• [[111.18_Graphen_Traversieren]]
• [[111.14_Graphen_gerichtet]]
• [[111.21_algo_graphs_ShortesPathProblems]]
• [[222.16_graph_centrality]]