# zkouška 20.6.2008, Valtr

<{ForumPost(poster="Yawgmoth", timestamp=2008-06-20 16:16:49)}>
**Zadání:**  
1) Dokažte, že v každém vrcholově 2-souvislém grafu odlišném od C<sub>3</sub> existuje hrana, jejíž kontrakce neporuší vrcholovou 2-souvislost. Je pravda, že dokonce kontrakce libovolné hrany v takovém grafu neporuší 2-souvislost?  
  
2) Dokažte následující tvrzení: Pro každé přirozené číslo k existují přirozené číslo c a k-prvková množina M přirozených čísel takové, že pro každou dvojici a,b z M je číslo a + b + (a-b)<sup>12</sup> - c dělitelné 333.  
  
3) Urcete vytvorujici funkci pro posloupnost (1,-4,9,-16,25,-36,...).  
  
4) Definujte tok. Definujte celočíselný tok. Zformulujte a dokažte větu o celočíselnosti.  
  
_____________________________________  
  
**Můj názor + možné řešení:**  
nebylo důležité mít to dokonale, žádná velká technická znalost, stačilo upatlat vlastní slovní řešení...   
  
1) a) podle ušatého lemmatu, ať už podle kterékoliv verze s tím, že buď kontrahujeme hranu na posledním přidaném uchu které má délku alespoň 2 (pokud takové neexistuje tak původní kružnice  musela být větší než C<sub>3</sub> a můžeme kontrahovat na ní), nebo v druhé verzi kontrahujeme libovolnou hranu vzniklou podrozdělením (tady je potřeba ukázat, že kontrakcí se nic nestane, že maximálně zanikne nějaká hrana přidaná podle ušatého lemma později -> i bez ní je graf 2-souvislý)  
b) to pravda není, například čtverec (C<sub>4</sub>) s jednou úhlopříčkou, kontrakcí úhlopříčky vznikne cesta délky 3, která není 2-souvislá  
  
2) oficiálně to bylo myšlené na Ramseyovu vícebarevnou větu (že to má být nějaká Ramseyova věta nám po cca 40 minutách bylo napovězeno) a to tak, že vrcholy K<sub>n</sub> jsou přirozená čísla 1..n, hrany obarvíme 333 barvami tak, že barva hrany ab odpovídá (a + b + (a-b)<sup>12</sup>) mod 333. Z ramseyovy věty tedy existuje k-prvková jednobarevná množina, tu vezmeme a podle čísla barvy dopočítáme c.  
  
Já jsem to takhle ale neřešil a alternativní řešení (které šlo odhadnout stylem kouknu a vidím) mi bylo uznáno za plný počet bodů:  
M = {x|x = 333i, i přirozené, i<=k}, tj k-prvková množina násobků 333  
c = 333, tj konstantní pro všechna k  
a + b + (a-b)<sup>12</sup> - c se tedy dá přepsat na 333m + 333n + (333m-333n)<sup>12</sup> - 333 = 333(m+n-1+333<sup>11</sup>(m-n)<sup>12</sup>) ... m-n je celé číslo, na sudou mocninu přirozené, celá závorka je tedy také přirozená a po vynásobení 333 tedy dělitelná 333 :)  
  
3)   
(1,1,...) ~ 1/(1-x)  
(0,1,2,3,...) ~ x/(1-x)<sup>2</sup> ... zderivováno + posunouto  
(1,4,9,16,...) ~ (3-x)/(1-x)<sup>3</sup> ... zderivováno podruhé  
(1,-4,9,-16,...) ~ (3+x)/(1+x)<sup>3</sup> ... substituce -x za x  
  
4) tok f: E->R<sub>0</sub><sup>+</sup>, 1) pro každou hranu e f(e) <= c(e); 2) pro každý vrchol v mimo zdroj a stok je součet f(uv) přes všechny hrany uv  roven součtu f(vu) přes vechny hrany vu  
celočíselný tok: f: E->N<sub>0</sub> + stejné podmínky  
  
u věty jsem trošku vařil, ani jsem si nebyl jist zněním natož důkazem, ale uznáno bylo :-)  
Pokud všechny kapacity celočíselné, pak existuje celočíselný maximální tok.  
Dokážeme pomocí Ford-Fulkersonova algoritmu pro hledání maximálního toku, kde v tomto případě každá nalezená zlepšující cesta je celočíselná => zlepšující tok a zbytková kapacita taky. Navíc díky tomu algoritmus určitě doběhne, protože celková kapacita všech hran je konečná a každým krokem zlepšíme tok alespoň o 1.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-05-28 17:06:08)}>
Nemela by ta 3 byt takhle ?  
  
3)  
(1,1,...) ~ 1/(1-x)  
(0,1,2,3,...) ~ x/(1-x)2 ... zderivováno + posunouto  
(1,4,9,16,...) ~ (1+x)/(1-x)3 ... zderivováno podruhé  //zde bylo (3-x)/(+-x)3  
(1,-4,9,-16,...) ~ (1-x)/(1+x)3 ... substituce -x za x  
  
Teda jestli uz nejse blbej a neumim derivovat.
<{/ForumPost}>

<{ForumPost(poster="Jindra", timestamp=2009-05-28 19:43:44)}>
Souhlasím s návštěvníkem, má to být (1-x) / (1+x)^3... :-)
<{/ForumPost}>

<{ForumPost(poster="R.U.R.", timestamp=2009-06-01 02:19:48)}>
JJ, tohle se dá docela jednoduše ověřit v Mathematice - například

    Series[(1 - x)/(1 + x)^3, {x, 0, 10}]

hodí prvních deset členů toho mnohočlenu, který odpovídá té posloupnosti...
<{/ForumPost}>

<{ForumPost(poster="Lukas Mach", timestamp=2009-06-03 16:22:54)}>

 > R.U.R. wrote:JJ, tohle se dá docela jednoduše ověřit v Mathematice - například
 > 
 > 
 > 
 > 
 >     Series[(1 - x)/(1 + x)^3, {x, 0, 10}]
 > 
 > 
 > 
 > hodí prvních deset členů toho mnohočlenu, který odpovídá té posloupnosti...

Vzhledem k tomu, ze Mathematica neni ve vsech labech, tak bych jen doplnil odkaz na WA (viz "series expansion"):   
  
[http://www44.wolframalpha.com/input/?i= ... 1+%2B+x)^3](http://www44.wolframalpha.com/input/?i=%281+-+x%29%2F%281+%2B+x%29%5E3)  
  
Popripade si clovek muze nainstalovat Sage (myslim, ze balicek sagemath v Debianu).
<{/ForumPost}>