Grundbegriffe der Graphentheorie 1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
Ralf Zücker,
Frank Ehrlich
=Relevanz und Motivation=
==Entstehung von Theorien und Modellen==
* Meist aus einem praktischen Problem heraus
* Zusammentragen aller Fakten die damit irgendwie zu tun haben
* Weglassen aller Dinge die keinen direkten Einfluss haben
* Verallgemeinerung / Abstraktion
* Finden von Ähnlichkeiten mit bekannten einfacheren Dingen
* Entwurf eines Modells mit diesen einfacheren Dingen
* Verhältnismäßig einfache Bestimmung von übertragbaren Eigenschaften und Konsequenzen
==Leonard Euler 1737==
* Problem der Königsberger Brücken
* Weglassen von Entfernungen und Ausmaßen
* Einfluss haben nur Stadtteile und Brücken
* Abstraktion zu Punkten mit Verbindungslinien
* Lösung des Problems mit Punkten und Verbindungen löst auch das Problem mit Stadtteilen und Brücken
* Entstehung des Graphenmodells
==Die Graphentheorie als Modell==
* Sehr minimalistisch, nur Punkte mit Verbindungen
* Dadurch übertragbar auf alle Arten von Beziehungen zwischen Objekten
** Städte und Zugverbindungen
** Freundschaften zwischen Menschen
** Verlinkung von Internetseiten
* Viele praktische Probleme lassen sich zu einem Graphenproblem umformulieren
** Ausfallwahrscheinlichkeit von Netzwerken
** Routenermittlung bei der Navigation
** Einstufung der Wichtigkeit von Einzelnen in einer Gruppe
* Graphentheorie stellt bereits Lösungen zur Verfügung
* Meist ist "nur noch" eine Interpretation erforderlich
==Arbeiten mit dem Graphenmodell==
* Mathematik des Modells ist gut dokumentiert
* Kritisch sind die Transformationen
** Formulierung eines praktischen Problems im Graphenmodell
** Interpretation des mathematischen Ergebnisse für die Praxis
* Falsche Formulierung oder falsche Interpretation liefert keine Problemlösung
* Zeitverteilung eines Softwareentwicklers: 10% tippen, 90% denken
* Gute Programmierer denken immer abstrakt (also in Modellen)
* Wenn man viele Modelle kennt, muss man sich selbst keine ausdenken
* Die Einfachheit der Graphentheorie macht sie zu einem Universalmodell
=Knoten und Kanten=
;Definition Graph
:$\color{red}G=\color{blue}(V,E\color{blue}),~V=\color{green}\{v\color{green}\},~V \color{orange}{\neq \emptyset},~E=\color{green}\{~\color{brown}\{x,y\color{brown}\}~\color{magenta}|~x,y \in V~\color{green}\}$*
<popup name="*">
Es handelt sich um die Definition eines einfachen Graphen ohne Schleifen, Mehrfachkanten und Richtungsgebundenheit.
</popup>
:'''Gelesen:''' Ein $\color{red}{Graph}$ ist ein $\color{blue}{geordnetes~Paar}$, wobei dessen erstes Element eine $\color{green}{Menge}$ ist, welche $\color{orange}{nicht~leer}$ sein darf, und dessen zweites Element eine $\color{green}{Menge}$ von $\color{brown}{Zweiermengen}$ ist, $\color{magenta}{mit~der~Eigenschaft,~dass}$ die Zweiermengenelemente in der ersten Menge enthalten sein müssen.
* $V$ (für ''Vertices'') ist die Menge der Knoten
* $E$ (für ''Edges'') ist die Menge der Kanten
* '''Man beachte:''' Es ist nicht festgelegt, was $v$ eigentlich ist!
* Zur grafischen Darstellung bieten sich Punkte und Linien an
* Welche der Darstellungen repräsentieren Graphen?<br/>
[[Bild:RaZ_Graphen.png|800px]]
<popup name="Lösung">Alle außer b) und c)</popup>
==Konsequenzen==
* Ein Graph muss mindestens einen Knoten enthalten
* Ein Graph muss nicht unbedingt Kanten haben
* Eine Kante muss immer durch 2 (nicht zwingend verschiedene) Knoten begrenzt sein
* Zwei Graphen sind gleich, wenn sie die gleichen Knoten enthalten, die durch die gleichen Kanten verbunden sind
* Adjazenz = Nachbarschaft = Es gibt etwas trennendes dazwischen
** Nur zwischen Knoten und Knoten bzw. zwischen Kante und Kante
** Dazwischen ist immer eine Kante oder ein Knoten
* Inzidenz = Angrenzung = Es gibt direkten Kontakt
** Nur zwischen Knoten und Kante
* $n$ für Anzahl der Knoten
* $m$ für Anzahl der Kanten
==In der Praxis==
* Knoten und Kanten werden immer als Objekte mit Beziehungen interpretiert
* Dadurch werden die Konsequenzen intuitiv klar
* Erst wenn es ein Objekt gibt, kann man etwas darüber aussagen: "ist allein"
* Zwei Objekte ohne Verbindung sind auch sinnvoll: "nicht allein, aber isoliert"
* Eine Beziehung findet per Definition immer zwischen Objekt'''en''' statt
* Objekte müssen dabei nicht zwingend verschieden sein (z.B. Besitzer$\leftrightarrow$Eigentümer)
==Modellierung==
* Transformation einer Gegebenheit/eines Problems ins Graphenmodell
* Scheinbar offensichtlich (Computernetzwerke, Straßen, Facebook-Freundschaften)
* In der Praxis: Immer abhängig von der Problemstellung!
* z.B. Kabelverlegung in einem Haus
** Wie verlegt man die Kabel, sodass die verwendete Gesamtkabellänge minimal ist?
** Wie teile ich eine 50m Kabelrolle auf, sodass der Verschnitt möglichst gering ist?
* Kein Patentrezept um von der konkreten Problemstellung zum abstrakten Graphenmodell zu gelangen
* Hilfreiche Fragen die man sich stellen kann
** Welches Ergebnis wird gebraucht?
** Welches Ergebnis der Graphentheorie soll genutzt werden?
* Oft helfen Zwischen-Abstraktionen anstatt direkt zu Knoten und Kanten zu abstrahieren
** Zustände und deren Übergänge
** Situationen und deren Änderung
* Grafische Darstellung von Graphen kann geometrische Körper ergeben
=Programmiertechnische Verarbeitung=
* Wie bilde ich das gestellte Problem programmtechnisch ab?
*# Mathematische Analyse ($\rightarrow$ mathematische Grundalgorithmus)
*# Verbesserung des Algorithmus (dynamic programming, divide & conquer, ...)
*# Definition der Datenstruktur zur effizienten Unterstützung des Algorithmus
* Wahl der Datenstruktur immer nach Anforderungen des Algorithmus
* Speicherbedarf vs. Effizienz
==Naive Herangehensweise==
* Streng nach Definition: Menge von Knoten + Menge von Kanten (zwischen Knoten)<br/><code id="562384e909645">
class Graph{
int[] vertices;
Edge[] edges;
}
class Edge{
int from;
int to;
}
</code>
* Kante von a nach b vorhanden? $\mathcal{O}(m)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(m)$
* Speicherbedarf $\mathcal{O}(n+2m)$
==Adjazenzmatrix==
* Matrix der Größe $n\times n$, 0 oder 1 für jedes Punkte-Paar<br/>[[Bild:RaZ_GraphMatrix.png|500px]][[Bild:RaZ_AdjazenzMatrix.png|300px]]
* Kante von a nach b vorhanden? $\mathcal{O}(1)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(n)$
* Speicherbedarf $\mathcal{O}(n^2)$ (oder doch etwas weniger möglich?)
* Codebeispiel:<br/><code id="5626b165b8dff">
class Graph<T>{
T[][] adjacency;
}
</code>
* Speicherbedarf unabhängig von der Kantenanzahl
* Bei großen Graphen nicht mehr möglich
==Adjazenzliste==
* Weglassen der Nullen in der Adjazenzmatrix
* Liste der Knoten mit deren Nachbarn<br/>[[Bild:RaZ_GraphMatrix.png|500px]][[Bild:RaZ_Adjazenzliste.png|380px]]
* Kante von a nach b vorhanden? $\mathcal{O}(n)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(1)$
* Speicherbedarf $\mathcal{O}(n+m)$
* Codebeispiel:<br/><code id="5626b165b8ea9">
class Graph<T>{
int[] neighborIndex;
T[] neighbors;
}
</code>
** Für jeden Knoten ein <tt>neighborIndex</tt> wo in <tt>neighbors</tt> seine adjazenten Knoten abgelegt sind<br/>
** Knoten ohne Nachbar erkennbar wenn der Folgeknoten den gleichen <tt>neigborIndex</tt> hat<br/>Achtung! Sonderbehandlung des letzten Knotens
* weniger Speicherbedarf als Adjazenzmatrix wenn Graph nicht vollständig
==Kantenliste==
* Nur die Kanten (zwischen 2 Knoten) werden gehalten<br/>[[Bild:RaZ_GraphMatrix.png|500px]][[Bild:RaZ_Kantenliste.png|380px]]
* Kante von a nach b vorhanden? $\mathcal{O}(m)$
* Anzahl anliegender Kanten am Knoten? $\mathcal{O}(m)$
* Speicherbedarf $\mathcal{O}(m)$
* Codebeispiel:<br/><code id="5626b165b8f32">
class Graph<T>{
T[][] edges; // second dimension is 2
}
</code>
* Speicherbedarf unabhängig von der Knotenanzahl
* keine Unterstützung isolierter Knoten
==In der Praxis==
* Knoten und Kanten sind meist komplexere Datenstrukturen (beliebige Klassen)
* Bei Algorithmenimplementation ''generics'' bzw. ''templates'' benutzen
* Hilfsdatenstrukturen '''richtig''' verwenden (HashMap, HashSet)
* Redundanz vermeiden (Speicherbedarf minimieren), oder auch explizit nutzen (Effizienzsteigerung)
=Grad eines Knotens=
;Definition
:$\color{red}d(\color{orange}v) = \color{blue}|~\color{green}\{~\color{brown}\{\color{orange}v,x\color{brown}\}~\color{magenta}{|~\{v,x\} \in E}~\color{green}\}~\color{blue}|$*
<popup name="*">
Es wird der Knotengrad in einem schlichten Graphen definiert ohne Schleifen, Mehrfachkanten und Richtungsgebundenheit.
</popup>
:'''Gelesen:''' Der $\color{red}{Grad}$ eines $\color{orange}{Knotens}$ ist die $\color{blue}{Kardinalität}$ der $\color{green}{Menge}$ von $\color{brown}{Zweiermengen}$, die diesen $\color{orange}{Knoten}$ enthalten und $\color{magenta}{in~E~enthalten~sind}$.
[[Bild:RaZ_Degree.png|800px]]
<popup name="Regularität">
Alle außer h) sind regulär und von diesen sind alle außer i) stark regulär.
</popup>
* Einzelner Knoten ohne anliegende Kanten hat Grad 0 (isolierter Knoten)
* Schleife an einem Knoten erhöht den Grad um 2
* Haben alle Knoten den gleichen Grad ist der Graph regulär<br/>genauer: bei Grad k $\rightarrow$ k-regulär
* Stark regulär:
** 2 benachbarte Knoten haben immer gleich viele gemeinsame Nachbarknoten und
** 2 '''nicht''' benachbarte Knoten haben immer gleich viele gemeinsame Nachbarknoten
* Ein Graph hat: Minimalgrad, Maximalgrad, Durchschnittsgrad
* Wichtig: $\sum_{i=1}^n d(v_i)=2\cdot m$
** Summe aller Grade entspricht doppelter Kantenanzahl im Graph
** Da jede Kante den Grad ihrer 2 angrenzenden Knoten um 1 erhöht
* Daraus folgt: Anzahl der Knoten mit ungeradem Grad muss gerade sein
<popup name="Beweis">
# Summe aller Grade ist $\color{blue}{gerade}$ wegen $\textbf{2}\cdot m$
# Summe aller $\color{blue}{geraden}$ Grade ist auch $\color{blue}{gerade}$
# Wegen 1. muss die Summe aller $\color{red}{ungeraden}$ Grade auch $\color{blue}{gerade}$ sein
# Wegen 3. muss die Anzahl der Knoten mit $\color{red}{ungeradem}$ Grad $\color{blue}{gerade}$ sein
</popup>
* Praktisch: schnelle Überprüfbarkeit einer Aussage<br/>Unter 7 Unternehmen unterhält jedes Geschäftsbeziehungen zu genau 3 anderen Unternehmen. Möglich?
<popup name="Antwort">
Nein! Denn es würden 7 Knoten mit jeweils 3 abgehenden Kanten enstehen, also 7 Knoten mit jeweils Grad 3.
Das ist eine ungerade Anzahl von ungeraden Graden und somit nicht möglich.
</popup>
=Isomorphie=
* Gleichstrukturiertheit von Graphen $G \sim G'$
* Grafische Darstellung der Graphen kann ineinander überführt werden (Morphing)
* Achtung: Isomorphie $<>$ Gleichheit
** Knotennamen für Isomorphie irrelevant
** Ebenso Kantenbewertungen
** Aber: Kantenrichtungen dürfen nicht ignoriert werden
*Algorithmische Prüfung auf Isomorphie <span style="font-size:88%">''($\mathcal{O}$ per Adjazenzmatrix)''</span>
** Anzahl der Knoten muss gleich sein $=\mathcal{O}(1)$
** Anzahl der Kanten bzw. Summe der Grade muss gleich sein $=\mathcal{O}(n^2)$
* Das reicht aber noch nicht!<br>[[Bild:RaZ_NotIso.png|500px]]
** Die Adjazenzmatrix muss gleich sein von mindestens einer ihrer '''Permutationen''' $=\mathcal{O}(n!)$
** Optimierung lt. Ullmann: Partitionieren! (Gruppierung von Knoten mit gleichem Grad)<br/>Dadurch statt $9!=362.880$ Möglichkeiten, Einschränkung auf z.B. $2!\cdot 7!=10.080$ Möglichkeiten
** Hier gibts einen Ferrari zu holen...
=Kantenzug, Wege, Kreise und Zusammenhang=
==Kantenzug==
;Definition Kantenzug
Für n ≥ 2 nennt man einen Graphen $P_n$ mit einer Folge von Knoten $V(P_n)$ = ($v_0$, $v_1$, . . . , $v_n$) und
einer Folge von Kanten $E(P_n)$ = ({$v_0$, $v_1$}, {$v_1$, $v_2$}, . . . , {$v_{n−1}$, $v_n$})
einen Kantenzug der Länge $n$.
Also: Knoten und Kanten können mehrfach durchlaufen werden.
[[Bild:Ghx8 ;_Kantenzug.png|800px]]
* Kantenzug: {B,C,E,F,G,H,F,E,D}
;Geschlossener Kantenzug
Ein geschlossener Kantenzug ist ein Kantenzug mit $v_0$ = $v_n$.
[[Bild:Ghx8 ;_GeschlKantenzug.png|800px]]
* Geschlossener Kantenzug: {B,C,E,F,G,H,F,E,D,B}
==Weg==
;Definition Weg
Für n ≥ 2 nennt man einen Graphen $P_n$ mit der Knotenmenge $V(P_n)$ = {$v_0$, $v_1$, . . . , $v_n$} oder auch einer Folge von Knoten $V(P_n)$ = ($v_0$, $v_1$, . . . , $v_n$) und
der Kantenmenge
$E(P_n)$ = {{$v_0$, $v_1$}, {$v_1$, $v_2$}, . . . , {$v_{n−1}$, $v_n$}}
einen Weg (oder Pfad) der Länge $n$, sofern keine Kante mehrfach durchlaufen wird. Knoten
hingegen dürfen bei einem Weg mehrfach vorkommen.
Also: Bei einem Weg dürfen die Knoten mehrfach und die Kanten nur einmal durchlaufen werden.
[[Bild:Ghx8 ;_WegCEFGJF.png|800px]]
* Weg: {C,E,F,G,J,F}
;Definition Einfacher Weg
Für n ≥ 2 nennt man einen Graphen $P_n$ mit der Knotenmenge $V(P_n)$ = {$v_0$, $v_1$, . . . , $v_n$} und
der Kantenmenge $E(P_n)$ = {{$v_0$, $v_1$}, {$v_1$, $v_2$}, . . . , {$v_{n−1}$, $v_n$}}
einen einfachen Weg der Länge $n$, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.
Also: Bei einem einfachen Weg dürfen die Knoten und Kanten nur einmal durchlaufen werden.
[[Bild:Ghx8 ;_EinfacherWegCEFG.png|800px]]
* Einfacher Weg: {C,E,F,G}
==Kreise==
;Definition Kreis
Für n ≥3 heißt der Graph $C_n$ mit $V(P_n)$ = {$v_0$, $v_1$, . . . , $v_n$}, oder auch $V(P_n)$ = ($v_0$, $v_1$, . . . , $v_n$), und $E(C_n)$ = {{$v_0$, $v_1$}, {$v_1$, $v_2$}, . . . , {$v_{n−1}$, $v_n$}} Kreis der Länge $n$.
Also: Ein Kreis ist ein geschlossener Weg mit $v_o = v_n$, mit mindestens drei Knoten.
[[Bild:Ghx8_;_KreisFGJIHF.png|800px]]
* Kreis: {F,G,J,I,H,J,F}
;Definition Einfacher Kreis
Für n ≥ 3 nennt man einen Graphen $P_n$ mit der Knotenmenge $V(P_n)$ = {$v_0$, $v_1$, . . . , $v_n$} und
der Kantenmenge $E(C_n)$ = {{$v_0$, $v_1$}, {$v_1$, $v_2$}, . . . , {$v_{n−1}$, $v_n$}}
einen einfachen Weg (oder Pfad) der Länge $n$, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.
Also: Ein einfacher Kreis ist ein geschlossener einfacher Weg mit $v_o = v_n$, mit mindestens drei Knoten.
[[Bild:Ghx8 ;_EinfacherKreisFGJF.png|800px]]
* Einfacher Kreis: {F,G,J,F}
==Zusammenhang bei Graphen==
;Definition
Ein Graph ist zusammenhängend, falls es zu je zwei verschiedenen Knoten $v,w∈V(G)$ einen Weg auf $G$ mit $v$ und $w$ als Endknoten gibt. Ein maximal zusammenhängender Teilgraph von $G$ heißt Zusammenhangskomponente von $G$.
[[Bild:Ghx8 ;_Zusammenhang.png|400px]]
==Übung==
[[Bild:Ghx8 ;_UbungA.png|400px]]
{| class="wikitable"
|-
! Knoten !! Kantenzug !! geschlossener Kantenzug !! einfacher Weg !! Weg !! einfacher Kreis !! Kreis
|-
|{G,C,A,G,F,E,G} || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>ja</popup>
|-
|{G,H} || <popup>nein</popup>|| <popup>nein</popup> || <popup>ja</popup> ||<popup>ja</popup>|| <popup>nein</popup> ||<popup>nein</popup>
|-
|{D,G,B,D,F,G,B,A} || <popup>ja</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>nein</popup>
|-
|{G,B,A,G,H} || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>ja</popup>|| <popup>nein</popup> ||<popup>nein</popup>
|-
|{A,B,D,G,A} || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>ja</popup> ||<popup>ja</popup>
|-
|{G,B,A,G,B,A,G} || <popup>nein</popup>|| <popup>ja</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>nein</popup>
|}
=Strukturelle Umformungen=
==Entfernen von Knoten und Kanten==
[[Bild:Ghx8 ;_Obergraph.png|800px]]
*Obergraph
;Definition Enfernen von Kanten
Es sei $G = (V,E)$ ein Graph. Das Entfernen einer Kante $e ∈ E$ erzeugt aus $G$ einen neuen Graphen $G - e = (V,E~$\$~,\{e\})$. Wenn $F ∈ E$ eine Kantenteilmenge des Graphen $G = (V,E)$ ist, so sei $G - F$ der Graph, der aus $G$ durch Entfernen aller Kanten aus $F$ hervorgeht.
Also: Entfernung einer Kante -> neuer Graph bzw. Graphen
[[Bild:Ghx8 ;_Kantenentfernung.png|800px]]
;Definition Enfernen von Knoten
Als einen Knoten $v ∈ V$ wird $G - v$ als der Graph definiert, der aus $G$ durch Entfernen des Knotens $v$ hervorgeht. Das Entfernen eines Knotens $v$ schließt hierbei das gleichzeitige Entfernen aller zu $v$ inzidenten Kanten des Graphen ein.
Also: Entfernung eines Knoten -> neuer Graph, hierbei das gleichzeitige Entfernen aller zum Knoten inzidenten Kanten.
[[Bild:Ghx8 ;_Knotenentfernung.png|800px]]
==Kontraktion==
;Definition Kontraktion
Die Kontraktion einer Kante $e = \{u,v\}$ eines Graphen $G$ ist das Entfernen von $e$ mit der anschließenden Fusion der Endknoten $u$ und $v$.
* dadurch Wegverkürzung
* wenn Endknoten = Endknoten des Weges -> Weglänge = 0
* wenn die Kante nicht auf dem Weg liegt, dann bleibt der Weg erhalten
* Folge: Ein Graph ist genau dann zusammenhängend, wenn durch eine Folge von Kontraktionen nur ein Knoten übrig bleibt.
[[Bild:Ghx8 ;_KontraktionVorher.png|800px]]
* Obergraph
[[Bild:Ghx8 ;_Kontraktion.png|800px]]
* Nach Kontraktion
==Artikulationen (= Knoten)==
;Definition
Es sei $c(G)$ die Anzahl der Komponenten eines Graphen $G$. Ein Knoten $v ∈ V$ mit der Eigenschaft $c(G-v) > c(G)$ heißt eine Artikulation von $G$.
Also: Wenn durch Entfernung eines Knotens der Graph in zwei oder mehrere Komponenten zerfällt.
[[Bild:Ghx8 ;_KritischerKnotenVor.png|800px]]
* Kritische Knoten: blau
[[Bild:Ghx8 ;_KritischerKnotenNach.png|800px]]
* Nach Entfernung der kritischen Knoten
==Brücken (= Kanten)==
;Definition
Es sei $c(G)$ die Anzahl der Komponenten eines Graphen $G$. Eine Kante $e ∈ E$ eines Graphen $G = (V,E)$ mit der Eigenschaft $c(G-e) > c(G)$ heißt eine Brücke von $G$.
Also: Wenn durch Entfernung einer Kante der Graph in zwei oder mehrere Komponenten zerfällt.
[[Bild:Ghx8 ;_KritischerKanteVor.png|800px]]
* kritische Kante: blau
[[Bild:Ghx8 ;_KritischerKanteNach.png|800px]]
* Nach Entfernung der Brücke
==Übung==
[[Bild:Ghx8 ;_UbungA.png|400px]]
* Was passiert bei Entfernung einer Kante bzw. Knoten
** Siehe Definition
* Was passiert bei Kontraktion?
** Siehe Definition
* Wo ist die Artikulation?
** Antwort: {G}
* Wo ist die Brücke?
** Antwort: Kante {G,H}
=Vollständige Graphen=
;Definition
Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig.
Also: Alle Knoten sind miteinander verbunden
[[Bild:Ghx8 ;_VollständigerGraph.png|800px]]
[[Bild:Ghx8 ;_VollständigerGraphB.png|800px]]
=Teilgraph und Untergraph=
==Teilgraph==
;Definition
Es sei $G = (V_G,E_G)$ ein Graph. Ein Teilgraph von $G$ ist ein Graph $H = (V_H,E_H)$, dessen Knotenmenge $E_H\subseteq E_G$ ist.
Also: Ein Teilgraph ist ein Ausschnitt aus einem Graphen, bei der Kanten zwischen den Knoten fehlen können.
* Jeder Untergraph ist auch ein Teilgraph, aber nicht umgekehrt!
[[Bild:Ghx8 ;_UUUntergraph.png|300px]] [[Bild:Ghx8 ;_TeilgraphB.png|300px]] [[Bild:Ghx8 ;_TTeilgraph.png|300px]]
==induzierter Teilgraph = Untergraph==
Ein induzierter Teilgraph entsteht, wenn beim Obergraphen ein oder mehrere Knoten samt dessen inzidenten Kanten entfernt werden.
[[Bild:Ghx8 ;_InduzierterTeilgraph.png|800px]]
==Untergraph==
Ein Untergraph ist ein Ausschnitt aus einem Graphen, dessen Knoten samt dessen inzidenten Kanten erhalten bleiben. Ein Untergraph wird auch als Clique bezeichnet.
[[Bild:Ghx8 ;_UUUntergraph.png|300px]]
==spannender Teilgraph==
Beim spannenden Teilgraphen bleiben alle Knoten des Obergraphen erhalten. Die Knoten sind dabei zusammenhängend.
[[Bild:Ghx8 ;_SpannenderTeilgraph.png|800px]]
==Übung==
[[Bild:Ghx8 ;_UbungA.png|400px]]
Welche Untergraphen gibt es?
*Antwort: {A,B,D,E,F,E} oder {G,B,A}
Welche Teilgraphen gibt es?
*Antwort: {G,B,A} oder {G,B,A} ohne Kante {A,B}
Skizziere induzierte Teilgraphen!
<gallery widths="300px" heights="300px">
Bild:Ghx8 ;_InduzierteTeilgraphA.png
Bild:Ghx8 ;_InduzierteTeilgraphB.png
</gallery>
Wie sieht der spannende Teilgraph aus?
[[Bild:Ghx8 ;_SpannendeTeilgraph.png|400px]]
=Grundlegende Graphenoperationen=
Besonders häufig werden die üblichen Operationen der Mengenlehre (Vereinigung, Durchschnitt, Differenz und Komplement) auf Knoten- bzw. Kantenmengen von Graphen angewendet.
==Operation: Durchschnitt==
$G\cap G' = V(G)\cap V(G'), E(G)\cap E(G')$, wenn es Knoten und Kanten von $G$ und $G'$ gibt, die übereinstimmen.
Also: Es bleiben nur die Knoten und Kanten erhalten, welche beide Graphen enthalten.
<gallery widths="250px" heights="300px">
Bild:Ghx8 ;_Vereinigung.png|Graph $G$ und $G'$
Bild:Ghx8 ;_Schnitt.png|$G\cap G'$
</gallery>
==Operation: Vereinigung==
$G\cup G' = V(G)\cup V(G'), E(G)\cup E(G')$, wenn es Knoten und Kanten von $G$ und $G'$ gibt, die übereinstimmen.
Also: Zwei Graphen werden durch gleichen Knoten und Kanten vereinigt.
<gallery widths="250px" heights="300px">
Bild:Ghx8 ;_Vereinigung.png|Graph $G$ und $G'$
Bild:Ghx8 ;_VereinigungB.png| $G\cup G'$
Bild:Ghx8 ;_Schnittdisj.png|$G \sqcup G'$ = disjunkte Vereinigung
</gallery>
==Operation: Differenz==
$G\backslash G' = V(G)\backslash V(G'), E(G)\backslash E(G')$
Also: Es bleiben die Knoten und Kanten erhalten, welche nur $G$ besitzt.
<gallery widths="250px" heights="300px">
Bild:Ghx8 ;_Vereinigung.png|Graph $G$ und $G'$
Bild:Ghx8 ;_Differenz.png|$G \setminus G'$
</gallery>
==Operation: Komplement==
Der Komplementärgraph $\overline{G}$ eines Graphen $G$ hat die selbe Knotenmenge wie der Ausgangsgraph. In $\overline{G}$ sind genau zwei Knoten adjazent, wenn sie in $G$ nicht adjazent sind.
<gallery widths="250px" heights="300px">
Bild:Ghx8 ;_Vereinigung.png|$G$ und $G'$
Bild:Ghx8 ;_KKomplement.png|$\overline{G}$ und $\overline{G'}$
</gallery>
==Übung==
[[Bild:Ghx8 ;_LetzteUbung.png]]
Welcher Graph entsteht durch die Bildung des Durchschnitts?
[[Bild:Ghx8 ;_LetzteUbungB.png|50px]]
Welcher Graph entsteht durch Vereinigung?
[[Bild:Ghx8 ;_LetzteUbungA.png|200px]]
Welcher Graph entsteht durch Differenz?
[[Bild:Ghx8 ;_LetzteUbungC.png|200px]]
Wie sehen die komplementären Graphen aus?
[[Bild:Ghx8 ;_LetzteUbungD.png|600px]]
= <b><font color="black"> Quellen </font color></b> =
* Turau, 2009, Algorithmische Graphentheorie
* Krischke/Röpcke, 2015, Graphen und Netzwerktheorie
* Tittmann, 2003, Graphentheorie
* https://books.google.de/books?id=Og8dBgAAQBAJ&pg=PA103&dq=graph+differenz&hl=de&sa=X&ved=0CDUQ6AEwBGoVChMI6-z8s87iyAIVxPNyCh0iFwtU#v=onepage&q=vereinigung&f=false
* https://books.google.de/books?id=Og8dBgAAQBAJ&pg=PA103&dq=graph+differenz&hl=de&sa=X&ved=0CDUQ6AEwBGoVChMI6-z8s87iyAIVxPNyCh0iFwtU#v=onepage&q=graph%20differenz&f=false