Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 16/latex
\setcounter{section}{16}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Waeller331.jpg} }
\end{center}
\bildtext {Vorli mag so ziemlich alles. Nur Handies findet sie blöd. Sie sind definitiv nix zum Fressen. Aber auch nix zum Spielen, da sie ablenken, ohne zu zerstreuen.} }
\bildlizenz { Waeller331.jpg } {} {Odatrulle} {Commons} {CC-by-sa 4.0} {}
\zwischenueberschrift{Untergraphen}
\inputdefinition
{}
{
Ein Graph
\mathl{(W,F)}{} heißt
\definitionswort {Untergraph}{}
eines
\definitionsverweis {Graphen}{}{}
\mathl{(V,E)}{,} wenn
\mavergleichskette
{\vergleichskette
{W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{F
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Kanten aus $F$ nur Bezug auf Punkte aus $W$ nehmen.
}
Einen Untergraphen kann man auch durch die beiden Eigenschaften
\mavergleichskette
{\vergleichskette
{W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{F
}
{ \subseteq} { E \cap \mathfrak {P}_2 \, (W )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
charakterisieren. Zu einem Graphen
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und einer Teilmenge
\mavergleichskette
{\vergleichskette
{W
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es eine Vielzahl an Untergraphstrukturen, abhängig davon, welche Kanten aus $E$, deren beide Endpunkte zu $W$ gehören, in $F$ übernommen werden und welche nicht. Jede Teilmenge $W$ ist mit der leeren Kantenmenge ein Untergraph. Für jeden Graphen
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskette
{\vergleichskette
{(V, \emptyset)
}
{ \subseteq }{ G
}
{ \subseteq }{ (V, \mathfrak {P}_2 \, (V ) )
}
{ }{
}
{ }{
}
}
{}{}{.}
Zum Sprachgebrauch der folgenden Definition vergleiche auch
Definition 7.15.
\inputdefinition
{}
{
Ein
\definitionsverweis {Untergraph}{}{}
\mavergleichskette
{\vergleichskette
{(W,F)
}
{ \subseteq }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {voll}{,}
wenn jede Kante aus $E$, die Punkte aus $W$ verbindet, auch eine Kante in $F$ ist.
}
Bei einem vollen Untergraphen werden also alle Kanten aus $E$ übernommen, die Bezug auf die Teilmenge $W$ nehmen. Statt von einem vollen Untergraphen spricht man auch von einem \stichwort {induzierten Untergraphen} {.}
\zwischenueberschrift{Homomorphismen von Graphen}
\inputdefinition
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {Graphen}{}{.}
Eine Abbildung
\maabb {\varphi} {V} {W
} {}
mit der Eigenschaft, dass aus
\mavergleichskette
{\vergleichskette
{vv'
}
{ \in }{ E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets
\mavergleichskette
{\vergleichskette
{ \varphi(v) \varphi(v')
}
{ \in }{ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt, heißt
\definitionswort {Graphhomomorphismus}{.}
}
Ein Homomorphismus von Graphen ist einfach eine relationserhaltende Abbildung, er führt adjazente Knotenpunkte in adjazente Knotenpunkte über. Er wird kurz als \maabb {\varphi} {G} {H } {} notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.
{Ungerichteter Graph/Homomorphismus/Erste Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Eine Hintereinanderschaltung von
\definitionsverweis {Graphhomomorphismen}{}{}
ist wieder ein Graphhomomorphismus.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 16.2. }
\inputdefinition
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {Graphen}{}{.}
Ein
\definitionsverweis {Graphhomomorphismus}{}{}
\maabb {\varphi} {G} {H
} {}
heißt
\definitionswort {Isomorphismus}{,}
wenn es einen Graphhomomorphismus
\maabbdisp {\psi} {H} {G
} {}
derart gibt, dass
\mavergleichskettedisp
{\vergleichskette
{ \psi \circ \varphi
}
{ =} {
\operatorname{Id}_{ V }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ \varphi \circ \psi
}
{ =} {
\operatorname{Id}_{ W }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Zwei
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißen
\definitionswort {isomorph}{,}
wenn es einen
\definitionsverweis {Graphisomorphismus}{}{}
\maabb {\varphi} {G} {H
} {}
gibt.
}
Isomorphe Graphen sind hinsichtlich sämtlicher graphentheoretischen Eigenschaften als gleich anzusehen.
Gelegentlich braucht man die folgende Variante eines Graphhomomorphismus, insbesondere, wenn durch eine Kante verbundene Knotenpunkte auf einen Punkt abgebildet werden sollen.
\inputdefinition
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {Graphen}{}{.}
Eine Abbildung
\maabb {\varphi} {V} {W
} {}
mit der Eigenschaft, dass aus
\mavergleichskette
{\vergleichskette
{vv'
}
{ \in }{ E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
entweder
\mavergleichskette
{\vergleichskette
{ \varphi(v)
}
{ = }{ \varphi(v')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder aber
\mavergleichskette
{\vergleichskette
{ \varphi(v) \varphi(v')
}
{ \in }{ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt, heißt
\definitionswort {schwacher Graphhomomorphismus}{.}
}
\zwischenueberschrift{Konstruktionen für Graphen}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man den Graphen
\mathl{(V, \mathfrak {P}_2 \, (V ) \setminus E )}{} den
\definitionswort {komplementären Graphen}{}
\zusatzklammer {oder
\definitionswort {Komplementärgraph}{}} {} {.}
Er wird mit $G^c$ bezeichnet.
}
Es wird also die Knotenmenge übernommen und eine zweielementige Teilmenge
\mathl{\{u,v\}}{} ist genau dann eine Kante des komplementären Graphen, wenn sie keine Kante des Ausgangsgraphen ist. Dabei entsprechen sich der
\definitionsverweis {vollständige Graph}{}{}
und der
\definitionsverweis {kantenfreie Graph}{}{.}
Wenn $G$ $n$ Punkte und $m$ Kanten besitzt, so besitzt $G^c$ gerade $\binom { n } { 2 } -m$ Kanten. Der komplementäre Graph des komplementären Graphes ist wieder der Ausgangsgraph, also
\mavergleichskette
{\vergleichskette
{ { \left( G^c \right) }^c
}
{ = }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und einer Teilmenge
\mavergleichskette
{\vergleichskette
{F
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der Kantenmenge versteht man unter $G \setminus F$ denjenigen Graphen, dessen Punktemenge $V$ ist und dessen Kantenmenge aus $E \setminus F$ besteht.
}
Für
\mavergleichskette
{\vergleichskette
{F
}
{ = }{\{e\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreibt man abkürzend $G \setminus e$ für $G \setminus \{e\}$.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Line_graph_construction_1.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Line_graph_construction_1.svg } {} {Haui, Booyabazooka, Chris-Martin} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Line_graph_construction_2.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Line_graph_construction_2.svg } {} {Haui, Booyabazooka, Chris-Martin} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Line_graph_construction_3.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Line_graph_construction_3.svg } {} {Haui, Booyabazooka, Chris-Martin} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Line_graph_construction_4.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Line_graph_construction_4.svg } {} {Haui, Booyabazooka, Chris-Martin} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge $E$ von $G$ ist und bei dem zwei Knoten
\mathkor {} {L_1} {und} {L_2} {}
\zusatzklammer {also Kanten aus $G$} {} {}
genau dann durch eine Kante verbunden werden, wenn
\mathkor {} {L_1} {und} {L_2} {}
einen gemeinsamen Punkt in $V$ besitzen, den
\definitionswort {Kantengraphen}{}
zu $G$.
}
\inputbeispiel{}
{
Der \definitionsverweis {Kantengraph}{}{} zu einem \definitionsverweis {Sterngraph}{}{} mit $n+1$ Punkten, also einem Zentrum mit daran anliegenden $n$ \definitionsverweis {Blättern}{}{,} ist ein \definitionsverweis {vollständiger Graph}{}{} mit $n$ Punkten.
}
\inputfaktbeweis
{Ungerichteter Graph/Kantengraph/Kantenanzahl/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und $K$ der zugehörige
\definitionsverweis {Kantengraph}{}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Die Anzahl der Punkte von $K$ ist gleich der Anzahl der Kanten von $G$.
}{Der
\definitionsverweis {Grad}{}{}
eines Punktes
\mathl{\{u,v\}}{} von $K$
\zusatzklammer {also einer Kante von $G$} {} {} ist
\mathdisp {d(u)+d(v)-2} { . }
}{Die Anzahl der Kanten von $K$ ist
\mathdisp {{ \frac{ 1 }{ 2 } } \sum_{v \in V} d(v) (d(v)-1)} { . }
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungdrei{Dies folgt unmittelbar aus der Definition des Kantengraphen.
}{Es sei
\mathl{\{u,v\}}{} eine Kante von $G$, aufgefasst als Punkt im Kantengraph $K$. Dieser Punkt ist mit einem anderen Punkt des Kantengraphen, also einer Kante
\mathl{\{r,s\}}{} des Ausgangsgraphen, genau dann verbunden, wenn diese Kante an $u$ oder an $v$ anliegt, wobei nur eines der Fall sein kann. Die Anzahl der an $u$ anliegenden Kanten ist $d(u)$, allerdings dürfen wir die Kante
\mathl{\{u,v\}}{} nicht mitzählen.
}{Nach
Lemma 15.16
ist die gesuchte Anzahl der Kanten in $K$ unter Verwendung von Teil (2) gleich
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ { \frac{ 1 }{ 2 } } \sum_{ \{u,v\} \in E } { \left( d(u)+d(v) -2 \right) }
}
{ =} { { \frac{ 1 }{ 2 } } \sum_{ \{u,v\} \in E } { \left( d(u)-1 +d(v) -1 \right) }
}
{ =} { { \frac{ 1 }{ 2 } } \sum_{ v \in V} d(v) (d(v)-1)
}
{ } {
}
{ } {
}
}
{}{}{,}
da in der mittleren Summe der Term $d(v)-1$ so oft vorkommt, wie es $d(v)$ angibt.
}
\zwischenueberschrift{Äquivalenzrelationen und Quotientengraphen}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{,}
$M$ eine Menge und
\maabb {\varphi} {V} {M
} {}
eine
\definitionsverweis {Abbildung}{}{.}
Unter dem
\definitionswort {Bildgraphen}{}
zu $\varphi$ versteht man denjenigen Graphen, dessen Knotenmenge durch das
\definitionsverweis {Bild}{}{}
\mavergleichskette
{\vergleichskette
{W
}
{ = }{ \varphi(V)
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
}
{}{}{}
von $\varphi$ und dessen Kantenmenge durch
\mavergleichskettedisp
{\vergleichskette
{F
}
{ =} { { \left\{ \{ \varphi(u), \varphi(v)\} \mid \{u,v\} \in E , \, \varphi(u) \neq \varphi(v) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben ist.
}
Man beachte, dass dabei jede Kante nur einfach genommen wird, auch wenn sie im Urbild durch mehrere Kanten repräsentiert sein sollte.
{Ungerichteter Graph/Menge/Abbildung/Bildgraph/Schwacher Homomorphismus/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{,}
$M$ eine Menge und
\maabb {\varphi} {G} {M
} {}
eine
\definitionsverweis {Abbildung}{}{.}
Es werde $M$ mit der Struktur des
\definitionsverweis {Bildgraphen}{}{}
versehen.}
\faktfolgerung {Dann ist $\varphi$ ein
\definitionsverweis {schwacher Homomorphismus}{}{}
von Graphen.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 16.7. }
\inputbeispiel{}
{
Wir betrachten den durch eine U-Bahn in einer Stadt gegebenen Graphen, der aus der Menge der Haltestellen gegeben ist, und bei dem zwei Haltestellen durch eine Kante verbunden werden, wenn sie ohne Umsteigen verbunden sind, also an einer Linie liegen \zusatzklammer {siehe Beispiel 15.5} {} {.} Es ist nicht zu erwarten, dass jede Haltestelle mit jeder anderen Haltestelle durch eine direkte Linie verbunden ist. Die Steuereinnahmen sprudeln kräftig und so möchte man wissen, ob zumindest jeder Stadtteil mit jedem Stadtteil ohne Umsteigen erreichbar ist. Dazu stellt man einen neuen Graphen auf, bei dem die Knotenpunkte die Stadtteile repräsentieren und bei dem zwei Stadtteile genau dann miteinander durch eine Kante zu verbinden sind, wenn es eine Haltestelle im einen und eine Haltestelle im andern Stadtteil gibt, die durch eine U-Bahnlinie verbunden sind.
}
\inputbeispiel{}
{
In einer Firma arbeiten verschiedene Personen $V$, und manche Personenpaare arbeiten gemeinsam an gewissen Aufgaben, was durch einen Kooperationsgraphen ausgedrückt wird. Es steht ein Stellenabbau an, bei dem die Aufgaben von mehreren Personen in Zukunft von einer einzigen \zusatzklammer {alten oder neuen} {} {} Person übernommen werden soll. Dabei sollen sämtliche Kooperationen übernommen werden, das heißt, dass jede Kooperation zwischen zwei \zusatzklammer {alten} {} {} Personen in eine Kooperation der diese Personen ersetzenden \zusatzklammer {neuen} {} {} Personen übertragen werden soll. Der einfachste nichttriviale Spezialfall hiervon ist, dass zwei Personen durch eine Person ersetzt werden und die bisherigen Kooperationen auf diese neue Person übergehen.
}
Die beiden vorstehenden Beispiele werden durch das folgende Konzept erfasst. Die Äquivalenzrelation ist im ersten Beispiel durch \anfuehrung{liegt im gleichen Stadtteil}{} und im zweiten durch \anfuehrung{werden durch eine Person ersetzt}{} gegeben.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und sei $\sim$ eine
\definitionsverweis {Äquivalenzrelation}{}{}
auf $V$. Dann nennt man die
\definitionsverweis {Quotientenmenge}{}{}
$V/\sim$, versehen mit der
\definitionsverweis {Bildgraphstruktur}{}{}
zur
\definitionsverweis {kanonischen Abbildung}{}{}
\maabbdisp {} {V} {V/\sim
} {,}
den
\definitionswort {Quotientengraphen}{}
zu $\sim$. Er wird mit $G/\sim$ bezeichnet.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
und
\mavergleichskette
{\vergleichskette
{e
}
{ \in }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Kante, die die Knotenpunkte
\mathkor {} {u} {und} {v} {}
verbindet. Man nennt denjenigen Graphen mit der Knotenmenge
\mavergleichskette
{\vergleichskette
{V'
}
{ = }{V/e
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
bei der
\mathkor {} {u} {und} {v} {}
miteinander identifiziert werden, und bei dem die Kantenmenge $E'$ aus den Bildkanten zur Kontraktionsabbildung
\maabb {} {V} {V/e
} {}
besteht, den
\definitionswort {Kontraktionsgraphen}{}
zu
\mavergleichskette
{\vergleichskette
{e
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Er wird mit $G/e$ bezeichnet.
} Der Kontraktionsgraph ist einfach der Quotientengraph zur Äquivalenzrelation, bei der \mathkor {} {u} {und} {v} {} \zusatzklammer {zusammen eine Kante bilden und} {} {} zueinander und ansonsten jeder Punkt nur zu sich selbst äquivalent ist. Eine rekursive Argumentation unter Bezug auf Kontraktionsgraphen werden wir in Lemma 18.12 und in Lemma 24.12 verwenden.
\inputfaktbeweis
{Ungerichteter Graph/Schwacher Homomorphismus/Faktorisierung/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\maabb {\varphi} {G} {H
} {}
ein
\definitionsverweis {schwacher Homomorphismus}{}{}
zwischen den
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{(W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es eine Faktorisierung von $\varphi$ als
\mathdisp {G \stackrel{q}{\longrightarrow} G/\sim \stackrel{r}{\longrightarrow} (U,K) \stackrel{s}{\longrightarrow} (U,K') \stackrel{t}{\longrightarrow} (W,F)} { , }
wobei $q$ die
\definitionsverweis {Quotientenabbildung}{}{}
zu einer Äquivalenzrelation auf $V$ ist, $r$ ein
\definitionsverweis {Isomorphismus}{}{}
ist, $s$ einen knotenidentischen Untergraphen und $t$ einen
\definitionsverweis {vollen Untergraphen}{}{}
beschreibt.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir definieren die Äquivalenzrelation $\sim$ auf $V$ durch
\mavergleichskette
{\vergleichskette
{u
}
{ \sim }{v
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wenn
\mavergleichskette
{\vergleichskette
{ \varphi(u)
}
{ = }{ \varphi(v)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es gibt dann nach
Lemma 11.13
eine Abbildung
\maabbdisp {\psi} {V/ \sim} {W
} {,}
wodurch $\varphi$ faktorisiert. Dabei ist $\psi$ injektiv und ebenfalls nach der Definition der Kanten auf $G/\sim$ ein Graphhomomorphismus. Der
\definitionsverweis {Bildgraph}{}{}
zu $\psi$
\zusatzklammer {der auch der Bildgraph von $\varphi$ ist} {} {,}
ist ein Untergraph
\mathl{(U,K)}{} von $H$, der zu $G/\sim$ isomorph ist. Wenn man
\mathl{(U,K)}{} durch die Kanten aus $F$ auffüllt, die zwischen Punkten aus $U$ verlaufen, so erhält man einen knotenpunktgleichen vollen Untergraphen von $H$.
\zwischenueberschrift{Konstruktionen aus mehreren Graphen}
Es gibt eine Vielzahl an Möglichkeiten, aus zwei Graphen einen neuen Graphen zusammenzusetzen.
\inputdefinition
{}
{
Zu zwei
\definitionsverweis {Graphen}{}{}
\mathkor {} {G=(V,E)} {und} {H=(W,F)} {}
mit
\definitionsverweis {disjunkten}{}{}
Knotenmengen
\mathkor {} {V} {und} {W} {}
nennt man den Graphen mit der Knotenmenge
\mathl{V \uplus W}{} und der Kantenmenge
\mavergleichskette
{\vergleichskette
{E \uplus F
}
{ \subseteq }{ \mathfrak {P} \, (V \uplus W )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die
\definitionswort {disjunkte Vereinigung}{}
der Graphen.
}
\inputdefinition
{}
{
Zu zwei
\definitionsverweis {Graphen}{}{}
\mathkor {} {G=(V,E)} {und} {H=(W,F)} {}
nennt man den Graphen mit Knotenmenge
\mathl{V \times W}{,} wobei zwischen zwei Knoten
\mathkor {} {(v_1,w_1)} {und} {(v_2,w_2)} {}
genau dann eine Kante besteht, wenn entweder
\mavergleichskette
{\vergleichskette
{v_1
}
{ = }{v_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \{w_1 , w_2\}
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{w_1
}
{ = }{w_2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \{v_1 , v_2\}
}
{ \in }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, das
\definitionswort {kartesische Produkt}{}
der Graphen.
}
Beispielsweise ist das kartesische Produkt von zwei \definitionsverweis {linearen Graphen}{}{} ein rechteckiger Gittergraph, es gibt dort nur horizontale und vertikale Kanten.
\zwischenueberschrift{Die Automorphismengruppe eines Graphen}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Ein
\definitionsverweis {Isomorphismus}{}{}
\maabb {\varphi} {G} {G
} {}
heißt
\definitionswort {Automorphismus}{.}
}
\inputdefinition
{}
{
Zu einem
\definitionsverweis {Graphen}{}{}
$G$ nennt man die
\definitionsverweis {Gruppe}{}{}
aller
\definitionsverweis {Automorphismen}{}{}
\maabbdisp {\varphi} {G} {G
} {}
die
\definitionswort {Automorphismengruppe}{}
von $G$. Sie wird mit
\mathl{\operatorname{Aut} \, G}{} bezeichnet.
}
Statt von der Automorphismengruppe spricht man auch von Symmetriegruppe des Graphen.
\inputbeispiel{}
{
Die
\definitionsverweis {Automorphismengruppe}{}{}
eines
\definitionsverweis {Sterngraphen}{}{}
mit einem Zentrum und
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {Blättern}{}{}
ist die volle
\definitionsverweis {Permutationsgruppe}{}{}
$S_n$, da man die Blätter beliebig ineinander überführen kann und das Zentrum auf sich selbst abgebildet werden muss.
}
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Butan Lewis.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Butan Lewis.svg } {} {NEUROtiker} {Commons} {Public domain} {}
Wir wollen die
\definitionsverweis {Automorphismengruppe}{}{}
des chemischen Elementes Butan
\zusatzklammer {bzw. der zugehörigen Darstellung als Graph $G$} {} {}
bestimmen. Zunächst halten wir fest, dass die Benennung von einigen Knotenpunkten mit $C$ und mit $H$
\zusatzklammer {was natürlich eine chemische Bedeutung hat} {} {}
keine eigenständige graphentheoretische Information dartellt, da sie ja aus dem Graphen direkt rekonstruierbar ist: Die Punkte mit dem
\definitionsverweis {Grad}{}{}
$4$ werden mit $C$ und die Punkte mit dem Grad $1$, also die
\definitionsverweis {Blätter}{}{,}
werden mit $H$ bezeichnet. In den folgenden Überlegungen werden wir zwecks Vereinfachung die chemischen Benennungen verwenden. Ein Automorphismus des Graphen führt $H$-Atome in $H$-Atome und $C$-Atome in $C$-Atome über, da der Grad bei einem Isomorphismus erhalten bleibt. Dies führt insbesondere zu einem
\definitionsverweis {Gruppenhomomorphismus}{}{}
\maabbdisp {\Psi} { \operatorname{Aut} \, G } { S_4
} {,}
wobei $S_4$ die Gruppe der Permutationen auf den vier $C$-Atomen und $\Psi$ die Einschränkung eines Automorphismus bezeichnet. Bei einem Automorphismus $\varphi$ des Moleküls wird also geschaut, was dieser mit den $C$-Atomen macht. Diese Gesamtzuordnung ist ein Gruppenhomomorphismus. Die vier $C$-Atome haben zwar alle den Grad $4$, sie sind aber nicht gleichberechtigt, die beiden äußeren sind mit drei Blättern und die beiden inneren sind mit zwei Blättern verbunden. Wenn man die beiden inneren vertauscht, so muss man auch die beiden äußeren vertauschen, da ja bei einem Automorphismus Kanten erhalten bleiben. Deshalb ist das Bild von $\Psi$ die zyklische Gruppe
\mavergleichskettedisp
{\vergleichskette
{ \Z/(2)
}
{ =} { S_2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {in der Tat ist die Spiegelung an der vertikalen Achse ein Automorphismus} {} {.}
Wir haben also einen surjektiven Gruppenhomomorphismus
\maabbdisp {\Psi} { \operatorname{Aut} \, G } {S_2
} {.}
Dies erleichtert die Bestimmung der Automorphismengruppe, da man diese aufspalten kann nach solchen Automorphismen, die auf den $C$-Atomen identisch wirken, und solchen, die die $C$-Atome spiegeln. Aufgrund von gruppentheoretischen Gesetzmäßigkeiten gibt es von beiden Sorten gleich viele. Deshalb betrachten wir nur noch den
\definitionsverweis {Kern}{}{}
von $\Psi$. Es sei also $\varphi$ ein Automorphismus, der auf den $C$-Atomen identisch wirkt. Dann wird jedes $H$-Atom unter $\varphi$ auf ein $H$-Atom abgebildet, das mit dem selben $C$-Atom verbunden ist. Was unter $\varphi$ mit den an einem $C$-Atom hängenden $H$-Atomen passiert, ist unabhängig voneinander. Der Kern ist deshalb gleich
\mathdisp {S_3 \times S_2 \times S_2 \times S_3} { }
und besitzt $144$ Elemente, die gesamte Automorphismengruppe besitzt $288$ Elemente.
}
\inputdefinition
{}
{
Ein
\definitionsverweis {Graph}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {homogen}{,}
wenn es zu je zwei Knotenpunkten
\mavergleichskette
{\vergleichskette
{u,v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen
\definitionsverweis {Automorphismus}{}{}
\maabbdisp {\varphi} {G} {G
} {}
mit
\mavergleichskettedisp
{\vergleichskette
{ \varphi(u)
}
{ =} { v
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt.
}
Ein homogener Graph sieht in jedem Punkt gleich aus, keine zwei Punkte sind durch graphentheoretische Eigenschaften unterscheidbar. Ein \definitionsverweis {vollständiger Graph}{}{} und ein leerer Graph sind homogen.
\inputdefinition
{}
{
Ein
\definitionsverweis {Graph}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {starr}{,}
wenn die
\definitionsverweis {Automorphismengruppe}{}{}
von $G$ trivial ist.
} Bei einem starren Graphen sind je zwei Knotenpunkte graphentheoretisch unterscheidbar. Statt starr sagt man auch \stichwort {asymmetrisch} {} oder \stichwort {rigide} {.}
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Identity graph5.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Identity graph5.svg } {} {Hikin1987} {Commons} {Public domain} {}
Der abgebildete Graph $G$ ist
\definitionsverweis {starr}{}{.}
Bei einem solchen Nachweis geht man am besten sukzessive vor, man zeigt für einen Automorphismus unter Bezug auf graphentheoretische Eigenschaften, dass er alle Knoten auf sich selbst abbildet, wobei man mit besonders einfachen Knotenpunkten anfängt und dann weitere Knotenpunkte betrachtet und dabei verwendet, dass andere Knotenpunkte auf sich selbst abgebildet werden. Es sei also $\varphi$ ein Automorphismus von $G$. Der Graph verfügt nur über ein einziges Blatt $b$
\zusatzklammer {links oben} {} {,}
diese muss auf sich selbst abgebildet werden. Damit muss auch der an das Blatt anliegende Knotenpunkt $u$ auf sich selbst abgebildet werden. Die an $u$ anliegenden Knotenpunkte
\zusatzklammer {außer $b$} {} {}
haben die Grade
\mathl{2,3,4}{,} sie müssen also jeweils auf sich selbst abgebildet werden. Dann muss auch der verbleibende Punkt auf sich selbst abgebildet werden.
}