Title: Matfyz / Lineární algebra 1 / Aplikace

Q: Zformulujte problém o počtu sudých podgrafů a vyřešte jej.
A: Nechť \(G\) je souvislý graf a \(\mathcal{A}\) obsahuje množiny hran \(A\) takové, že každý vrchol \(G\) náleží sudému počtu hran v \(A\). Tyto množiny \(A\) určují tzv. sudé podgrafy \(G\). Kolik sudých podgrafů obsahuje \(G\)?
Symetrický rozdíl \(\triangle\) zachovává sudé stupně, protože symetrický rozdíl dvou množin sudé mohutnosti, konkrétně hran incidentních s vrcholem, má také sudou mohutnost. \[|A\mathbin{\triangle}B|=|A|+|B|-2|A\cap B|\]Proto \((\mathcal{A},\triangle,\cdot)\) tvoří vektorový prostor nad \(\mathbb{Z}_2\).
Pro prostory konečné mohutnosti platí \(|\mathcal{A}|=|T|^{\operatorname{dim}(\mathcal{A})}\).
Ekvivalentní problém: Sestrojte bázi \(\mathcal{A}\).
Pro libovolnou kostru \(K\) grafu \(G\) označme \(\{e_1,\ldots,e_k\}=E_G\setminus E_K\). Pro každé \(i\in\{1,\ldots,k\}\) určíme unikátní cyklus \(C_i\) v grafu \(K\cup e_i\).
Množina \(\mathcal{C}=\{C_1,\ldots,C_k\}\) je lineárně nezávislá, nebot’ pro každé \(i\) platí, že hrana \(e_i\) patří do \(C_i\), ale nelze ji eliminovat symetrickým rozdílem \(C_i\) s ostatními cykly z \(\mathcal{C}\), nebot’ ty \(e_i\) neobsahují.
Pro libovolný sudý podgraf \(A\) označme \(\{e_{i_1},\ldots,e_{i_l}\}=A\setminus E_K\), čili \(i_1,\ldots,i_l\in\{1,\ldots,k\}\) jsou indexy hran z \(A\) mimo kostru \(K\).
Graf \(A\mathbin{\triangle}C_{i_1}\mathbin{\triangle}C_{i_2}\mathbin{\triangle}\ldots\mathbin{\triangle}C_{i_l}\) je sudým podgrafem \(G\), ale také je podgrafem \(K\), nebot’ nemá žádnou hranu z \(E_G\setminus E_k\). Strom nemá žádné cykly, tudíž \(A\mathbin{\triangle}C_{i_1}\mathbin{\triangle}C_{i_2}\mathbin{\triangle}\ldots\mathbin{\triangle}C_{i_l}=0\).
Úpravou rovnosti lze získat \(A=C_{i_1}\mathbin{\triangle}C_{i_2}\mathbin{\triangle}\ldots\mathbin{\triangle}C_{i_l}\). Proto \(\mathcal{C}\) generuje \(\mathcal{A}\).
Dostáváme: \(\operatorname{dim}(\mathcal{A})=|\mathcal{C}|=k=|E_G|-|E_K|=|E_G|-|V_G|+1\).
Odpověď: Každý souvislý graf \(G\) má \(2^{|E_G|-|V_G|+1}\) sudých podgrafů.

Q: Zformulujte problém o množinových systémech s omezeními na mohutnosti a vyřešte jej.
A: Kolik podmnožin může mít \(n\)-prvková množina, pokud každá podmnožina má mít lichou velikost, ale průnik každé dvojice různých podmnožin má mít sudou velikost?
Formálně: \(\max k:\exists A_1,\ldots,A_k\subseteq\{1,\ldots,n\}\ \forall i\neq j: 2\nmid |A_i|\land 2 \mid |A_i\cap A_j|\)
Ukázka: \(n=5, k=3\):
Věta: Vždy platí, že \(k\leq n\), neboli existuje nejvýše \(n\) podmnožin \(A_1,\ldots,A_n\) předepsaných vlastností (například jednoprvkových).
Sestrojíme tzv. matici incidence \(M\in\mathbb{Z}^{k\times n}_2\) předpisem:
\(m_{ij}=\begin{cases} 1 & \text{pokud }j\in A_i\\ 0 & \text{pokud }j\notin a_i \end{cases}\).
Matice splňuje \(MM^\top =I_k\), protože nad \(\mathbb{Z}_2\) máme:
\((MM^\top)_{ij}=\begin{cases} 1 & \text{pro $i=j$, protože toto je parita $|A_i|$}\\ 0 & \text{pro $i\neq j$, protože toto je parita $|A_i\cap A_j|$} \end{cases}\).
Nyní \(k=\operatorname{rank}(I_k)=\operatorname{rank}(MM^\top)\leq\operatorname{rank}(M)\leq n\)
Poznámka: Pokud zvolíme \(M\in{\color{red}\mathbb{R}}^{k\times n}\), pak \((MM^\top)_{ij}=|A_i\cap A_j|\).

Q: Zformulujte problém o dělení obdélníku na čtverce a vyřešte jej.
A: Lze obdélník s iracionálním poměrem délek jeho stran rozdělit na konečně mnoho čtverců?
Poznámka: Pro racionální \(p : q\) vezmeme \(pq\) jednotkových čtverců.
Věta: Pro iracionální poměr žádné takové rozdělení neexistuje.
Důkaz: Necht’ má obdélník \(R\) délky stran \(1 : x\), kde \(x\in\mathbb{R}\setminus\mathbb{Q}\). \(\mathbb{R}\) tvoří vektorový prostor nad \(\mathbb{Q}\). Zde jsou 1 a \(x\) lineárně nezávislé. Zvolme libovolné lineární \(f:\mathbb{R}\to\mathbb{R}\), kde \(f(1)=1\) a \(f(x)=-1\). Takové zobrazení \(f\) existuje, protože je dán obraz části báze. Pro \(A\) o stranách \(a, b\) definujeme "plochu" jako \(v(A)=f(a)f(b)\). Pokud postupně rozdělíme \(A\) na \(B_1,\ldots,B_k\), pak \(v(A)=\sum_{i=1}^kv(B_i)\).
... dělíme-li \(A\) na \(B_1\) a \(B_2\), pak \(v(A)=v(B_1)+v(B_2)\).
\(f(a)f(b)=f(a_1+a_2)f(b)=(f(a_1)+f(a_2))f(b)=f(a_1)f(b)+f(a_2)f(b)\)
Pokud postupně rozdělíme \(A\) na \(B_1,\ldots,B_k\), pak \(v(A)=\sum_{i=1}^kv(B_i)\).
Kdyby \(R\) šlo rozdělit na čtverce \(A_1,\ldots,A_k\) o stranách délek \(a_1,\ldots,a_k\), tak zjemníme rozdělení podél jejich stran na obdélníky \(B_1,\ldots,B_k\) a dostaneme spor:\[-1=f(1)f(x)=v(R)=\sum_{j=1}^lv(B_j)=\sum_{i=1}kv(A_i)=\sum_{i=1}^kf(a_i)^2\geq0\]