Ungerichteter Graph/Schwacher Homomorphismus/Faktorisierung/Fakt

Faktorisierungssatz für Graphhomomorphismen

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.

Zum Beweis, Alternativen Beweis erstellen