Aktualizováno 15. Srpna 2023

Parafrázování článku Spanning Trees of the Complete Bipartite Graph ↗.

Věta

Počet koster úplného bipartitního grafu $K_{m,n}$ je $n^{m-1} m^{n-1}$.

Lemma

Mějme kostru T grafu $K_{m,n}, m \leq n$, s vrcholy rozdělenými na množiny $M={a_1,\dots,a_m}$ a $N={b_1,\dots,b_n}$, kde množiny $M,N$ jsou barvy přirozeného obarvení úplného bipartitního grafu. Pak pro nějaké k, $1 \leq k \leq n, \textrm{deg}(b_k)=1$.

Důkaz lemma

Mějme $A, B$ součty stupňů uvnitř T vrcholů v $M, N$ resp. Zřejmě $A=B$ a $(A+B)/2=m+n-1$, protože $T$ je strom. Takže \[B = \frac{A+B}{2}=m+n-1,\] a kdyby $\textrm{deg}(b_j) \ge 2$ platilo pro všechny j, pak \[B \geq m+n > m+n-1,\] což je spor s předchozí rovností pro $B$. Takže existuje $k$ takové že $\textrm{deg}(b_k) = 1$.

$\square$

Důkaz věty

Bez újmu na obecnosti mějme $m \leq n$. Označme si partity $K_{m,n}$ jako $M={a_1,\dots,a_m}$ a $N={b_1,\dots,b_n}$. Dokážeme, že řada délky $m+n-2$ ve tvaru \[a_{i_1},a_{i_2},\dots,a_{i_{n-m+1}},b_{j_1},a_{i_{n-m+2}},b_{j_2},\dots,a_{i_{n-1}},b_{j_{m-1}},\] kde prvky nemusí být nutně různé, přímo koresponduje s kostrou $K_{m,n}$. Hodnoty $a_i$ budou nabývat $n$ různých hodnot zatímco $b_j$ budou nabývat $m$ různých hodnot. Pozorujeme, že taková řada má přesně $m^{n-1} n^{m-1}$ možných variant.

Mějme kostru $T_0$ grafu $K_{m,n}$, pak řada $S_0$ je svázaná s $T_0$ následujícím způsobem. Z dokázaného lemma existuje v $N$ list uvnitř $T_0$. Vezměme z $N$ list s nejmenším ID a zapišme do řady $S_0$ jeho rodiče a odmažme ho z $T_0$, čímž vznikne strom $T_1$. Tento proces opakujeme dokud se nedostaneme k poslední hraně.

Je jasné, že zápis vybraného stromu je jednoznačný (popsali jsme algo.), ale je vybraný zápis zápisem k pouze jednomu stromu? idk…

Tento zápis je tzv. Prüferův kód, a 1 k 1 koresponduje se stromem.

$\square$