Diskrete Mathematik/Gemischte Definitionsabfrage/2/Aufgabe/Lösung
- Ein Monoid ist eine Menge zusammen mit einer
Verknüpfung
und einem ausgezeichneten Element derart, dass folgende beiden Bedingungen erfüllt sind.
- Die Verknüpfung ist assoziativ, d.h. es gilt
für alle .
- ist neutrales Element der Verknüpfung, d.h. es gilt
für alle .
- 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
- Die Äquivalenzrelation ist auf durch , falls , definiert.
- Ein Graphisomorphismus ist ein Graphhomomorphismus
,
wenn es einen Graphhomomorphismus
derart gibt, dass
und
gilt.
- 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.
- Die Paarungsbedingung ist erfüllt, wenn für jede Teilmenge die Beziehung gilt.