Matfyz Wiki
Zadání:
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?
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.
Urcete vytvorujici funkci pro posloupnost (1,-4,9,-16,25,-36,...).
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í...
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á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 :)
(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 xtok 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.