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

1. Eine Permutation ${}\sigma$ auf ${}M$ ist eine bijektive Abbildung

   $\sigma \colon M\longrightarrow M.$

2. Die Abbildung

   $F\colon M_{1}\longrightarrow M_{2},$

   heißt ordnungstreu, wenn für alle  ${}x,x'\in M_{1}$  mit  ${}x\leq _{1}x'$  stets auch  ${}F(x)\leq _{2}F(x')$  gilt.

3. Man nennt

   ${}M/\sim :={\left\{[x]\mid x\in M\right\}}\,$

   die Quotientenmenge von ${}\sim$.

4. Ein Graph auf ${}V$ heißt ${}r$-regulär, wenn jeder Punkt den Grad ${}r$ besitzt.
5. Das kartesische Produkt besitzt die Knotenmenge ${}V\times W$, und zwischen zwei Knoten ${}(v_{1},w_{1})$ und ${}(v_{2},w_{2})$ liegt genau dann eine Kante, wenn entweder  ${}v_{1}=v_{2}$  und  ${}\{w_{1},w_{2}\}\in F$  oder  ${}w_{1}=w_{2}$  und  ${}\{v_{1},v_{2}\}\in E$  gilt.
6. Eine Paarung  ${}P\subseteq E$  in ${}G$ heißt optimal, wenn sie unter allen Paarungen von ${}G$ die größtmögliche Anzahl von Kanten enthält.

Zur gelösten Aufgabe