transitive Hülle: R^+ = \bigcup_{k \in \N}R^kR+=⋃k∈NRk
(alle Pfade, die mindestens einen Schritt machen)
reflexiv-transitive Hülle: R^* = R^0 \cup R^kR∗=R0∪Rk
(alle Pfade, die mindestens einen Schritt machen, und auch Pfade der Länge 0 /
Selbstschleifen)
Eigenschaften von binären Relationen
eine binäre Relation R
\subseteq A \times AR⊆A×A ist...
...reflexiv, falls Id_A \subseteq RA⊆R
(jeder Knoten hat eine Schleife)
...symmetrisch, falls für jedes (s,t) \in R(s,t)∈R
auch (t,s) \in R(t,s)∈R
gilt (zwischen je zwei Knoten gibt es entweder keine oder beide Kanten)
...asymmetrisch, falls für jedes (s,t) \in R(s,t)∈R
immer (t,s) \notin R(t,s)∈/R
gilt (keine Schleifen + zwischen je zwei verschiedenen Knoten gibt es
höchstens eine Kante)
...antisymmetrisch, falls für jedes (s,t) \in R(s,t)∈R und
(t,s) \in R(t,s)∈R
auch s = ts=t gilt
(Schleifen erlaubt + zwischen je zwei verschiedenen Knoten gibt es
höchstens eine Kante)
...transitiv, falls für jedes (s,t) \in R(s,t)∈R und
(t,u) \in R(t,u)∈R
auch (s,u) \in R(s,u)∈R
gilt (kommt man mit genau zwei Schritten von ss nach
uu, dann
auch mit genau einem)
totale Ordnungen: partielle Ordnung + für alle a,b \in Ra,b∈R
gilt entweder aRbaRb oder bRabRa
m \in Am∈A ist ein
maximales Element bzgl. RR,
wenn es keine Kanten zu einem anderen Element gibt
analog: minimal
Darstellung: Hasse-Diagramme
m \in Am∈A ist das
größte Element bzgl. RR,
wenn es keine Kanten zu einem anderen Element gibt und von jedem
anderen Knoten eine Kante zu mm
existiert (z.B. 1 in |^{-1}_\N∣N−1)
G - zusammenhängend, wenn u(E \cup E^{-1})^*v \; \forall u,v \in Vu(E∪E−1)∗v∀u,v∈V
es existiert einen Weg zwischen jedem uu und
vv,
wenn GGungerichtet wäre
U \subseteq VU⊆V
ist eine Zusammenhangskomponente von G, wenn G[U]G[U]
zusammenhängend ist
(*) hinreichende Bedingung: wenn die Summe aus minimalem und
maximalem Knotengrad größer oder gleich n-1n−1 ist, ist der
Graph zusammenhängend
generell, ohne Beweis: prüfe anhand des maximalen Grades, ob der
Knoten mit minimalem Grad irgendwie durch einen Pfad mit dem Knoten mit
maximalem Grad verbunden ist
G - stark zusammenhängend, wenn uE^*v \; \forall u,v \in VuE∗v∀u,v∈V
es existiert einen Weg zwischen jedem uu und
vv
im gerichteten Graph GG
U \subseteq VU⊆V
ist eine starke Zusammenhangskomponente von G, wenn G[U]G[U] stark
zusammenhängend ist
isolierte Knoten sind starke Zusammenhangskomponenten
(!) jeder stark zusammenhängende Graph GG
mit nn
Knoten hat mindestens nn
Kanten
Kreise
Pfad mit l \geq 1l≥1, der in Knoten uu beginnt und
in uu endet
einfache Kreise: kein Knoten taucht mehrmals auf
m.a.W der Kreis enthält keinen kleineren Kreis
ein Graph ohne Kreise heist azyklisch (kreisfrei)
Vorgänger und Nachfolger
Nachfolger von uu: uE = \left\{v \in V |
uEv\right\}uE={v∈V∣uEv}
Vorgänger von vv:
Ev = \left\{u \in V |
uEv\right\}Ev={u∈V∣uEv}
für jeden einfachen zshgd. Graphen gilt: |E| \geq |V| -
1∣E∣≥∣V∣−1 bzw. |V| \leq |E| +
1∣V∣≤∣E∣+1
"jeder zshgd. Graph hat mindestens|V| - 1∣V∣−1Kanten"
"jeder zshgd. Graph hat höchstens|E| + 1∣E∣+1Knoten"
jeder einfache Graph mit |E| \geq |V|∣E∣≥∣V∣ und |V| \geq 3∣V∣≥3 enthält einen
Kreis
GG
kreisfrei, wenn |V| \geq |E| + 1∣V∣≥∣E∣+1
wenn GGkreisfrei ist, dann ist GGbipartit, falls |E| \geq
1∣E∣≥1
Handschlaglemma: 2|E| = \sum_{i \in [n]}deg(v_i)2∣E∣=∑i∈[n]deg(vi) (Anzahl der
Kanten eines Graphen ist gleich mit der Hälfte der Summe aller Knotengrade)
ein Graph mit |V| >
\frac{1}{2}\sum_{i\in[n]}d_i+1∣V∣>21∑i∈[n]di+1 kann
nicht zusammenhängend sein (da sonst |V| > |E| + 1∣V∣>∣E∣+1 gilt und
der Graph nicht genug Kanten hat)
dies bedeutet jedoch nicht, dass ein Graph mit |V| \leq
\frac{1}{2}\sum_{i\in[n]}d_i+1∣V∣≤21∑i∈[n]di+1 zshgd.
ist
Hamiltonkreis: jeder Knoten wird genau einmal
besucht
(!) Existenz (hinreichend; es gibt auch Hamiltonkreise, wo diese Bedingung
verletzt wird): jeder Knoten in einem einfachen Graph mit |V| \geq 3∣V∣≥3 hat mindestens Grad
\frac{|V|}{2}2∣V∣
Eulertour: jede Kante wird genau einmal besucht
(!) Existenz: jeder Knoten in einem einfachen, zshgd. Graph hat
geraden Grad
Matchings existieren in
bipartiten Graphen G = (A
\dot \cup B, E)G=(A∪˙B,E)
Definition: ein Matching M \subseteq EM⊆E ist
eine Teilmenge der Kanten EE
eines Graphen GG, so dass
keine zwei Kanten aus MM
einen gemeinsamen Knoten haben (\forall e,e' \in M \; : \; |e \cap e'| \neq
1∀e,e′∈M:∣e∩e′∣=1)
Heiratssatz: \exists∃ Matching \leftrightarrow↔|\Gamma(X)| \geq |X|∣Γ(X)∣≥∣X∣ mit \Gamma(X) = \bigcup_{x\in
X}\Gamma(x)Γ(X)=⋃x∈XΓ(x) (XX - beliebige
Knotenmenge in A, \Gamma(X)Γ(X) - Nachbarn von X in B)
jede Knotenteilmenge XX in
A hat mind. |X|∣X∣ Nachbarn in B
Matchings mit Präferenzen
instabiles Matching: f(a) \prec_a f(a') \; \land \; a' \prec_{f(a')}
af(a)≺af(a′)∧a′≺f(a′)a (a
bevorzugt den Partner von a' und der Partner von a' bevorzugt a \to→ a und f(a') würden
ihren aktuellen Partner verlassen)
Bindungsregeln (Reihenfolge stark \to→ schwach):
\neg, \land, \lor,
\to¬,∧,∨,→
\neg p \land q \equiv (\neg
p \land q)¬p∧q≡(¬p∧q)
p \land q \to r \equiv ((p
\land q) \to r)p∧q→r≡((p∧q)→r)
p \land q \lor r \land s
\equiv ((p \land q) \lor (r \land s))p∧q∨r∧s≡((p∧q)∨(r∧s))
Belegung\beta: V' \to \{0, 1\}β:V′→{0,1} mit V' \subseteq VV′⊆V
Abbildung, die jeder Aussagenvariablen V'V′
einen Wahrheitswert 0 bzw. 1 zuordnet
minimal, wenn V' = V_FV′=VF
Bedeutung / Wahrheitswert von F: [F](\beta)[F](β) oder [F][F]:
[F](\beta) =
\begin{dcases}1 & \text{falls } F = true \\ 0 & \text{falls } F = false \\
\beta(p) & \text{falls }F = p \text{ für } p \in V \\ 1 - [G](\beta) &
\text{falls } F = \neg G \\ \max\{[G](\beta), [H](\beta)\} & \text{falls } F = G
\lor H \\ \min\{[G](\beta), [H](\beta)\} & \text{falls } F = G \land H \\
\max\{1 - [G](\beta), [H](\beta)\} & \text{falls } F = G \to
H\end{dcases}[F](β)=⎩⎨⎧10β(p)1−[G](β)max{[G](β),[H](β)}min{[G](β),[H](β)}max{1−[G](β),[H](β)}falls F=truefalls F=falsefalls F=p fu¨r p∈Vfalls F=¬Gfalls F=G∨Hfalls F=G∧Hfalls F=G→H
Erf_GG:
Menge aller minimalen Belegungen \betaβ, die G
erfüllen
Eine Formel ist...
...eine Tautologie / (allgemein)gültig, wenn sie in allen
Welten wahr ist (für jede Belegung \betaβ
gilt [F](\beta) = 1[F](β)=1)
(Test: prüfe in Wahrheitstabelle, ob Spalte für FF nur
1 enthält)
z.B. p \lor \neg pp∨¬p
...ein Widerspruch / unerfüllbar, wenn sie in allen Welten
falsch ist (für jede Belegung \betaβ
gilt [F](\beta) = 0[F](β)=0)
(Test: prüfe in Wahrheitstabelle, ob Spalte für FF nur
0 enthält)
z.B. p \land \neg pp∧¬p
...erfüllbar, wenn es mindestens eine Belegung \betaβ mit
[F](\beta) = 1[F](β)=1 gibt (Test:
prüfe in Wahrheitstabelle, ob Spalte für FF
mindestens ein 1 enthält)
z.B. p \to qp→q
FF gültig
\leftrightarrow↔\neg F¬F
unerfüllbar
FF
unerfüllbar \leftrightarrow↔\neg F¬F
gültig
FF nicht
gültig \leftrightarrow↔\neg F¬F
erfüllbar
FF
erfüllbar \leftrightarrow↔\neg F¬F
nicht gültig
FF nicht
gültig, aber erfüllbar \leftrightarrow↔\neg F¬F nicht
gültig, aber erfüllbar
Wahrheitstabellen
Logische Äquivalenzen
F \equiv GF≡G genau dann, wenn
für jede mögliche Belegung \betaβ für FF und GG die Gleichung [F](\beta) = [G](\beta)[F](β)=[G](β) gilt
wenn F und G äquivalent sind, heißt das, dass F und G zwei unterschiedliche Schreibweise für
die selben Formeln sind / F und G sind semantisch gleich
Test: prüfe in Wahrheitstabelle, ob für F \leftrightarrow
GF↔G die
Spalte für \leftrightarrow↔ nur 1 enthält
erfüllbar, wenn mindestens ein Disjunkt erfüllbar ist
jede Formel ist in DNF übertragbar
Entferne \to→, \leftrightarrow↔ und \oplus⊕ mit
Umformung
Wende deMorgan an
Wende Distributivität an
Kanonische DNF und Kanonische KNF
K. DNF (1-Werte)
K. KNF (0-Werte) (wenn KV-Diagramm, wähle 0-Werte und negiere
sie)
Aufstellen einer KNF-Formel
erfüllbarkeitsäquivalent zu F
stelle Syntaxbaum von FF auf,
notiere Wurzel als TT
für jede Teilformel (nichtterminale Knoten), notiere sie als T_iTi
mit T_i \leftrightarrow T_{i_1} \cdot
T_{i_2}Ti↔Ti1⋅Ti2
(wobei i_1i1
und i_2i2
die Kinder von T_iTi
sind) bzw. T_i \leftrightarrow \neg
T_{i_1}Ti↔¬Ti1
(wenn nur Negation)
die finale Klausel hat die Form T \land (T \leftrightarrow T_{i} \cdot T_{j}) \land
...T∧(T↔Ti⋅Tj)∧...
falls man nn Objekte auf
mm Mengen
verteilt (n, m > 0n,m>0) und nngrößer als mm ist, dann
gibt es mindestens eine Menge, in der mehr als ein Objekt landet
falls man nn Objekte auf
mm Mengen
verteilt (n, m > 0n,m>0) und nnkleiner als mm ist, dann
gibt es mindestens eine Menge, in der kein Objekt landet
Verschärfung: verteilt man nn Elemente
auf kk
Mengen, gibt es mindestens eine Menge, in der sich zumindest \lceil \frac{n}{k}
\rceil⌈kn⌉ Objekte befinden
Beispiele:
in einer Gruppe von 3 Personen haben mindestens 2 das gleiche Geschlecht: 2 = \lceil 3 / 2
\rceil2=⌈3/2⌉
in einer Gruppe von 13 Personen haben mindestens 2 Personen im selben Monat
Geburtstag: 2 = \lceil 13 / 12 \rceil2=⌈13/12⌉
es gibt in Deutschland mindestens 415 Menschen, die exakt die gleiche Anzahl von
Haaren auf dem Kopf haben: 415 = \lceil 83.000.000 / 200.000
\rceil415=⌈83.000.000/200.000⌉, wobei die
Einwohnerzahl Deutschlands 83 Mio. beträgt und die durschnittliche Anzahl der Haare
auf dem Kopf 200.000 ist
Inzidenzmatrix: die Summe der Spalten (\sum_{v \in V}deg(v)∑v∈Vdeg(v)) ist gleich mit der
Summe der Zeilen (2|E|2∣E∣) \to→ Beweis des
Handschlaglemmas (2|E| = \sum_{v \in V}deg(v)2∣E∣=∑v∈Vdeg(v))
"Aufsteigend sortierte kk-Tupel
mit kk
verschiedenen Einträgen aus [n][n]"
eindeutige Menge
Mit Zurücklegen, Ohne Reihenfolge: C_{n,k} := \{(s_1, ..., s_k) \in
[n]^k : s_1 \leq s_2 \leq ... \leq s_k \}Cn,k:={(s1,...,sk)∈[n]k:s1≤s2≤...≤sk}
|C_{n,k}| = {n + k - 1
\choose k}∣Cn,k∣=(kn+k−1)
(!)|C_{n,k}| = |D_{k,n}|∣Cn,k∣=∣Dk,n∣
"Aufsteigend sortierte kk-Tupel
über [n][n] mit
Wiederholungen"
Multimenge
Mit Zurücklegen, Mit Reihenfolge: \{(s_1, ..., s_k) \in [n]^k
\}{(s1,...,sk)∈[n]k}
Anz. Möglichkeiten = n^knk
Tupel mit Duplikate
Beispielsaufgaben: Ziehen aus einer Urne
Wie viele mögliche Lottoziehungen gibt es (nn Bälle, kk Ziehungen)?
\to |B_{n,k}|→∣Bn,k∣ (ohne
Zurücklegen, ohne Reihenfolge)
Ein Wettbewerb vergibt einen ersten, einen zweiten, ... und einen kk-ten Preis.
Wie viele Möglichkeiten gibt es, die Preise unter den nn
Wettbewerbsteilnehmer zu verteilen? \to
|A_{n,k}|→∣An,k∣ (ohne
Zurücklegen, mit Reihenfolge)
Wie viele Möglichkeiten gibt es, kk
Fußballspiele auf nn Austragungsorte zu
verteilen? \to n^k→nk
(mit Zurücklegen, mit Reihenfolge)
Wie viele Möglichkeiten gibt es, kk Euro unter
nn Personen zu
verteilen? \to |C_{n,k}|→∣Cn,k∣ (mit
Zurücklegen, ohne Reihenfolge)
Möglichkeiten, die Buchstaben in ABCDEFGH umzuordnen, so, dass ABC erhalten bleibt
gesamte Anzahl an Buchstaben: 88\to→ Anz. Möglichkeiten,
alle Buchstaben umzuordnen, ohne zu beachten, dass ABC erhalten bleibt = 8!8!
betrachte ABC als 1 Einheit \to→ 5 einzelne Buchstaben,
1 Paar ABC \to→ Anz. Möglichkeiten,
alle Buchstaben umzuordnen, ohne dass das Paar ABC verloren geht = 6! = 7206!=720
Anz. der erhaltenen Wörter aus Permutation von "hallo"
wenn man l_1l1
und l_2l2
als unterschiedliche Buchstaben betrachten würde: 5! = 1205!=120 (Wortlänge)
Anzahl der Zahlpartitionen von nn in
kk
positive Summanden
ungeordnete Zahlpartition
Beispielsaufgaben: Verteilungsprobleme
Wie viele Möglichkeiten gibt es, kk
Weihnachtsgeschenke unter nn Kindern zu
verteilen, so dass jedes Kind mindestens ein Geschenk erhält?
Sowohl die Kinder als auch die Geschenke sind unterscheidbar! \to |F_{n,k}|→∣Fn,k∣
(geordnete Partition von [n][n] in kk
Klassen)
Wie viele Möglichkeiten gibt es, kk
Weihnachtsgeschenke in nn Päckchen
aufzuteilen, so dass jedes Päckchen mindestens ein Geschenk enthält?
Die Päckchen sind nicht unterscheidbar, die Geschenke sind
unterscheidbar\to S_{n,k}→Sn,k
(ungeordnete Partition von [n][n] in kk
Klassen)
Wie viele Möglichkeiten gibt es, nn Euromünzen unter
kk Kindern zu
verteilen, so dass jedes Kind mindestens eine Münze erhält?
Die Münzen sich nicht unterscheidbar, die Kinder sind
unterscheidbar\to |G_{n,k}|→∣Gn,k∣
Wie viele Möglichkeiten gibt es, nn Euromünzen in kk Päckchen
aufzuteilen, so dass jedes Päckchen mindestens eine Münze enthält?
Sowohl die Münzen, als auch die Päckchen sind nicht unterscheidbar! \to |P_{n,k}|→∣Pn,k∣
Wie viele Möglichkeiten gibt es, n Euro in k Päckchen aufzuteilen, wenn Päckchen auch 0 Euro
enthalten dürfen? \to
|H_{n,k}| = |P_{n+k,k}|→∣Hn,k∣=∣Pn+k,k∣
Binomialkoeffizient,
Binomialformel und Vandermondesche Identität
Binomialkoeffizient: {n
\choose k} = \frac{n!}{k!(n-k)!}(kn)=k!(n−k)!n!:
Anzahl der kk-Elementigen
Teilmengen einer nn-Elementigen Menge
Restklasse [a]_m[a]m
von a \mod mamodm: Menge
(Äquivalenzklasse) aller Zahlen, die bei Division durch mm (m \in \Z \land m \neq 0m∈Z∧m=0) denselben
Rest lassen wie aa
[a]_m = a + m\Z[a]m=a+mZ
(a \mod m) = (k \mod
m)(amodm)=(kmodm) für ein beliebiges
k \in Zk∈Z
Kongruenz modulo m \equiv_m≡m:
Zwei Zahlen aa und bb sind
kongruent modulo mm, wenn sie bei der
Division durch mmbeide
denselben Rest haben
beide Zahlen unterscheiden sich um ein ganzzahliges Vielfaches von mm
von oben nach unten: bestimme \lfloor b / a \rfloor⌊b/a⌋, trage Wert von
aa in unteren
Zeile für bb und den
Rest b \mod abmoda für aa ein
wiederhole so lange, bis b \mod a = 0bmoda=0
von unten nach oben: setze \alpha = 1α=1 und b = 0b=0, dann trage Wert von
\alpha_{alt}αalt
in der oberen Zeile für \betaβ und
\beta_{alt} - \lfloor b/a
\rfloor_{current} * \alpha_{alt}βalt−⌊b/a⌋current∗αalt
für \alphaα ein
wiederhole bis zur obersten Zeile
multiplikatives Inverse von a in \left< Z^*_n, \cdot_n, 1\right>⟨Zn∗,⋅n,1⟩: \alpha \mod nαmodn
Test auf ggT: ggT(a,b) = a * \alpha + b * \betaggT(a,b)=a∗α+b∗β
Beispiel: a = 5, b = 911a=5,b=911
Teilerfremde Reste modulo NN und
Primzahltest
Teilerfremde Reste modulo NN:
\Z^*_N := \{ k \in \Z_N | ggT(k, N)
= 1 \}ZN∗:={k∈ZN∣ggT(k,N)=1}
Menge aller Zahlen aus \Z_NZN,
deren größten gemeinsamen Teiler mit N 1 ist /
teilerfremd zu N sind
(*) für additive Gruppen: ord(a) := min\{ k
\in \N \;|\; ka = 0 \}ord(a):=min{k∈N∣ka=0}
(!)ord(a) = ord(a^{-1})ord(a)=ord(a−1)
(!)ord(a)ord(a)muss Teiler von |\mathbb{G}|∣G∣ sein
Erzeugnis von aa: \left< a \right> := \{ a^k |
k \in \Z \} = \{ ... (a^{-1})^2, (a^{-1})^1, 1, a^1, a^2, ...\}⟨a⟩:={ak∣k∈Z}={...(a−1)2,(a−1)1,1,a1,a2,...}
(*) für additive Gruppen: \left< a \right> := \{ ka \;|\; k \in \Z
\}⟨a⟩:={ka∣k∈Z}
(!)\left< a \right> = \left< a^{-1}
\right>⟨a⟩=⟨a−1⟩
(!)ord(a) = |\left< a \right>|ord(a)=∣⟨a⟩∣
Erzeuger von \mathbb{G}G: aa ist ein Erzeuger
von \mathbb{G}G, wenn \left< a\right> =
\mathbb{G}⟨a⟩=G
(!)um ein Element mit Ordnung dd zu
finden: wenn gg ein
Erzeuger von \mathbb{G}G ist (daraus
ord(g) =
|\mathbb{G}|ord(g)=∣G∣), dann gilt für jeden
Teiler d \; | \; ord(g)d∣ord(g), dass g^{ord(g) / d}gord(g)/d
Ordnung dd hat
Gruppenexponent von \mathbb{G}G: \lambda_\mathbb{G} = kgV(\{ord(a)
\; | \; a \in \mathbb{G}\})λG=kgV({ord(a)∣a∈G})
\lambda_\mathbb{G}λG
teilt \mathbb{G}G ohne Rest
(!) Eigenschaften:
a^{ord(a)} = 1aord(a)=1
a^{-1} =
a^{ord(a)-1}a−1=aord(a)−1
a^{k} = a^{k\mod
ord(a)}ak=akmodord(a)
für jedes k \in \Zk∈Z
a^{k} = a^{k\mod
|\mathbb{G}|}ak=akmod∣G∣
für jedes k \in \Zk∈Z
a^{k} = a^{k\mod
\lambda_\mathbb{G}}ak=akmodλG
für jedes k \in \Zk∈Z
\left< a \right> = \{
1, a, a^2, ... , a^{ord(a)-1}\}⟨a⟩={1,a,a2,...,aord(a)−1}
Sei \left< \mathbb{\Z^*_p},
\cdot_p, 1\right>⟨Zp∗,⋅p,1⟩
für p \in
\mathbb{P}p∈P, dann gilt
1 = a^{|\Z^*_p|} =
a^{\varphi(p)} = a^{p-1}1=a∣Zp∗∣=aφ(p)=ap−1
G_{r_a} = (\mathbb{G}, \{ (x,xa) |
x \in \mathbb{G} \})Gra=(G,{(x,xa)∣x∈G})
x\left<a\right>x⟨a⟩: Kreis in G_{r_a}Gra,
der xx enthält
(!) Eigenschaften:
Länge des Kreises: ord(a)ord(a)
jeder Kreis hat die gleiche Länge
Anzahl der Kreisen: |\mathbb{G}| \;/ \; ord(a)∣G∣/ord(a)
(?) Allgemeine Regel: für alle k \geq 3k≥3 gilt...
...\Z^*_{2^k}Z2k∗
(teilerfremde Gruppe einer Zweierpotenz) ist nie zyklisch, wird
aber stets durch 2 Elemente erzeugt, wobei eines die Ordnung 2^{k-2}2k−2,
das andere die Ordnung 2 hat
...der Gruppenexponent\lambdaλ von \Z^*_{2^k}Z2k∗
ist stets 2^{k-2}2k−2
z.B: für \Z^*_{16}Z16∗
sind die Erzeuger beispielsweise 3 und 7 (ord(3) =
4ord(3)=4, ord(7) =
2ord(7)=2) und der
Gruppenexponent ist 4
jedes Tupel beschreibt einen Kreis in G_f = ([n], f)Gf=([n],f)
Zykel können beliebig angeordnet werden, Fixpunkte (Kreise bzw. Tupel der Länge 1)
müssen nicht angegeben werden: (2)(1,3,5)(4) = (3,5,1)(4)(2) = (5,1,3)(2)(1,3,5)(4)=(3,5,1)(4)(2)=(5,1,3)