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

1. Die Relation  ${}R\subseteq M\times N$  heißt linkseindeutig, wenn es zu jedem  ${}y\in N$  maximal ein  ${}x\in M$  mit  ${}(x,y)\in R$  gibt.
2. Ein Verband ${}M$ heißt boolesch, wenn er komplementär und distributiv ist.
3. Eine Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$ ist eine Relation, die die folgenden drei Eigenschaften besitzt (für beliebige ${}x,y,z\in M$).
   1. ${}x\sim x$.
   2. Aus ${}x\sim y$ folgt ${}y\sim x$.
   3. Aus ${}x\sim y$ und ${}y\sim z$ folgt ${}x\sim z$.
4. Ein aufspannender Wald ist ein Untergraph  ${}W\subseteq G$,  der ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von ${}V$ übereinstimmen.
5. Ein Graph heißt bipartit, wenn es eine disjunkte Zerlegung

   ${}V=A\uplus B\,$

   derart gibt, dass es nur Kanten zwischen ${}A$ und ${}B$ gibt.

6. Eine Paarung für ${}S$ liegt vor, wenn jeder Knoten aus ${}S$ von einer Kante aus ${}P$ abgedeckt wird.

Zur gelösten Aufgabe