zkouška 20.6.2008, Valtr

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

zkouška 20.6.2008, Valtr

Příspěvek od Yawgmoth »

Zadání:
1) Dokažte, že v každém vrcholově 2-souvislém grafu odlišném od C3 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ž C3 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 (C4) 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 Kn 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+33311(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->R0+, 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->N0 + 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.
Návštěvník

Re: zkouška 20.6.2008, Valtr

Příspěvek od Návštěvník »

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.
Jindra

Re: zkouška 20.6.2008, Valtr

Příspěvek od Jindra »

Souhlasím s návštěvníkem, má to být (1-x) / (1+x)^3... :-)
Uživatelský avatar
R.U.R.
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 25. 5. 2008 18:46
Typ studia: Informatika Ph.D.
Bydliště: Beroun
Kontaktovat uživatele:

Re: zkouška 20.6.2008, Valtr

Příspěvek od R.U.R. »

JJ, tohle se dá docela jednoduše ověřit v Mathematice - například

Kód: Vybrat vše

Series[(1 - x)/(1 + x)^3, {x, 0, 10}]
hodí prvních deset členů toho mnohočlenu, který odpovídá té posloupnosti...
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Re: zkouška 20.6.2008, Valtr

Příspěvek od Lukas Mach »

R.U.R. píše:JJ, tohle se dá docela jednoduše ověřit v Mathematice - například

Kód: Vybrat vše

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

Popripade si clovek muze nainstalovat Sage (myslim, ze balicek sagemath v Debianu).
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“