# [zk] 6.6.2006 9:00 sk. A

<{ForumPost(poster="Kuba", timestamp=2006-06-06 12:14:38)}>
Zde je sk. A

*Attachments:*

- *[zk060606A.jpg](/Forum%20archiv/Attachments/zk060606a.jpg)*

<{/ForumPost}>

<{ForumPost(poster="Kuba", timestamp=2006-06-06 15:42:33)}>
**A1)**  
(1-3x)^(1/2) = SUMA\[n=0..inf]( 1/2 nad n )*(-3)^n*x^n (zobecněná binomická věta)  
a0 = 1  
a1 = -3/2  
a2 = -9/8  
a3 = -27/16  
a4 = -405/128  
atd.  
**a) žádný další kladný koeficient není**  
v (1/2 nad n) jsou záporné a2, a4, ...  
v (-3)^n jsou záporné a1,a3,...  
každý koeficient a1, a2... je záporný.  
**b) žádný další celý koeficient není**  
čitatel je vždy lichý  
*(3^n vždy liché, čitatelé u (1/2 nad n) liší - násobením vznikne liché)*  
jmenovatel vždy sudý  
*(vždy ho někde násobím 2 - faktoriál z (1/2 nad n),čitatel z (1/2 nad n) jsou (1/2)^n)*  
takže nikdy nevznikne celé číslo.  
  
**A2)**  
1) Vytvořit nějaké největší párování není problém, např. horní vrcholy *v*, spodní *u*, očíslovat zleva do prava, pak je jedno takové párování třeba *(v7u7,v8u6,v6u4,v5u5,v4u3,v2u2,v1u1)*  
2) Dokázat, že je největší - uspokojuje celou jednu partitu, takže v bipart. grafu být větší nemůže (nebo nějak přes Hallovu větu, nebo přes Edmondsův les + algoritmus)  
  
**A3)**  
**Obě tvrzezní platí, b) => a).  
b) G** je k-souvislý => má alespoň k+1 vrcholů a odebráním max k-1 vrcholů zůstane souvislý.  
Aby byl **G+v** souvislý, musí platit, že odebráním max k-1 vrcholů se neporuší souvislost.  
Pokud je mezi odebíranými vrcholy **v**, v původním grafu **G** již odeberu pouze k-2 vrcholů a souvislost se neporuší.  
Pokud mezi odebíranými vrcholy **v** není, nejhorší případ by byl, kdybych odebral k-1 vrcholů, přes které je **v** připojen. V tomto případě je původní **G** stále souvislý *(předpoklad)* a zbývá 1 hrana, přes kterou je připojen **v**, takže se souvislost opět neporuší.  
Tvrzení platí pro k, tedy i pro k = 2.  
  
**A4)** - náznak, tento příklad jsem neměl, tak jen zběžně jak to říkal před výsledky  
a) viz. důkaz Shurova lemmatu  
b) viz. a) a když se něco opakuje, tak vzít součet (a=b, vzít a, a+b), pokud se opakují všechny 3, vzít a, 2a, 3a.
<{/ForumPost}>