FS21

1

c)

$G[N(v)]$ sind nur die Knoten in $N(v)$ und die Edges zwischen ihnen (nicht alle Knoten die verbunden sind).

d)

Seien $P,Q$ zwei Mengen von Punkten. Dann gilt $Conv(P\cap Q)=Conv(P)\cap Conv(Q)$.

Die convex hull ist eine Fläche → Menge von Punkten die covered, nicht nur die Punkte die die Hull definieren. Die Intersektion von $P\cap Q$ ist also empty hier, die Convex hull aber nicht (sie intersecten auf der Fläche) → non null Fläche.

2

b)

Anmerken dass $t\ge 0$ (also nicht-negativ) ist für Chebychev.

c)

Richtig rechnen!
Außerdem staten, dass $X$ die Summe von unabhängigen Bernoulli-Experimenten ist.

3

Fische im Teich

Anstatt es kompliziert zu machen und so, einfach $p_i=\frac{i}{n+i}$ wo $i$ die “Fische die übrig sind” ist.
Dann gilt $X_i\sim \text{Geo}(\frac{i}{n+i})$ und der Rest ist easy.

$\frac{i}{n+i}=\frac{\text{\# salmon}}{\#otherfish+\#salmon}$.

5

a)

Note das der Algo mit irgendeiner Kante anfängt ”$\{e\}$ für irgendeine Kante $e\in E$“.

b)

Jede Runde wird der Pfad um mindestens $+2$ länger.
Das heisst das nach $\sqrt{V}$ durchläufen $k\ge 2\sqrt{V}$.

Es gilt $|M^{\prime }|\le |M|+\frac{|V|}{k+1}$ wobei $k$ die Länge des kürzesten augmentierenden Pfades ist.

Sobald $k\ge \sqrt{V}$ gilt, hat das maximale Matching höchstens $|M^{\prime }|\le |M|+\frac{|V|}{\sqrt{|V|}}$ und damit $|M^{\prime }|\le |M|+\sqrt{V}$, also $\sqrt{V}$ Kanten mehr. Da das Matching jede Runde um mindestens eine Kante größer wird (die Pfade um 2) gilt dass wir dann nur noch $\sqrt{V}$ Durchläufe brauchen.

Insgesamt brauchen wir also $\frac{\sqrt{V}}{2}+\sqrt{V}=O(\sqrt{V})$.

c)

Sei $G$ bipartit mit $|A|=|B|$ Prove das für $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ wo das die Mengen die nicht von $M$ überdeckt sind. Zeigen sie das $\mathrm{deg}(a)+\mathrm{deg}(b)\le |A|-|A^{\prime }|$

Wir wissen $|A^{\prime }|=|B^{\prime }|$ da $|A^{\prime }|=|A|-|M|=|B|-|M|=|B^{\prime }|$.

Proof $|A|-|A^{\prime }|=|M|$, da es die überdeckten Knoten zählt.

• es kann keine Kante von $a\in A^{\prime }$ (oder $b\in B^{\prime }$) zu einem unüberdeckten Knoten geben, da $M$ maximal ist.
  • also sind alle Nachbarn von $a,b$ überdeckt.
  • Da $|A^{\prime }|=|B^{\prime }|$ gilt auch das $A_m,B_m$ die Sets der überdeckten Knoten $|A_M|=|B_M|$.
• Nehme an $\mathrm{deg}(a)+\mathrm{deg}(b)>|A|-|A^{\prime }|=|M|$.
  • $N(a)\subseteq B_M$ und $N(b)\subseteq A_M$.
  • Deswegen gilt für alle zu Nachbarn von $a,b$, dass sie genau zu einer Kante $\in M$ inzident sind.
  • wenn sie gemeinsam mehr als $|M|$ Nachbarn haben, muss es ein paar geben, welches sich eine Kante teilt.
    • sonst gibt es einen augmentierenden Pfad.

Formell mit Injektion: Es gibt ${\varphi }_A:A_M\to M$ welche jedem überdeckten Knoten genau eine Kante aus $M$ zuweist (das gleiche für B).
Da die Funtionen injektiv sind gilt $|{\varphi }_B(N(a))|+|{\varphi }_A(N(b))|=|N(a)|+|N(b)|>|M|$ nach Annahme.

• ${\varphi }_B(N(a)),{\varphi }_A(N(b))\subseteq M$ und $|{\varphi }_B(N(a))|+|{\varphi }_A(N(b))|>|M|⟹{\varphi }_B(N(a))\cap {\varphi }_A(N(b))\ne \varnothing$ .
• Also muss es eine Kante in beiden Sets gemeinsam geben. Diese bildet einen augmentierenden Pfad.

6

a)