From 20e9da0124cdf3d4b988b6a1705e90ed44f9bdb4 Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Sat, 23 Aug 2025 12:39:29 +0300 Subject: improve other section (kirchhoff and dilworth) --- content/other/other.tex | 25 +++++++++++++++++-------- 1 file changed, 17 insertions(+), 8 deletions(-) (limited to 'content/other/other.tex') diff --git a/content/other/other.tex b/content/other/other.tex index a5004fb..d3e2a47 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -154,7 +154,7 @@ Das Komplement eines Vertex-Cover ist ein Independent Set. $\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover. - \item \textbf{Bipartiter Graph:} + \item \textbf{Bipartiter Graph (Satz von \textsc{König}):} Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching. Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$. @@ -189,15 +189,19 @@ \item \textbf{Verteilung von Primzahlen:} Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$. - \item \textbf{Satz von \textsc{Kirchhoff}:} + \item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):} Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten. - Sei $A$ die Adjazenzmatrix von $G$. + Sei $A$ die Adjazenzmatrix von~$G$. Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$. - Sei $B$ eine Diagonalmatrix, $b_{ii}$ sei der Grad von Knoten $i$. + Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$. Definiere $R = B - A$. - Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$. + Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante. + Das Ergebnis ist die Anzahl der Spannbäume von $G$. \newline - Entferne letzte Zeile und Spalte und berechne Betrag der Determinante. + Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man + berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte. + Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$, + sodass jeder Knoten einen Pfad zu $k$ hat. \item \textbf{\textsc{Dilworths}-Theorem:} Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset). @@ -208,10 +212,15 @@ Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition. $\Rightarrow$ \emph{Weite} des Poset. \newline - Berechnung: Maximales Matching in bipartitem Graphen. + Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen. Dupliziere jedes $s \in S$ in $u_s$ und $v_s$. Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu. - Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. + Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette. + \newline + Berechnung der maximalen Antikette: Verwende Satz von König, um ein + minimales Vertexcover des bipartiten Graphen zu finden. + Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset. + Das Komplement davon ist eine maximale Antikette. \item \textbf{\textsc{Turan}'s-Theorem:} Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist: -- cgit v1.2.3