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

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

   $\sigma :M⟶M.$

2. Die Abbildung

   $F:M_1⟶M_2,$

   heißt ordnungstreu, wenn für alle  $x,x^{\prime }\in M_1$  mit  $x{\le }_1{x}^{\prime }$  stets auch  $F(x){\le }_{2}F(x^{\prime })$  gilt.

3. Man nennt

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

   die Quotientenmenge von $\sim$.

4. Die beiden Relationen heißen isomorph, wenn es bijektive Abbildungen $\phi :M_1\to M_2$ und $\psi :N_1\to N_2$ derart gibt, dass  $(x,y)\in R_1$  genau dann gilt, wenn  $(\phi (x),\psi (y))\in R_2$  gilt.
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