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


  1. Ein Monoid ist eine Menge zusammen mit einer Verknüpfung

    und einem ausgezeichneten Element derart, dass folgende beiden Bedingungen erfüllt sind.

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

      für alle .

    2. ist neutrales Element der Verknüpfung, d.h. es gilt

      für alle .

  2. Eine natürliche Zahl heißt größter gemeinsamer Teiler der , wenn ein gemeinsamer Teiler der ist und wenn jeder gemeinsame Teiler der dieses teilt
  3. Die Äquivalenzrelation ist auf durch , falls , definiert.
  4. Ein Graphisomorphismus ist ein Graphhomomorphismus , wenn es einen Graphhomomorphismus

    derart gibt, dass

    und

    gilt.

  5. Der vollständige bipartite Graph ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer -elementigen Menge und einer -elementigen Menge besteht und dessen Kantenmenge durch

    gegeben ist.

  6. Die Paarungsbedingung ist erfüllt, wenn für jede Teilmenge die Beziehung gilt.