Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 16

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.

Untergraphen

Definition

Ein Graph ${}(W,F)$ heißt Untergraph eines Graphen ${}(V,E)$, wenn ${}W\subseteq V$, ${}F\subseteq E$ und die Kanten aus ${}F$ nur Bezug auf Punkte aus ${}W$ nehmen.

Einen Untergraphen kann man auch durch die beiden Eigenschaften ${}W\subseteq V$ und

${}F\subseteq E\cap {\mathfrak {P}}_{2}\,(W)\,$

charakterisieren. Zu einem Graphen ${}G=(V,E)$ und einer Teilmenge ${}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 ${}G=(V,E)$ gilt ${}(V,\emptyset )\subseteq G\subseteq (V,{\mathfrak {P}}_{2}\,(V))$.

Zum Sprachgebrauch der folgenden Definition vergleiche auch Definition 7.15.

Definition

Ein Untergraph ${}(W,F)\subseteq (V,E)$ heißt 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 induzierten Untergraphen.

Homomorphismen von Graphen

Definition

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ stets ${}\varphi (v)\varphi (v')\in F$ folgt, heißt Graphhomomorphismus.

Ein Homomorphismus von Graphen ist einfach eine relationserhaltende Abbildung, er führt adjazente Knotenpunkte in adjazente Knotenpunkte über. Er wird kurz als ${}\varphi \colon G\rightarrow H$ notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.

Lemma

Eine Hintereinanderschaltung von Graphhomomorphismen ist wieder ein Graphhomomorphismus.

Beweis

Siehe Aufgabe 16.2.

$\Box$

Definition

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$ heißt Isomorphismus, wenn es einen Graphhomomorphismus

$\psi \colon H\longrightarrow G$

derart gibt, dass

${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

und

${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

gilt.

Definition

Zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ heißen isomorph, wenn es einen Graphisomorphismus ${}\varphi \colon G\rightarrow 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.

Definition

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ entweder ${}\varphi (v)=\varphi (v')$ oder aber ${}\varphi (v)\varphi (v')\in F$ folgt, heißt schwacher Graphhomomorphismus.

Konstruktionen für Graphen

Definition

Zu einem Graphen ${}G=(V,E)$ nennt man den Graphen ${}(V,{\mathfrak {P}}_{2}\,(V)\setminus E)$ den komplementären Graphen (oder Komplementärgraph). Er wird mit ${}G^{c}$ bezeichnet.

Es wird also die Knotenmenge übernommen und eine zweielementige Teilmenge ${}\{u,v\}$ ist genau dann eine Kante des komplementären Graphen, wenn sie keine Kante des Ausgangsgraphen ist. Dabei entsprechen sich der vollständige Graph und der 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 ${}{\left(G^{c}\right)}^{c}=G$.

Definition

Zu einem Graphen ${}G=(V,E)$ und einer Teilmenge ${}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 ${}F=\{e\}$ schreibt man abkürzend ${}G\setminus e$ für ${}G\setminus \{e\}$.

Definition

Es sei ${}G=(V,E)$ ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge ${}E$ von ${}G$ ist und bei dem zwei Knoten ${}L_{1}$ und ${}L_{2}$ (also Kanten aus ${}G$) genau dann durch eine Kante verbunden werden, wenn ${}L_{1}$ und ${}L_{2}$ einen gemeinsamen Punkt in ${}V$ besitzen, den Kantengraphen zu ${}G$.

Beispiel

Der Kantengraph zu einem Sterngraph mit ${}n+1$ Punkten, also einem Zentrum mit daran anliegenden ${}n$ Blättern, ist ein vollständiger Graph mit ${}n$ Punkten.

Lemma

Es sei ${}G=(V,E)$ ein Graph und ${}K$ der zugehörige Kantengraph. Dann gelten folgende Aussagen.

1. Die Anzahl der Punkte von ${}K$ ist gleich der Anzahl der Kanten von ${}G$.
2. Der Grad eines Punktes ${}\{u,v\}$ von ${}K$ (also einer Kante von ${}G$) ist

   $d(u)+d(v)-2.$

3. Die Anzahl der Kanten von ${}K$ ist

   ${\frac {1}{2}}\sum _{v\in V}d(v)(d(v)-1).$

Beweis

1. Dies folgt unmittelbar aus der Definition des Kantengraphen.
2. Es sei ${}\{u,v\}$ eine Kante von ${}G$, aufgefasst als Punkt im Kantengraph ${}K$. Dieser Punkt ist mit einem anderen Punkt des Kantengraphen, also einer Kante ${}\{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 ${}\{u,v\}$ nicht mitzählen.
3. Nach Lemma 15.16 ist die gesuchte Anzahl der Kanten in ${}K$ unter Verwendung von Teil (2) gleich

   ${\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.

$\Box$

Äquivalenzrelationen und Quotientengraphen

Definition

Es sei ${}G=(V,E)$ ein Graph, ${}M$ eine Menge und ${}\varphi \colon V\rightarrow M$ eine Abbildung. Unter dem Bildgraphen zu ${}\varphi$ versteht man denjenigen Graphen, dessen Knotenmenge durch das Bild ${}W=\varphi (V)\subseteq M$ von ${}\varphi$ und dessen Kantenmenge durch

${}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.

Lemma

Es sei ${}G=(V,E)$ ein Graph, ${}M$ eine Menge und ${}\varphi \colon G\rightarrow M$ eine Abbildung. Es werde ${}M$ mit der Struktur des Bildgraphen versehen.

Dann ist ${}\varphi$ ein schwacher Homomorphismus von Graphen.

Beweis

Siehe Aufgabe 16.7.

$\Box$

Beispiel

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 (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.

Beispiel

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 (alten oder neuen) Person übernommen werden soll. Dabei sollen sämtliche Kooperationen übernommen werden, das heißt, dass jede Kooperation zwischen zwei (alten) Personen in eine Kooperation der diese Personen ersetzenden (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 „liegt im gleichen Stadtteil“ und im zweiten durch „werden durch eine Person ersetzt“ gegeben.

Definition

Es sei ${}G=(V,E)$ ein Graph und sei ${}\sim$ eine Äquivalenzrelation auf ${}V$. Dann nennt man die Quotientenmenge ${}V/\sim$, versehen mit der Bildgraphstruktur zur kanonischen Abbildung

$V\longrightarrow V/\sim ,$

den Quotientengraphen zu ${}\sim$. Er wird mit ${}G/\sim$ bezeichnet.

Definition

Es sei ${}G=(V,E)$ ein Graph und ${}e\in E$ eine Kante, die die Knotenpunkte ${}u$ und ${}v$ verbindet. Man nennt denjenigen Graphen mit der Knotenmenge ${}V'=V/e$, bei der ${}u$ und ${}v$ miteinander identifiziert werden, und bei dem die Kantenmenge ${}E'$ aus den Bildkanten zur Kontraktionsabbildung ${}V\rightarrow V/e$ besteht, den Kontraktionsgraphen zu ${}e\in G$. Er wird mit ${}G/e$ bezeichnet.

Der Kontraktionsgraph ist einfach der Quotientengraph zur Äquivalenzrelation, bei der ${}u$ und ${}v$ (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.

Lemma

Es sei ${}\varphi \colon G\rightarrow H$ ein schwacher Homomorphismus zwischen den Graphen ${}G=(V,E)$ und ${}H=(W,F)$.

Dann gibt es eine Faktorisierung von ${}\varphi$ als

$G{\stackrel {q}{\longrightarrow }}G/\sim {\stackrel {r}{\longrightarrow }}(U,K){\stackrel {s}{\longrightarrow }}(U,K'){\stackrel {t}{\longrightarrow }}(W,F),$

wobei ${}q$ die Quotientenabbildung zu einer Äquivalenzrelation auf ${}V$ ist, ${}r$ ein Isomorphismus ist, ${}s$ einen knotenidentischen Untergraphen und ${}t$ einen vollen Untergraphen beschreibt.

Beweis

Wir definieren die Äquivalenzrelation ${}\sim$ auf ${}V$ durch ${}u\sim v$, wenn ${}\varphi (u)=\varphi (v)$. Es gibt dann nach Lemma 11.13 eine Abbildung

$\psi \colon V/\sim \longrightarrow W,$

wodurch ${}\varphi$ faktorisiert. Dabei ist ${}\psi$ injektiv und ebenfalls nach der Definition der Kanten auf ${}G/\sim$ ein Graphhomomorphismus. Der Bildgraph zu ${}\psi$ (der auch der Bildgraph von ${}\varphi$ ist), ist ein Untergraph ${}(U,K)$ von ${}H$, der zu ${}G/\sim$ isomorph ist. Wenn man ${}(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$.

$\Box$

Konstruktionen aus mehreren Graphen

Es gibt eine Vielzahl an Möglichkeiten, aus zwei Graphen einen neuen Graphen zusammenzusetzen.

Definition

Zu zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ mit disjunkten Knotenmengen ${}V$ und ${}W$ nennt man den Graphen mit der Knotenmenge ${}V\uplus W$ und der Kantenmenge ${}E\uplus F\subseteq {\mathfrak {P}}\,(V\uplus W)$ die disjunkte Vereinigung der Graphen.

Definition

Zu zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ nennt man den Graphen mit Knotenmenge ${}V\times W$, wobei zwischen zwei Knoten ${}(v_{1},w_{1})$ und ${}(v_{2},w_{2})$ genau dann eine Kante besteht, wenn entweder ${}v_{1}=v_{2}$ und ${}\{w_{1},w_{2}\}\in F$ oder ${}w_{1}=w_{2}$ und ${}\{v_{1},v_{2}\}\in E$ gilt, das kartesische Produkt der Graphen.

Beispielsweise ist das kartesische Produkt von zwei linearen Graphen ein rechteckiger Gittergraph, es gibt dort nur horizontale und vertikale Kanten.

Die Automorphismengruppe eines Graphen

Definition

Es sei ${}G=(V,E)$ ein Graph. Ein Isomorphismus ${}\varphi \colon G\rightarrow G$ heißt Automorphismus.

Definition

Zu einem Graphen ${}G$ nennt man die Gruppe aller Automorphismen

$\varphi \colon G\longrightarrow G$

die Automorphismengruppe von ${}G$. Sie wird mit ${}\operatorname {Aut} \,G$ bezeichnet.

Statt von der Automorphismengruppe spricht man auch von Symmetriegruppe des Graphen.

Beispiel

Die Automorphismengruppe eines Sterngraphen mit einem Zentrum und ${}n\geq 2$ Blättern ist die volle Permutationsgruppe ${}S_{n}$, da man die Blätter beliebig ineinander überführen kann und das Zentrum auf sich selbst abgebildet werden muss.

Beispiel

Wir wollen die Automorphismengruppe des chemischen Elementes Butan (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$ (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 Grad ${}4$ werden mit ${}C$ und die Punkte mit dem Grad ${}1$, also die 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 Gruppenhomomorphismus

$\Psi \colon \operatorname {Aut} \,G\longrightarrow 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

${}\mathbb {Z} /(2)=S_{2}\,$

(in der Tat ist die Spiegelung an der vertikalen Achse ein Automorphismus). Wir haben also einen surjektiven Gruppenhomomorphismus

$\Psi \colon \operatorname {Aut} \,G\longrightarrow 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 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

$S_{3}\times S_{2}\times S_{2}\times S_{3}$

und besitzt ${}144$ Elemente, die gesamte Automorphismengruppe besitzt ${}288$ Elemente.

Definition

Ein Graph ${}G=(V,E)$ heißt homogen, wenn es zu je zwei Knotenpunkten ${}u,v\in V$ einen Automorphismus

$\varphi \colon G\longrightarrow G$

mit

${}\varphi (u)=v\,$

gibt.

Ein homogener Graph sieht in jedem Punkt gleich aus, keine zwei Punkte sind durch graphentheoretische Eigenschaften unterscheidbar. Ein vollständiger Graph und ein leerer Graph sind homogen.

Definition

Ein Graph ${}G=(V,E)$ heißt starr, wenn die Automorphismengruppe von ${}G$ trivial ist.

Bei einem starren Graphen sind je zwei Knotenpunkte graphentheoretisch unterscheidbar. Statt starr sagt man auch asymmetrisch oder rigide.

Beispiel

Der abgebildete Graph ${}G$ ist 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$ (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 (außer ${}b$) haben die Grade ${}2,3,4$, sie müssen also jeweils auf sich selbst abgebildet werden. Dann muss auch der verbleibende Punkt auf sich selbst abgebildet werden.

<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)