Zadání:
1) Dokažte, že v každém vrcholově 2-souvislém grafu odlišném od C
3 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)
12 - 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
3 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
4) 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
n jsou přirozená čísla 1..n, hrany obarvíme 333 barvami tak, že barva hrany ab odpovídá (a + b + (a-b)
12) 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)
12 - c se tedy dá přepsat na 333m + 333n + (333m-333n)
12 - 333 = 333(m+n-1+333
11(m-n)
12) ... 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)
2 ... zderivováno + posunouto
(1,4,9,16,...) ~ (3-x)/(1-x)
3 ... zderivováno podruhé
(1,-4,9,-16,...) ~ (3+x)/(1+x)
3 ... substituce -x za x
4) tok f: E->R
0+, 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
0 + 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.