Kurs:Diskrete Mathematik (Osnabrück 2020)/Definitionsabfrage
Zu einer natürlichen Zahl nennt man die Zahl
die Fakultät von (sprich Fakultät).
Eine Permutation auf einer Menge ist eine bijektive Abbildung
Zu einer Menge nennt man die Menge aller Teilmengen von die Potenzmenge von . Sie wird mit
bezeichnet.
Es seien und natürliche Zahlen mit . Dann nennt man
den Binomialkoeffizienten „ über “.
Eine Verknüpfung auf einer Menge ist eine Abbildung
Eine Verknüpfung
auf einer Menge heißt kommutativ, wenn für alle die Gleichheit
gilt.
Eine Verknüpfung
auf einer Menge heißt assoziativ, wenn für alle die Gleichheit
gilt.
Es sei eine Menge mit einer Verknüpfung
gegeben. Dann heißt ein Element neutrales Element der Verknüpfung, wenn für alle die Gleichheit gilt.
Es sei eine Menge mit einer Verknüpfung
und einem neutralen Element gegeben. Dann heißt zu einem Element ein Element inverses Element (zu ). wenn die Gleichheit
gilt.
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 .
Ein kommutativer Halbring ist eine Menge mit Verknüpfungen und (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen und derart, dass folgende Bedingungen erfüllt sind:
- Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
- Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
- Es gilt das Distributivgesetz, also
für alle
.
Eine Menge mit einem ausgezeichneten Element und mit einer Verknüpfung
heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.
- Die Verknüpfung ist assoziativ, d.h. für alle
gilt
- Das Element ist ein neutrales Element, d.h. für alle
gilt
- Zu jedem
gibt es ein inverses Element, d.h. es gibt ein
mit
Eine Gruppe heißt kommutativ (oder abelsch), wenn die Verknüpfung kommutativ ist, wenn also für alle gilt.
Es sei eine Gruppe. Eine Teilmenge heißt Untergruppe von wenn folgendes gilt.
- .
- Mit ist auch .
- Mit ist auch .
Eine Menge heißt ein Ring, wenn es zwei Verknüpfungen (genannt Addition und Multiplikation)
und (nicht notwendigerweise verschiedene) Elemente gibt, die die folgenden Eigenschaften erfüllen.
- Axiome der Addition
- Assoziativgesetz: Für alle gilt .
- Kommutativgesetz: Für alle gilt .
- ist das neutrale Element der Addition, d.h. für alle ist .
- Existenz des Negativen: Zu jedem gibt es ein Element mit .
- Axiome der Multiplikation
- Assoziativgesetz: Für alle gilt .
- ist das neutrale Element der Multiplikation, d.h. für alle ist .
- Distributivgesetz: Für alle gilt und .
Ein Ring heißt kommutativ, wenn die Multiplikation kommutativ ist.
Ein kommutativer Ring heißt Körper, wenn ist und wenn jedes von verschiedene Element ein multiplikatives Inverses besitzt.
Es seien und Mengen. Eine Relation zwischen den Mengen und ist eine Teilmenge der Produktmenge , also .
Es seien und Mengen und es sei
eine Abbildung. Dann nennt man
den Graphen der Abbildung .
Eine Relation heißt linkseindeutig, wenn es zu jedem maximal ein mit gibt.
Eine Relation heißt rechtseindeutig, wenn es zu jedem maximal ein mit gibt.
Eine Relation heißt linksvollständig, wenn es zu jedem ein mit gibt.
Eine Relation heißt rechtsvollständig, wenn es zu jedem ein mit gibt.
Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .
Eine Relation auf einer Menge heißt reflexiv, wenn für alle gilt.
Eine Relation auf einer Menge heißt transitiv, wenn aus und stets folgt.
Eine Relation auf einer Menge heißt symmetrisch, wenn aus stets folgt.
Eine Relation auf einer Menge heißt antisymmetrisch, wenn aus und stets folgt.
Es seien und Mengen mit darauf erklärten Relationen bzw. . Man nennt eine Abbildung
relationstreu (oder relationserhaltend), wenn für alle mit auch gilt.
Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.
- Es ist für alle .
- Aus und folgt stets .
- Aus und folgt .
Eine Ordnungsrelation auf einer Menge heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen die Beziehung oder gilt.
Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung auf gibt, die die beiden Eigenschaften
- Aus folgt für beliebige ,
- Aus und folgt für beliebige ,
erfüllt.
Man sagt, dass die natürliche Zahl die natürliche Zahl teilt (oder dass von geteilt wird, oder dass ein Vielfaches von ist), wenn es eine natürliche Zahl derart gibt, dass ist. Man schreibt dafür auch .
Es sei , , eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge durch
falls
für alle gilt, die Produktordnung.
Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung
heißt ordnungstreu (oder monoton), wenn für alle mit stets auch gilt.
Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung
heißt ordnungsvolltreu, wenn für alle genau dann gilt, wenn gilt.
Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung
heißt monoton fallend, wenn für alle mit stets gilt.
Es sei eine geordnete Menge. Ein Element heißt größtes Element von , wenn für jedes gilt.
Es sei eine geordnete Menge. Ein Element heißt kleinstes Element von , wenn für jedes gilt.
Es sei eine geordnete Menge. Ein Element heißt maximal (in ) oder ein maximales Element (von ), wenn es kein Element , , mit gibt.
Es sei eine geordnete Menge. Ein Element heißt minimal (in ) oder ein minimales Element (von ), wenn es kein Element , , mit gibt.
Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt obere Schranke für , wenn für jedes gilt.
Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt untere Schranke für , wenn für jedes gilt.
Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Supremum von , wenn die kleinste obere Schranke von ist.
Es sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Infimum von , wenn die größte untere Schranke von ist.
Es seien natürliche Zahlen. Dann heißt eine natürliche Zahl gemeinsamer Teiler der , wenn jedes teilt für .
Es seien natürliche Zahlen. Dann heißt eine natürliche Zahl der größte gemeinsame Teiler der , wenn ein gemeinsamer Teiler der ist und wenn jeder gemeinsame Teiler der dieses teilt.
Zu einer Menge von natürlichen Zahlen
heißt eine natürliche Zahl ein gemeinsames Vielfaches, wenn ein Vielfaches von jedem ist, also von jedem geteilt wird.
Zu einer Menge von natürlichen Zahlen
heißt eine natürliche Zahl das kleinste gemeinsame Vielfache dieser Zahlen, wenn ein gemeinsames Vielfaches der ist und wenn jedes gemeinsame Vielfache der Zahlen ein Vielfaches von ist.
Es seien zwei ganze Zahlen (mit ) gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest
rekursiv bestimmte Folge die Folge der euklidischen Reste.
Eine geordnete Menge mit der Eigenschaft, dass für je zwei Elemente ein Infimum und ein Supremum existiert, heißt Verband.
Eine Menge mit zwei kommutativen und assoziativen Verknüpfungen und heißt algebraischer Verband, wenn die Absorptionsgesetze
und
gelten.
In einem algebraischen Verband nennt man die durch
falls
definierte Ordnung, die zugehörige Ordnung.
Ein Verband heißt beschränkt, wenn es in ihm ein kleinstes Element und ein größtes Element gibt.
Ein beschränkter Verband heißt komplementär, wenn es zu jedem ein mit und gibt.
Ein Verband heißt distributiv, wenn in ihm die Distributivgesetze
und
gelten.
Ein Verband heißt boolesch, wenn er komplementär und distributiv ist.
Es sei eine geordnete Menge mit einem kleinsten Element . Ein Element heißt Atom, wenn ist und die Beziehung nur für und gilt.
Eine Äquivalenzrelation auf einer Menge ist eine Relation , die die folgenden drei Eigenschaften besitzt (für beliebige ).
- Es ist (reflexiv).
- Aus folgt (symmetrisch).
- Aus und folgt (transitiv).
Dabei bedeutet , dass das Paar zu gehört.
Es sei eine Äquivalenzrelation und . Dann ist
die Äquivalenzklasse von bezüglich .
Es sei eine Äquivalenzrelation auf einer Menge . Eine Teilmenge heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in aus dieser Klasse gibt.
Es sei eine Äquivalenzrelation. Dann heißt
die Quotientenmenge von .
Es sei eine Äquivalenzrelation und die Quotientenmenge. Die Abbildung
heißt kanonische Projektion von .
Es seien und Gruppen. Eine Abbildung
heißt Gruppenhomomorphismus, wenn die Gleichheit
für alle gilt.
Es seien und Ringe. Eine Abbildung
heißt Ringhomomorphismus, wenn folgende Eigenschaften gelten:
- .
- .
- .
Es sei eine kommutative Gruppe und eine Untergruppe. Für Elemente setzen wir (und sagen, dass und äquivalent sind), wenn .
Es sei eine kommutative Gruppe und eine Untergruppe. Die Quotientenmenge
mit der aufgrund von Satz 12.5 eindeutig bestimmten Gruppenstruktur heißt Restklassengruppe von modulo . Die Elemente heißen Restklassen. Für eine Restklasse heißt jedes Element mit ein Repräsentant von .
Eine Teilmenge eines kommutativen Ringes heißt Ideal, wenn die folgenden Bedingungen erfüllt sind:
- .
- Für alle ist auch .
- Für alle und ist auch .
Es sei eine natürliche Zahl und natürliche Zahlen mit . Dann nennt man
den Multinomialkoeffizienten über .
Es sei eine Menge. Eine Teilmenge heißt Partition von , falls die folgenden Bedingungen erfüllt sind.
- Für alle gilt .
- Für , , gilt .
- Die Elemente von bilden eine Überdeckung von , d.h. jedes Element von liegt in mindestens einem Element von .
Die Anzahl der Partitionen einer -elementigen Menge in Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit bezeichnet.
Die Anzahl der Partitionen einer -elementigen Menge heißt Bellzahl und wird mit bezeichnet.
Ein ungerichteter Graph auf einer Menge (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von .
Zu einem Punkt in einem Graphen nennt man
die Nachbarschaft von .
Ein Graph auf einer Menge heißt vollständig, wenn je zwei Punkte miteinander durch eine Kante verbunden sind.
Ein Graph heißt kantenfrei, wenn die Kantenmenge leer ist.
Ein Graph heißt linear, wenn es eine Auflistung aller Knoten derart gibt, dass die Kantenmenge gleich , , ist.
Ein Graph heißt Sterngraph, wenn es in ihm einen Knoten (das Zentrum) gibt, der mit allen anderen Knoten verbunden ist und dies die einzigen Kanten des Graphen sind.
Zu einem Punkt in einem Graphen nennt man die Anzahl der Kanten, die an anliegen, den Grad von . Er wird mit bezeichnet.
Ein Punkt eines Graphen mit Grad heißt isoliert.
Ein Punkt eines Graphen mit Grad heißt Blatt.
Zu einem Graphen nennt man
den Minimalgrad des Graphen.
Zu einem Graphen nennt man
den Maximalgrad des Graphen.
Ein Graph auf einer Menge heißt -regulär, wenn jeder Punkt den Grad besitzt.
Ein Graph heißt Untergraph eines Graphen , wenn , und die Kanten aus nur Bezug auf Punkte aus nehmen.
Ein Untergraph heißt voll, wenn jede Kante aus , die Punkte aus verbindet, auch eine Kante in ist.
Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus stets folgt, heißt Graphhomomorphismus.
Es seien und Graphen. Ein Graphhomomorphismus heißt Isomorphismus, wenn es einen Graphhomomorphismus
derart gibt, dass
und
gilt.
Zwei Graphen und heißen isomorph, wenn es einen Graphisomorphismus gibt.
Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus entweder oder aber folgt, heißt schwacher Graphhomomorphismus.
Es sei ein Graph. Ein Isomorphismus heißt Automorphismus.
Zu einem Graphen nennt man die Gruppe aller Automorphismen
die Automorphismengruppe von . Sie wird mit bezeichnet.
Ein Graph heißt homogen, wenn es zu je zwei Knotenpunkten einen Automorphismus
mit
gibt.
Ein Graph heißt starr, wenn die Automorphismengruppe von trivial ist.
Zu einem Graphen nennt man den Graphen den komplementären Graphen (oder Komplementärgraph). Er wird mit bezeichnet.
Zu einem Graphen und einer Teilmenge der Kantenmenge versteht man unter denjenigen Graphen, dessen Punktemenge ist und dessen Kantenmenge aus besteht.
Es sei ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge von ist und bei dem zwei Knoten und (also Kanten aus ) genau dann durch eine Kante verbunden werden, wenn und einen gemeinsamen Punkt in besitzen, den Kantengraphen zu .
Es sei ein Graph, eine Menge und eine Abbildung. Unter dem Bildgraphen zu versteht man denjenigen Graphen, dessen Knotenmenge durch das Bild von und dessen Kantenmenge durch
gegeben ist.
Es sei ein Graph und sei eine Äquivalenzrelation auf . Dann nennt man die Quotientenmenge , versehen mit der Bildgraphstruktur zur kanonischen Abbildung
den Quotientengraphen zu . Er wird mit bezeichnet.
Es sei ein Graph und eine Kante, die die Knotenpunkte und verbindet. Man nennt denjenigen Graphen mit der Knotenmenge , bei der und miteinander identifiziert werden, und bei dem die Kantenmenge aus den Bildkanten zur Kontraktionsabbildung besteht, den Kontraktionsgraphen zu . Er wird mit bezeichnet.
Zu zwei Graphen und mit disjunkten Knotenmengen und nennt man den Graphen mit der Knotenmenge und der Kantenmenge die disjunkte Vereinigung der Graphen.
Zu zwei Graphen und nennt man den Graphen mit Knotenmenge , wobei zwischen zwei Knoten und genau dann eine Kante besteht, wenn entweder und oder und gilt, das kartesische Produkt der Graphen.
Ein Weg in einem Graphen ist eine Folge von Knoten derart, dass für alle eine Kante ist.
Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten einen Weg gibt, der und verbindet.
Zu einem Punkt in einem Graphen nennt man
die Zusammenhangskomponente von .
Unter der Länge eines Weges in einem Graphen versteht man die Anzahl seiner Kanten.
Zu zwei Knotenpunkten und in einem zusammenhängenden Graphen versteht man unter dem Abstand die minimale Länge eines verbindenden Weges von nach .
Unter dem Durchmesser eines zusammenhängenden Graphen versteht man das Maximum über alle Abstände zu .
Unter dem Radius eines zusammenhängenden Graphen versteht man den Ausdruck
Zu einem Knotenpunkt eines zusammenhängenden Graphen nennt man
die Exzentrizität von .
Ein Weg in einem Graphen heißt Zyklus, wenn ist.
Ein Kreis in einem Graphen ist ein Zyklus der Länge ohne Wiederholungen.
Ein Graph heißt Rundgang, wenn es in ihm einen Kreis gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.
Die Taille eines zyklischen Graphen ist die kürzeste Länge eines Kreises in .
Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .
Ein Graph ohne Kreis heißt Wald
Ein zusammenhängender Wald heißt Baum.
Ein Untergraph eines Graphen heißt aufspannender Baum von , wenn ein Baum mit der vollen Knotenmenge ist.
Zu einer endlichen Menge heißt eine Teilmenge
ein Matroid, wenn folgende Bedingungen erfüllt sind.
- Es ist .
- Aus und folgt .
- Wenn
mit
so gibt es ein derart, dass .
In einem Matroid auf einer Menge nennt man die maximalen Mengen aus Basen.
In einem Matroid auf einer Menge nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von den Rang des Matroids.
Ein Untergraph eines Graphen heißt aufspannender Wald von , wenn ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von übereinstimmen.
Ein Multigraph besteht aus einer Knotenmenge , einer Kantenmenge und einer Abbildung
Zu einem Graphen versteht man unter der Adjazenzmatrix diejenige - Matrix, deren Einträge durch
gegeben sind.
Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von .
Es sei ein Graph. Unter der Inzidenzmatrix zu verstehen wir die - Matrix, deren Einträge durch
gegeben sind.
Es sei ein Graph. Unter der Gradmatrix zu verstehen wir die - Diagonalmatrix, deren Diagonaleintrag an der Stelle durch den Grad im Knotenpunkt gegeben ist.
Zu einem Multigraphen versteht man unter der Laplace-Matrix die Differenz
aus Gradmatrix und Adjazenzmatrix .
Ein Graph heißt bipartit, wenn es eine disjunkte Zerlegung
derart gibt, dass es nur Kanten zwischen und gibt.
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.
Eine Paarung in einem Graphen ist eine Kantenmenge , wobei die Kanten aus zueinander disjunkt sind.
Wir sagen, dass eine Paarung in einem Graphen einen Knotenpunkt abdeckt, wenn es eine Kante aus gibt, zu der gehört.
Eine Paarung in einem Graphen heißt Paarung für eine Teilmenge , wenn jeder Knoten aus von einer Kante aus abgedeckt wird.
Eine Paarung in einem Graphen heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.
Eine Paarung in einem Graphen heißt maximal, wenn jedes mit keine Paarung ist.
Eine Paarung in einem Graphen heißt optimal, wenn sie unter allen Paarungen von die größtmögliche Anzahl von Kanten enthält.
Die Paarungszahl eines bipartiten Graphen ist die größtmögliche Anzahl von Kanten in einer Paarung von .
Es sei ein bipartiter Graph mit einer Bipartition und sei . Man sagt, dass die Paarungsbedingung erfüllt, wenn für jede Teilmenge die Beziehung gilt.
Es sei ein Graph und eine Paarung. Man nennt einen Weg in alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus und aus besitzt.
Es sei ein Graph. Eine Teilmenge heißt Knotenüberdeckung von , wenn jede Kante mindestens einen Knoten aus trifft.
Es sei ein Graph. Eine Knotenüberdeckung von heißt minimal, wenn zu jedem keine Knotenüberdeckung ist.
Es sei ein Graph. Eine Knotenüberdeckung von heißt optimal, wenn es keine Knotenüberdeckung von mit weniger als Elementen gibt.
Es sei ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von heißt Knotenüberdeckungszahl von .
Ein Kreis in einem Graphen heißt Hamiltonkreis, wenn in ihm jeder Knotenpunkt vorkommt.
Ein Graph heißt hamiltonsch, wenn es in ihm einen Hamiltonkreis gibt.
Es sei ein Graph. Ein Kantenzug heißt eulersch, wenn in ihm jede Kante aus genau einmal vorkommt.
Ein Graph heißt eulersch, wenn in ihm ein geschlossener Eulerzug existiert.
Zwei Untergraphen und in einem Graphen heißen kantendisjunkt, wenn ist.
Es sei ein Graph. Eine Abbildung
in eine Menge heißt Färbung des Graphen.
Es sei ein Graph. Eine Färbung
heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.
Zu einem Graphen nennt man die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt, die chromatische Zahl des Graphen. Sie wird mit bezeichnet.
Zu einem Graphen versteht man unter dem chromatischen Polynom die Funktion, die durch
gegeben ist.
Es sei ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von im besteht aus folgenden Daten.
- Eine
injektive
Abbildung
zu jedem Knotenpunkt gibt es also einen Punkt und verschiedene Knotenpunkte besitzen verschiedene Realisierungen .
- Zu jeder Kante
eine injektive
stetige
Abbildung
mit und .
- Für verschiedene Kanten
ist
Ein Graph heißt planar, wenn er eine geometrische Realisierung im besitzt.