Zum Inhalt springen

Ungerichteter Graph/Schwacher Homomorphismus/Faktorisierung/Fakt

Aus Wikiversity
Faktorisierungssatz für Graphhomomorphismen

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

Dann gibt es eine Faktorisierung von φ als

G⟶qG/∼⟶r(U,K)⟶s(U,K′)⟶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.