Počty koster
Úloha číslo: 3747
Určte počet koster následujících grafů
Varianta
\(C_m \oplus_e C_n\) (slepím za hranu)
Nápověda
Kostry rozdělíme na dvě skupiny: na obsahující hranu \(e\) a na ostatní.
V první skupině je pak třeba ze zbylých \(m-1\) hran cyklu \(C_m\) sestavit kostru \(C_m\), což lze provést \(m-1\) způsoby a zároveň totéž povést pro \(C_n\).
Kostry v druhé skupině odpovídají kostrám v \((C_m \oplus_e C_n)-e=C_{m+n-2}\).
Řešení
Graf \(C_m \oplus_e C_n\) má \((m-1)(n-1) + m+n-2\) koster.
Varianta
\(C_m \oplus_e K_n\)
Nápověda
Využijte faktu, že koster \(K_n\) obsahujících pevně zvolenou hranou \(e\) je \(2n^{n-3}\).
Řešení
Každou kostru \(K_n\) lze rozšířit \(m-1\) způsoby no kostru celého grafu.
Zbývá určit počet koster \(T\), jejichž průnik s \(K_n\) je nesouvislý, neboli má dvě komponenty. (Tyto kostry nutně obsahují \(m-1\) hran z \(C_m\) a to všechny s vyjímkou \(e\).)
Přidáme-li do \(T\cap K_n\) hranu \(e\), dostaneme opět kostru \(K_n\), tedy je jich stejně jako koster \(K_n\) obsahujících pevně zvolenou hranu \(e\).
Odpověď
Graf \(C_m \oplus_e K_n\) má \(n^{n-2}(m-1)+2n^{n-3}\) koster.
Varianta
\(K_m \oplus_e K_n\)
Odpověď
Graf \(K_m \oplus_e K_n\) má \(2m^{m-3}n^{n-3}(m+n-2)\) koster.
Varianta
\(K_n \div e\) (podrozdělíme jednu hranu)
Odpověď
Graf \(K_n \div e\) má \((2n-2)n^{n-3}\) koster.
Varianta
\(K_n \div E\) (podrozdělíme všechny hrany)
Odpověď
Graf \(K_n \div E\) má \(n^{n-2}2^{{n \choose 2}-(n-1)}\) koster.
Varianta
\(2K_n\) (ke každé hraně přidáme jednu paralelní)
Odpověď
Graf \(2K_n\) má \(n^{n-2}2^{(n-1)}\) koster.
Varianta
\(K_{m,n}\)
Nápověda
Upravte důkaz využívající povykosy nebo spočítejte počet koster pomocí determinantů.
Řešení
Označme \(A\) tu část \(K_{m,n}\) s \(m\) vrcholy a \(B\) tu zbylou.
Budeme počítat dvěma způsoby počet koster zakořeněných ve vrcholu z \(A\), kde šipky vedoucí z \(A\) do \(B\) jsou očíslovány \(1,…,m-1\) (z kořene žádná šipka nevychází). Šipky vedoucí z \(B\) do \(A\) žádná čísla nemají.
Takovýchto upravených koster je \(\kappa(K_{m,n})m(m-1)!\).
Pro druhý způsob výpočtu postupujeme následovně: Nejprve zvolíme z každého vrcholu \(B\) jednu šipku do libovolného vrcholu \(A\) – celkem \(m^n\) možností. Nyní máme \(m\) komponent, každá vypadá jako hvězda se středem v \(A\).
Postupně přidáme \(m-1\) šipek z \(A\) do \(B\). V \(i\)-tém kroku přidáme šipku očíslovanou \(i\) vedoucí do libovolného vrcholu \(B\) ovšem z kořene nějaké jiné komponenty \(A\) – což pro \(i\)-tý krok znamená \(n(m-i)\) možností.
Upravením rovnosti \(\displaystyle \kappa(K_{m,n})m(m-1)!=m^n \prod_{i=1}^{m-1}n(m-1) \) dostaneme výsledek.
Pro další kombinatorický důkaz vizte http://dx.doi.org/10.1016/0012-365X(90)90377-T
Odpověď
Graf \(K_{m,n}\) má \(m^{n-1}n^{m-1}\) koster.
Varianta
\(K_{m,n} - e\)
Odpověď
Graf \(K_{m,n} - e\) má \((m-1)(n-1)m^{n-2}n^{m-2}\) koster.
Varianta
\(K_{m,n} \div E\)
Odpověď
Graf \(K_{m,n} \div E\) má \(2^{(m-1)(n-1)}m^{n-1}n^{m-1}\) koster.