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

1. Ein Monoid ist eine Menge ${}M$ zusammen mit einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M$

   und einem ausgezeichneten Element ${}e\in M$ derart, dass folgende beiden Bedingungen erfüllt sind.

   1. Die Verknüpfung ist assoziativ, d.h. es gilt

      ${}(x\circ y)\circ z=x\circ (y\circ z)\,$

      für alle ${}x,y,z\in M$.

   2. ${}e$ ist neutrales Element der Verknüpfung, d.h. es gilt

      ${}x\circ e=x=e\circ x\,$

      für alle ${}x\in M$.

2. Eine natürliche Zahl ${}g$ heißt größter gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}g$ ein gemeinsamer Teiler der ${}a_{i}$ ist und wenn jeder gemeinsame Teiler ${}t$ der ${}a_{i}$ dieses ${}g$ teilt
3. Die Äquivalenzrelation ${}\sim _{H}$ ist auf ${}G$ durch ${}x\sim _{H}y$, falls ${}x-y\in H$, definiert.
4. Ein Graphisomorphismus ist ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$, wenn es einen Graphhomomorphismus

   $\psi \colon H\longrightarrow G$

   derart gibt, dass

   ${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

   und

   ${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

   gilt.

5. Der vollständige bipartite Graph ${}K_{m,n}$ ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer ${}m$-elementigen Menge ${}A$ und einer ${}n$-elementigen Menge ${}B$ besteht und dessen Kantenmenge durch

   ${}E={\left\{\{a,b\}\mid a\in A,\,b\in B\right\}}\,$

   gegeben ist.

6. Die Paarungsbedingung ist erfüllt, wenn für jede Teilmenge ${}S\subseteq A$ die Beziehung ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$ gilt.

Zur gelösten Aufgabe