Diskrete Mathematik - Cheatsheet.pdf

Arten von Graphen: gerichtete und ungerichtete Graphen

Definition:

Graphen können entweder gerichtet oder ungerichtet sein, je nachdem, ob die Kanten eine Richtung haben.

Details:

• Ungerechter Graph: Kanten haben keine Richtung. Eine Kante \( \{u,v\} \) bedeutet einfach eine Verbindung zwischen \( u \) und \( v \).
• Gerichteter Graph (Digraph): Kanten haben eine Richtung. Eine Kante \( (u,v) \) zeigt eine Verbindung von \( u \) nach \( v \).
• Anwendungen: Soziale Netzwerke (ungerichtet), Verkehrsnetzwerke (gerichtet)
• Matrizenrepräsentation: Adjacenzmatrix für ungerichtete (symmetrisch) und gerichtete (asymmetrisch) Graphen.

Inklusions-Exklusions-Prinzip

Definition:

Technik, um die Größe der Vereinigung mehrerer Mengen zu berechnen, unter Verwendung der Größen der einzelnen Mengen und ihrer Durchschnitte.

Details:

• Grundformel: \[|A_1 \bigcup A_2 \bigcup \ldots \bigcup A_n| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \bigcap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \bigcap A_j \bigcap A_k| - ... + (-1)^{n+1} |A_1 \bigcap A_2 \bigcap \ldots \bigcap A_n| \]
• Berechnung von Schnittmengen erforderlich
• Anwendung auf probleme wie Zählprobleme, Wahrscheinlichkeiten

Normalformen: Konjunktive und disjunktive Normalform

Definition:

Konjunktive Normalform (KNF) und disjunktive Normalform (DNF) sind Arten, boolesche Ausdrücke standardisiert darzustellen.

Details:

• KNF: Logischer Ausdruck in Form einer Konjunktion von Disjunktionen.
• DNF: Logischer Ausdruck in Form einer Disjunktion von Konjunktionen.
• Jede boolesche Funktion kann in KNF und DNF umgewandelt werden.
• Formel für KNF: \(C_1 \land C_2 \land \ldots \land C_n\), wobei \(C_i\) Disjunktionen von Literalen sind.
• Formel für DNF: \(D_1 \lor D_2 \lor \ldots \lor D_m\), wobei \(D_i\) Konjunktionen von Literalen sind.

Mächtigkeit von Mengen: Endliche und unendliche Mengen

Definition:

Bezug der Anzahl der Elemente einer Menge, unterscheidet zwischen endlich und unendlich.

Details:

• Eine Menge ist endlich, wenn ihre Elemente gezählt werden können: \( |A| = n \text{mit}\ \ n \in\ \mathbb{N} \).
• Unendlich, wenn keine solche Zahl existiert.
• Beispiel endliche Menge: \( A = \{1, 2, 3\} \).
• Beispiel unendliche Menge: \( \mathbb{N} = \{1, 2, 3, \dots \} \).

Rekursive Algorithmen und Rekursion

Definition:

Verwendung einer Funktion, die sich selbst aufruft, um Probleme kleinerer Größe zu lösen.

Details:

• Basisfall (Triviales Problem, direkte Lösung)
• Rekursionsfall (Problem in kleinere Teilprobleme zerlegen)
• Mathematische Darstellung: Rekurrenzrelationen
• Typische Beispiele: Fibonacci-Folge, Fakultät
• Komplexität analysieren: Rekursionsbaum oder Master-Theorem

Graphenpfade und Kreise

Definition:

Pfad: Sequenz von Knoten, in der jeder Knoten genau einmal besucht wird.Kreis: Geschlossener Pfad, bei dem Start- und Endknoten identisch sind.

Details:

• Pfadlänge: Anzahl der Kanten im Pfad.
• Ein einfacher Pfad hat keine wiederholten Knoten, außer bei einem Kreis, wo Start- und Endknoten gleich sind.
• Ein Kreis mit minimaler Länge, der einen gegebenen Knoten enthält, heißt elementarer Kreis.
• Kreisfreiheit: Ein Graph ist kreisfrei, wenn er keine Kreise enthält (d.h. ein Wald/Baum).

Beweistechniken und logische Schlüsse

Definition:

Techniken und Methoden zur Validierung mathematischer Aussagen und zur Durchführung logischer Schlüsse.

Details:

• Direkter Beweis: Zeigt unmittelbar, dass eine Aussage wahr ist, indem man schlüssig von Hypothesen auf die Behauptung schließt.
• Widerspruchsbeweis: Annahme der Verneinung der zu beweisenden Aussage und Herleitung eines Widerspruchs.
• Induktionsbeweis: Beweis der Basis (oft für n=0) und des Induktionsschrittes (von n auf n+1).
• Kontraposition: Beweis der zur Originalaussage kontrapositiven Aussage.
• Existenz- und Einzigkeitsbeweis: Nachweis, dass mindestens ein Element existiert und dass höchstens ein Element existiert, das die gewünschte Eigenschaft erfüllt.
• Logische Schlüsse: Anwendungen der logischen Regeln. Beispiel: Modus ponens, Modus tollens, Kettenschluss.

Permutation und Kombination

Definition:

Untersuchen von Anordnung und Auswahl ohne und mit Wiederholung in endlichen Mengen.

Details:

• Permutation: Anordnung von Elementen.
• Anzahl der Permutationen einer Menge: \(n!\)
• Permutation mit Wiederholung: \(\frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_r!}\)
• Kombination: Auswahl von Elementen.
• Unterscheidung: Kombination mit/ohne Wiederholung.
• Kombination ohne Wiederholung: \(\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}\)
• Kombination mit Wiederholung: \(\binom{n+k-1}{k} = \frac{(n+k-1)!}{k! \cdot (n-1)!}\)