Diskrete Mathematik/Gemischte Definitionsabfrage/14/Aufgabe/Lösung

1. Es seien ${}(M,R)$ und ${}(N,S)$ Mengen mit darauf erklärten Relationen ${}R$ bzw. ${}S$. Man nennt eine Abbildung

   $\varphi \colon M\longrightarrow N$

   relationstreu, wenn für alle  ${}x,y\in M$  mit ${}xRy$ auch ${}\varphi (x)S\varphi (y)$ gilt.

2. In einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$ nennt man die durch

   ${}y\geq x\,,$

   falls

   ${}x\sqcap y=x\,,$

   definierte Ordnung, die zugehörige Ordnung.

3. Die Stirling-Zahl zweiter Art ${}S({n},{k})$ ist die Anzahl der Partitionen einer ${}n$-elementigen Menge ${}M$ in ${}k$ Blöcke.
4. Ein Graphhomomorphismus ist eine Abbildug ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus  ${}vv'\in E$  stets  ${}\varphi (v)\varphi (v')\in F$  folgt.
5. Ein Rundgang ist ein Graph, wenn es in ihm einen Kreis ${}v_{1},v_{2},\ldots ,v_{m}=v_{1}$ gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.
6. Eine Knotenüberdeckung  ${}W\subseteq V$  heißt minimal, wenn ${}W\setminus \{w\}$ zu jedem  ${}w\in W$  keine Knotenüberdeckung ist.

Zur gelösten Aufgabe