Kurs:Diskrete Mathematik (Osnabrück 2026)/Vorlesung 19

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 𝔓_{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, 𝔓_{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. Zu einer Teilmenge $W \subseteq V$ gibt es eine eindeutige volle Untergraphenstruktur auf $W$ . Man spricht auch von der Einschränkung von $G$ auf $W$ .

Definition

Zu einem Graphen $G = (V, E)$ und einer Teilmenge $F \subseteq E$ der Kantenmenge versteht man unter $G ∖ F$ , genannt Restgraph, denjenigen Graphen, dessen Punktemenge $V$ ist und dessen Kantenmenge aus $E ∖ F$ besteht.

Für $F = {e}$ schreibt man abkürzend $G ∖ e$ für $G ∖ {e}$ . Der Restgraph ist ein Untergraph des Ausgangsgraphen mit der gleichen Knotenmenge. Es ist kein voller Untergraph, außer bei $F = \emptyset$ .

Homomorphismen von Graphen

Definition

Es seien $G = (V, E)$ und $H = (W, F)$ Graphen. Eine Abbildung $φ : V \to W$ mit der Eigenschaft, dass aus $v v^{'} \in E$ stets $φ (v) φ (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 $φ : G \to H$ notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.

Lemma

Eine Hintereinanderschaltung von Graphhomomorphismen ist wieder ein Graphhomomorphismus.

Beweis

Siehe Aufgabe 19.2.

◻

Definition

Es seien $G = (V, E)$ und $H = (W, F)$ Graphen. Ein Graphhomomorphismus $φ : G \to H$ heißt Isomorphismus, wenn es einen Graphhomomorphismus

ψ : H ⟶ G

derart gibt, dass

ψ \circ φ = {Id}_{V}

und

φ \circ ψ = {Id}_{W}

gilt.

Definition

Zwei Graphen $G = (V, E)$ und $H = (W, F)$ heißen isomorph, wenn es einen Graphisomorphismus $φ : G \to H$ gibt.

Isomorphe Graphen sind hinsichtlich sämtlicher graphentheoretischer 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 $φ : V \to W$ mit der Eigenschaft, dass aus $v v^{'} \in E$ entweder $φ (v) = φ (v^{'})$ oder aber $φ (v) φ (v^{'}) \in F$ folgt, heißt schwacher Graphhomomorphismus.

Konstruktionen für Graphen

Definition

Zu einem Graphen $G = (V, E)$ nennt man den Graphen $(V, 𝔓_{2} (V) ∖ 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. Der komplementäre Graph des komplementären Graphes ist wieder der Ausgangsgraph, also ${(G^{c})}^{c} = G$ . In diesem Sinne 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.

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.

Die Anzahl der Punkte von $K$ ist gleich der Anzahl der Kanten von $G$ .

Der Grad eines Punktes ${u, v}$ von $K$ (also einer Kante von $G$ ) ist
$d (u) + d (v) - 2.$

Die Anzahl der Kanten von $K$ ist
$\frac{1}{2} \sum_{v \in V} d (v) (d (v) - 1) .$

Beweis

Dies folgt unmittelbar aus der Definition des Kantengraphen.
Es sei ${u, v}$ eine Kante von $G$ , aufgefasst als Punkt im Kantengraphen $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.
Nach Lemma 18.16 ist die gesuchte Anzahl der Kanten in $K$ unter Verwendung von Teil (2) gleich
$\frac{1}{2} \sum_{{u, v} \in E} (d (u) + d (v) - 2) = \frac{1}{2} \sum_{{u, v} \in E} (d (u) - 1 + d (v) - 1) = \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.

◻

Äquivalenzrelationen und Quotientengraphen

Definition

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

F = {{φ (u), φ (v)} ∣ {u, v} \in E, φ (u) \neq φ (v)}

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 $φ : G \to M$ eine surjektive Abbildung. Es werde $M$ mit der Struktur des Bildgraphen versehen.

Dann ist $φ$ ein schwacher Homomorphismus von Graphen.

Beweis

Siehe Aufgabe 19.10.

◻

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 18.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 soll.

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 Bildgraphenstruktur zur kanonischen Abbildung

V ⟶ 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 \to V / e$ besteht, den Kontraktionsgraphen zu $e$ . 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 21.11 und in Lemma 26.13 verwenden.

Lemma

Es sei $φ : G \to H$ ein schwacher Homomorphismus zwischen den Graphen $G = (V, E)$ und $H = (W, F)$ .

Dann gibt es eine Faktorisierung von $φ$ als

$G \overset{q}{⟶} G / \sim \overset{r}{⟶} (U, K) \overset{s}{⟶} (U, K^{'}) \overset{t}{⟶} (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 $φ (u) = φ (v)$ . Es gibt dann nach Lemma 11.13 eine Abbildung

ψ : V / \sim ⟶ W,

wodurch $φ$ faktorisiert. Dabei ist $ψ$ injektiv und ebenfalls nach der Definition der Kanten auf $G / \sim$ ein Graphhomomorphismus. Der Bildgraph zu $ψ$ (der auch der Bildgraph von $φ$ 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$ .

◻

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 ⊎ W$ und der Kantenmenge $E ⊎ F \subseteq 𝔓 (V ⊎ 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. Es wird mit $G ◻ H$ bezeichnet.

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 $φ : G \to G$ heißt Automorphismus.

Definition

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

φ : G ⟶ G

die Automorphismengruppe von $G$ . Sie wird mit $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 (also insgesamt $n + 1$ Knoten) 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 darstellt, 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

Ψ : Aut G ⟶ S_{4},

wobei $S_{4}$ die Gruppe der Permutationen auf den vier $C$ -Atomen und $Ψ$ die Einschränkung eines Automorphismus bezeichnet. Bei einem Automorphismus $φ$ 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 $Ψ$ die zyklische Gruppe

ℤ / (2) = S_{2}

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

Ψ : 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 Kern von $Ψ$ . Es sei also $φ$ ein Automorphismus, der auf den $C$ -Atomen identisch wirkt. Dann wird jedes $H$ -Atom unter $φ$ auf ein $H$ -Atom abgebildet, das mit demselben $C$ -Atom verbunden ist. Was unter $φ$ 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

φ : G ⟶ G

mit

φ (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 $φ$ 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 2026) \| >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)