Graph/Nachbarschaftsvergleich/Homomorphismus/Aufgabe

Es sei ${}G=(V,E)$ ein Graph.

1. Zeige, dass für ${}x,y\in V$ die folgenden Eigenschaften äquivalent sind.
   a) Es ist ${}N(x)\subseteq N(y)$.
   b) Für alle ${}z\in V$ folgt aus ${}xz\in E$ auch ${}yz\in E$.
   c) Die Abbildung

   $\varphi \colon V\longrightarrow V$

   mit

   ${}\varphi (u)={\begin{cases}u\,,{\text{ für }}u\neq x\,,\\y\,,{\text{ für }}u=x\,,\end{cases}}\,$

   ist ein Graphhomomorphismus.

2. Es sei ${}xRy$ die Relation aus (1). Welche Eigenschaften einer Ordnungsrelation erfüllt sie, welche nicht?

Zur Lösung, Alternative Lösung erstellen