[zk] 6.6.2006 9:00 sk. A

Zde je sk. A

Attachments:

• zk060606A.jpg

A1)
(1-3x)^(1/2) = SUMA[n=0..inf]( 1/2 nad n )(-3)^nx^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.