Zum Inhalt springen

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


  1. Ein Monoid ist eine Menge M zusammen mit einer Verknüpfung
    ∘:M×M⟶M

    und einem ausgezeichneten Element  e∈M  derart, dass die beiden folgenden Bedingungen erfüllt sind.

    1. Die Verknüpfung ist assoziativ, d.h. es gilt
      (x∘y)∘z=x∘(y∘z)

      für alle  x,y,z∈M. 

    2. e ist neutrales Element der Verknüpfung, d.h. es gilt
      x∘e=x=e∘x

      für alle  x∈M. 

  2. Eine natürliche Zahl g heißt größter gemeinsamer Teiler der a1,…,ak, wenn g ein gemeinsamer Teiler der ai ist und wenn jeder gemeinsame Teiler t der ai dieses g teilt.
  3. Die Äquivalenzrelation ∼H ist auf G durch x∼Hy, falls x−y∈H, definiert.
  4. Ein Graphisomorphismus ist ein Graphhomomorphismus φ:G→H, für den es einen Graphhomomorphismus
    ψ:H⟶G

    derart gibt, dass

    ψ∘φ=IdV

    und

    φ∘ψ=IdW

    gilt.

  5. Der vollständige bipartite Graph Km,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={{a,b}∣a∈A,b∈B}

    gegeben ist.

  6. Die Paarungsbedingung ist erfüllt, wenn für jede Teilmenge  S⊆A  die Beziehung  #(S)≤#(N(S))  gilt.