Kurs:Diskrete Mathematik (Osnabrück 2020)/Liste der Hauptsätze

???: Satz über die Wohldefiniertheit der Anzahl

Wenn ${}M$ eine Menge ist und wenn

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

bijektive Abbildungen sind,

so ist

${}n=k\,.$

Die Anzahl einer endlichen Menge ist also wohldefiniert.

 

???: Schubfachprinzip

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und ${}N$ eine endliche Menge mit ${}n$ Elementen. Es sei ${}m>n$.

Dann gibt es keine injektive Abbildung

$M\longrightarrow N.$

 

???: Injektiv und surjektiv bei gleicher Anzahl

Seien ${}M$ und ${}N$ endliche Mengen mit ${}n$ Elementen. Dann sind für eine Abbildung

$F\colon M\longrightarrow N$

die Begriffe injektiv, surjektiv und bijektiv äquivalent.

 

???: Satz über die Addition und endliche Mengen

Es seien ${}M$ und ${}N$ disjunkte endliche Mengen mit ${}m$ bzw. ${}n$ Elementen.

Dann besitzt ihre Vereinigung ${}M\cup N$ gerade ${}m+n$ Elemente.

 

???: Satz über die Multiplikation und endliche Mengen

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen.

Dann besitzt die Produktmenge ${}M\times N$ genau ${}m\cdot n$ Elemente.

 

???: Satz über die Urbildanzahl

Es seien ${}L$ und ${}M$ endliche Mengen und es sei

$f\colon L\longrightarrow M$

eine Abbildung.

Dann gilt

${}{\#\left(L\right)}=\sum _{y\in M}{\#\left(f^{-1}(y)\right)}\,.$

 

???: Satz über die Abbildungsanzahl

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen.

Dann gibt es ${}m^{\ell }$ Abbildungen von ${}L$ nach ${}M$.

 

???: Satz über die Anzahl von bijektiven Abbildungen

Es seien ${}M$ und ${}N$ endliche Mengen, die beide ${}n$ Elemente besitzen.

Dann gibt es ${}n!$ bijektive Abbildungen von ${}M$ nach ${}N$.

 

???: Die Anzahl der Permutationen

Auf einer endlichen Menge ${}M$ mit ${}n$ Elementen

gibt es ${}n!$ bijektive Abbildungen von ${}M$ nach ${}M$.

 

???: Satz über die Anzahl der Potenzmenge

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen.

Dann besitzt die Potenzmenge ${}{\mathfrak {P}}\,(M)$ genau ${}2^{m}$ Elemente.

 

???: Teilmengenanzahl

Die Anzahl der ${}k$-elementigen Teilmengen in einer ${}n$-elementigen Menge ist

${\frac {n!}{k!(n-k)!}}.$

 

???: Pascaldreieck

Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,.$

 

???: Siebformel

Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei

${}A_{J}=\bigcap _{i\in J}A_{i}\,.$

Dann ist

${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}\,.$

 

???: Satz über die Anzahl von fixpunktfreien Permutationen

Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit ${}n$ Elementen ist

$\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}.$

 

???: Allgemeines Distributivgesetz (kommutativer Halbring)

Es sei ${}R$ ein kommutativer Halbring und es seien ${}a_{1},\ldots ,a_{r},b_{1},\ldots ,b_{s}$ Elemente aus ${}R$.

Dann gilt das allgemeine Distributivgesetz

${}{\left(\sum _{i=1}^{r}a_{i}\right)}{\left(\sum _{k=1}^{s}b_{k}\right)}=\sum _{1\leq i\leq r,\,1\leq k\leq s}a_{i}b_{k}\,.$

 

???: Der Binomische Lehrsatz

Es sei ${}R$ ein kommutativer Halbring und ${}a,b\in R$. Ferner sei ${}n$ eine natürliche Zahl.

Dann gilt

$(a+b)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}.$

 

???: Lösbarkeit von Gleichungen in einer Gruppe

Es sei ${}(G,e,\circ )$ eine Gruppe.

Dann besitzen zu je zwei Gruppenelementen ${}a,b\in G$ die beiden Gleichungen

$a\circ x=b{\text{ und }}y\circ a=b$

eindeutige Lösungen ${}x,y\in G$.

 

???: Nichtnullteilereigenschaft in einem Körper

Es sei ${}K$ ein Körper. Aus ${}a\cdot b=0$

folgt ${}a=0$ oder ${}b=0$.

 

???: Satz über geordnete Mengen und Potenzmengen

Es sei ${}(M,\leq )$ eine geordnete Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge von ${}M$.

Dann ist die Abbildung

$M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto {\left\{y\in M\mid y\leq x\right\}},$

ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.

 

???: Lemma von Bezout (${}\mathbb {N}$)

Es seien ${}a,b\in \mathbb {N}$ zwei teilerfremde natürliche Zahlen.

Dann gibt es ganze Zahlen ${}r,s\in \mathbb {Z}$ mit ${}ra+sb=1$.

 

???: Division mit Rest (${}\mathbb {Z}$)

Es sei ${}d$ eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder ganzen Zahl ${}n$ eine eindeutig bestimmte ganze Zahl ${}q$ und eine eindeutig bestimmte natürliche Zahl ${}r$, ${}0\leq r\leq d-1$, mit

${}n=qd+r\,.$

 

???: Satz über die Untergruppen von ${}\mathbb {Z}$

Die Untergruppen von ${}\mathbb {Z}$ sind genau

die Teilmengen der Form

${}\mathbb {Z} d={\left\{kd\mid k\in \mathbb {Z} \right\}}\,$

mit einer eindeutig bestimmten nichtnegativen Zahl ${}d$.

 

???: Beschreibung des Durchschnitts von Untergruppen von ${}\mathbb {Z}$

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen.

Dann ist

${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,,$

wobei ${}u$ das kleinste gemeinsame Vielfache der ${}a_{1},\ldots ,a_{k}$ ist.

 

???: Das Lemma von Euklid

Es sei ${}p$ eine Primzahl und ${}p$ teile ein Produkt ${}ab$ von natürlichen Zahlen ${}a,b\in \mathbb {N}$.

Dann teilt ${}p$ einen der Faktoren.

 

???: Der Hauptsatz der elementaren Zahlentheorie

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

 

???: Satz über die atomare Darstellung in einem booleschen Verband

In einem endlichen booleschen Verband

besitzt jedes Element ${}x\in B$ eine eindeutige Darstellung der Form

${}x=a_{1}\sqcup \ldots \sqcup a_{n}\,$

mit Atomen ${}a_{j}$.

 

???: Isomorphiesatz für endliche boolesche Verbände

Jeder endliche boolesche Verband ${}B$

ist isomorph zur Potenzmenge einer endlichen Menge.

 

???: Äquivalenzrelation durch Abbildung

Es seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung.

Dann wird durch die Festlegung

${}x\sim y\,,$

wenn

${}f(x)=f(y)\,,$

eine Äquivalenzrelation auf ${}M$ definiert.

 

???: Universelle Eigenschaft der Quotientenmenge

Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit der Quotientenmenge ${}M/\sim$. Es sei ${}\varphi \colon M\rightarrow W$ eine Abbildung mit ${}\varphi (x)=\varphi (y)$ für alle ${}x,y\in M$ mit ${}x\sim y$.

Dann gibt es eine eindeutig bestimmte Abbildung ${}{\overline {\varphi }}\colon M/\sim \,\,\rightarrow W$ mit ${}\varphi ={\overline {\varphi }}\circ q$.

 

???: Aquivalenzrelation zu Untergruppe

Es sei ${}(G,0,+)$ eine kommutative Gruppe, ${}H\subseteq G$ eine Untergruppe und ${}\sim _{H}$ die durch ${}H$ auf ${}G$ definierte Relation.

Dann liegt eine Äquivalenzrelation vor, und die Äquivalenzklasse zu ${}0$ ist gerade ${}H$.

 

???: Algebraische Struktur der Restklassengruppe

Es sei ${}(G,0,+)$ eine kommutative Gruppe, ${}H\subseteq G$ eine Untergruppe und ${}G/H$ die Quotientenmenge zur durch ${}H$ definierten Äquivalenzrelation auf ${}G$ mit der kanonischen Projektion

$q\colon G\longrightarrow G/H,\,g\longmapsto [g].$

Dann gibt es eine eindeutig bestimmte Gruppenstruktur auf ${}G/H$ derart, dass ${}q$ ein Gruppenhomomorphismus ist.

 

???: Algebraische Struktur der Restklassenringe

Es sei ${}R$ ein kommutativer Ring, ${}{\mathfrak {a}}\subseteq R$ ein Ideal und ${}R/{\mathfrak {a}}$ die Quotientenmenge zur durch ${}{\mathfrak {a}}$ definierten Äquivalenzrelation auf ${}R$ mit der kanonischen Projektion

$q\colon R\longrightarrow R/{\mathfrak {a}},\,g\longmapsto [g].$

Dann gibt es eine eindeutig bestimmte Ringstruktur auf ${}R/{\mathfrak {a}}$ derart, dass ${}q$ ein Ringhomomorphismus ist.

 

???: Restklassenkörper von ${}\mathbb {Z}$

Es sei ${}n\in \mathbb {N}$. Der Restklassenring ${}\mathbb {Z} /(n)$ ist genau dann ein Körper,

wenn ${}n$ eine Primzahl ist.

 

???: Der Multinomialsatz (kommutativer Halbring)

Es sei ${}R$ ein kommutativer Halbring und seien ${}x_{1},\ldots ,x_{k}\in R$ Elemente und ${}n\in \mathbb {N}$.

Dann ist

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

 

???: Anzahl der Abbildungen mit vorgeschriebener Faseranzahl

Es sei ${}A$ eine ${}n$-elementige Menge und seien ${}(r_{1},\ldots ,r_{k})$ mit ${}\sum _{j=1}^{k}r_{j}=n$ vorgegeben.

Dann ist die Anzahl der Abbildungen ${}f$ von ${}A$ nach ${}\{1,\ldots ,k\}$ mit der Eigenschaft, dass ${}{\#\left(f^{-1}(j)\right)}=r_{j}$ für alle ${}j$ ist, gleich

${\binom {n}{r_{1},\dotsc ,r_{k}}}.$

 

???: Satz über die Anzahl der surjektiven Abbildungen mit Multinomialkoeffizienten

Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{(r_{1},\ldots ,r_{k}):\,r_{1}+r_{2}+\cdots +r_{k}=n,\,r_{j}\geq 1}{\binom {n}{r_{1},\dotsc ,r_{k}}}.$

 

???: Satz über die Anzahl der surjektiven Abbildungen mit Produktpotenzen

Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.$

 

???: Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten

Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

$\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}.$

 

???: Rekursionsformel für die Anzahl der surjektiven Abbildungen

Zu ${}n,k\in \mathbb {N}$ bezeichne ${}\operatorname {Surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge.

Dann gilt die Rekursionsformel

${}\operatorname {Surj} (n+1,k)=k\cdot \operatorname {Surj} (n,k)+k\cdot \operatorname {Surj} (n,k-1)\,.$

 

???: Beziehung zwischen Äquivalenzrelationen und Partitionen

Es sei ${}M$ eine Menge.

Es gibt eine natürliche Korrespondenz zwischen Äquivalenzrelationen auf ${}M$ und Partitionen auf ${}M$.

Dabei wird einer Äquivalenzrelation die Menge ihrer Äquivalenzklassen zugeordnet, und einer Partition wird diejenige Äquivalenzrelation zugeordnet, bei der zwei Elemente als äquivalent angesehen werden, wenn sie in dem gleichen Block der Partition liegen.

 

???: Satz über die Anzahl der surjektiven Abbildungen und Stirling-Zahlen zweiter Art

Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge.

Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich ${}k!S({n},{k})$.

 

???: Unterscheidbare Kugeln auf ununterscheidbare Urnen

Die Stirlingsche Zahl zweiter Art ${}S({n},{k})$

beschreibt die Anzahl an Möglichkeiten, ${}n$ unterscheidbare Kugeln auf ${}k$ ununterscheidbare Urnen so zu verteilen, dass keine Urne leer bleibt.

 

???: Rekursionsformel für Stirling-Zahlen zweiter Art

Die Stirling-Zahlen zweiter Art erfüllen die Rekursionsformel

${}S({n+1},{k})=k\cdot S({n},{k})+S({n},{k-1})\,.$

 

???: Satz über die Gradsumme in einem Graphen

Es sei ${}(V,E)$ ein Graph.

Dann gilt

${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$

 

???: Satz über die Anzahl von Knoten mit ungeradem Grad

Es sei ${}(V,E)$ ein Graph.

Dann ist die Anzahl der Knoten, die einen ungeraden Grad besitzen, gerade.

 

???: Faktorisierungssatz für Graphhomomorphismen

Es sei ${}\varphi \colon G\rightarrow H$ ein schwacher Homomorphismus zwischen den Graphen ${}G=(V,E)$ und ${}H=(W,F)$.

Dann gibt es eine Faktorisierung von ${}\varphi$ als

$G{\stackrel {q}{\longrightarrow }}G/\sim {\stackrel {r}{\longrightarrow }}(U,K){\stackrel {s}{\longrightarrow }}(U,K'){\stackrel {t}{\longrightarrow }}(W,F),$

wobei ${}q$ die Quotientenabbildung zu einer Äquivalenzrelation auf ${}V$ ist, ${}r$ ein Isomorphismus ist, ${}s$ einen knotenidentischen Untergraphen und ${}t$ einen vollen Untergraphen beschreibt.

 

???: Charakterisierungssatz für Bäume

Es sei ${}G=(V,E)$ ein Graph mit nichtleerer Knotenmenge ${}V$. Dann sind folgende Aussagen äquivalent.

1. ${}G$ ist ein Baum.
2. Zwischen je zwei Punkten ${}u,v\in V$ gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
3. ${}G$ ist zusammenhängend und es gilt ${}{\#\left(E\right)}={\#\left(V\right)}-1$.

 

???: Existenzsatz für aufspannende Bäume

Ein zusammenhängender Graph

besitzt einen aufspannenden Baum.

 

???: Ergänzungssatz für Wälder

Es sei ${}G=(V,E)$ ein Graph mit ${}n$ Knotenpunkten und ${}c$ Zusammenhangskomponenten.

Dann lässt sich jeder Unterwald ${}(W,F)\subseteq (V,E)$ mit weniger als ${}n-c$ Kanten zu einem Unterwald mit ${}n-c$ Kanten ergänzen.

 

???: Satz über die kombinatorische Struktur einer Waldmenge

Zu einem Graphen ${}G=(V,E)$ ist die Waldmenge ${}{\mathcal {W}}(G)$ (mit der vollen Knotenmenge)

ein Matroid auf ${}E$.

Der Rang dieses Matroids ist die Anzahl der Kanten in einem aufspannenden Wald.

 

???: Rekursionssatz für aufspannende Bäume

Es sei ${}G$ ein schleifenfreier Multigraph und ${}e$ eine Kante von ${}G$.

Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

${}t(G)=t(G\setminus e)+t(G/e)\,.$

 

???: Satz über Potenzen der Adjazenzmatrix

Es sei ${}G=(V,E)$ ein Graph mit zugehöriger Adjazenzmatrix ${}A$.

Dann ist die Anzahl der Wege von ${}u$ nach ${}v$ der Länge ${}\ell$ gleich dem Eintrag an der Stelle ${}(u,v)$ zur Matrixpotenz ${}A^{\ell }$.

 

???: Satz von Kirchhoff

Es sei ${}G$ ein Multigraph und sei ${}L$ die Laplace-Matrix zu ${}G$. Es sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von ${}G$ gleich der Determinante von ${}L'$.

 

???: Charakterisierungssatz für bipartite Graphen mittels Kreisen

Ein Graph

ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.

 

???: Paarungssatz

Es sei ${}M$ eine Menge, es sei ${}I$ eine endliche Indexmenge und zu jedem ${}i\in I$ sei eine Teilmenge ${}M_{i}\subseteq M$ gegeben. Zu einer Teilmenge ${}J\subseteq I$ setzen wir

${}M_{J}=\bigcup _{j\in J}M_{j}\,.$

Für jede Teilmenge ${}J\subseteq I$ gelte

${}{\#\left(M_{J}\right)}\geq {\#\left(J\right)}\,.$

Dann gibt es eine injektive Abbildung

$f\colon I\longrightarrow M$

mit ${}f(i)\in M_{i}$.

 

???: Satz von Berge

Eine Paarung ${}P$ in einem Graphen ${}G$

ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

 

???: Satz von König

In einem bipartiten Graphen

stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.

 

???: Satz von Ore

Es sei ${}G=(V,E)$ ein Graph mit mindestens drei Elementen, der die Bedingung

${}d(u)+d(v)\geq {\#\left(V\right)}\,$

für je zwei nicht adjazente Knoten ${}u,v$ erfüllt.

Dann ist ${}G$ hamiltonsch.

 

???: Charakterisierungssatz für eulersche Graphen

Für einen zusammenhängenden Graphen ${}G=(V,E)$ sind folgende Aussagen äquivalent.

1. ${}G$ ist eulersch.
2. Jeder Knotenpunkt von ${}G$ hat einen geraden Grad.
3. ${}G$ ist die Vereinigung von kantendisjunkten Kreisen (wobei ein einzelner Punkt hier als Kreis gelte).

 

???: Satz über nichtgeschlossene Eulerzüge

In einem zusammenhängenden Graphen ${}G=(V,E)$

gibt es genau dann einen nichtgeschlossenen Eulerzug, wenn es genau zwei Knotenpunkte mit ungeradem Grad gibt.

 

???: Satz über das chromatische Polynom

Das chromatische Polynom ${}P_{G}$ zu einem Graphen mit ${}n$ Knotenpunkten

ist ein normiertes Polynom vom Grad ${}n$.

 

???: Die eulersche Polyederformel

Es sei ${}G$ ein zusammenhängender planarer Graph mit ${}n$ Knotenpunkten, ${}m$ Kanten und ${}g$ Gebieten.

Dann gilt die eulersche Polyederformel

${}n-m+g=2\,.$

 

???: Satz über die Gebietsanzahl

Zu einem zusammenhängenden planaren Graphen

ist die Anzahl der Gebiete unabhängig von der ebenen Realisierung.

 

???: Sechs-Farben-Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens sechs Farben.

 

???: Fünf-Farben-Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens fünf Farben.

 

???: Vier-Farben-Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens vier Farben.