Ungerichtete Graphen/Konstruktionen/Äquivalenzrelation und Quotientengraph/Textabschnitt

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.

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

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 Fakt 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$