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

< Diskrete Mathematik/Gemischte Definitionsabfrage/6/Aufgabe

Eine Permutation ${}\sigma$ auf ${}M$ ist eine bijektive Abbildung
$\sigma \colon M\longrightarrow M.$
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.
Man nennt
${}M/\sim :={\left\{[x]\mid x\in M\right\}}\,$

die Quotientenmenge von ${}\sim$ .
Ein Graph auf ${}V$ heißt ${}r$ -regulär, wenn jeder Punkt den Grad ${}r$ besitzt.
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.
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