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