Skuska 5.6.2008

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
rb
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 8. 11. 2006 20:20
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Skuska 5.6.2008

Příspěvek od rb »

Tak dnesne menu:

1. priklad:
Urcit najvacsie parovanie v bipartitnom grafe.
2. priklad:
Funkciu (1-2x)^1/3 vyjadrime ako radu Sum_n=1^infinity a_n*x^n.
a) a_0 je prvy kladny koeficient, ktory je druhy?
b) a_0 je cele cislo, ktory dalsi koeficient je cely?
3. priklad:
Urcit dimenziu priestoru cyklov (priestoru Eulerovskych podgrafov) grafu + popisat nejaku bazu toho priestoru.
4. priklad:
Doplnit tabulku na latinsky stvorec, alebo dokazat, ze sa to neda:

Kód: Vybrat vše

+-----------+
|1|2|3|4|5|6|
+-----------+
| | | | | | |
+-----------+
|6|3|5|1|2|4|
+-----------+
| | | | | | |
+-----------+
| | | | | | |
+-----------+
|2|1|6|5|4|3|
+-----------+
5. priklad:
Dokazte, ze kazdy graf o n vrcholoch s maximalnym stupnov d ma najviac (2d)^n kostier.

6. priklad:
Nech G=(A zjedn. B, E) je suvisly bipartitny graf taky, ze kazdy vrchol v partite A ma stupen aspon k-krat vacsi nez lubovolny vrchol z partity B. Dokazte, ze vrcholy grafu G sa daju pokryt disjunktnymi hviezdami, z nich kazda ma aspon k+1 vrcholov. (Hviezda o k+1 vrcholoch je uplny bipartitny graf K_{1,k}.

7. priklad:
Dokazte, ze kazdy n-regularny graf na 2n-vrcholoch je hranovo n-suvisly.

Moj comment:
Mne osobne tie priklady neprisli velmi jednoduche. Nastastie p. Kratochvil dal kazdemu sancu na ustnu (ja som mal 14 bodov a tiez som siel na ustnu, nakoniec som to spravil na 3). Od 17 bodov uz bola trojka bez ustnej, okolo 22 (mozno viac) boli dvojky. Ale myslim, ze toto bol jeho posledny termin, dalsie uz budu s p. Valtrom. Vela stastie pri kombagre tym, co to este nemaju...
The secret to creativity is knowing how to hide your sources. (A. Einstein)
Petr2

Doplněk od posledního

Příspěvek od Petr2 »

Vážení!
Já bych jen doplnil kolegu ze zkoušky byl jsem poslední a tak můžu říct, že ze 21 lidí, co dnes byli zkoušeni : Jedna výborná, dvě nebo tři velmi dobré, ostatní dobré. Jen jeden polák nepřišel na ústní a jednoho vyhodil. To vyhození bylo dost drsné. Prof. Kratochvíl mu nabídl tři další věty k dokázání a pak řekl, že to nemá smysl. V sumě tedy k - souvislost, Ramseyovka, důkaz počtu koster přes determ., a ještě něco.
Nejnižší bodový zisk 9 bodů ze 40 :!: a dostal za tři po jednom dobře zvládnutém důkazu. Obecně ústní dozkoušení probíhá tak, že se prof. ptá třeba kdo zná Hallovu větu. Jak se někdo přizná, tak hned ať ji dokáže a takto u nás rozhodil každému dvě věty. Na trojku stačí obvykle jedna zcela. Na dvojku musíte mít velmi dobrý přehled a lepší na ústní dnes nedal. Dlužno podotknout, že tam byli jen lidé s 16 a méně body.
Památná věta prof. : "My s doc. Valtrem nelpíme na tom abyste znali všechny důkazy, ale něco znát prostě musíte. :) "
Oblíbená věta - Hallova. Dokazovala se dnes dvakrát :wink: .
Pro Vás, kteří jdete na zkoušku hodně štěstí!
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

ten 7. priklad by asi mel byt pro n >= 2, jinak to jde rychle vyvratit n = 1.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od beny »

No s tim vyvracenim bych si nebyl tak jisty :wink: , existuje jediny 1-regularni graf na dvou vrcholech a ten je hranove 1-souvisly, nebot jakmile odeberes jedinou hranu, prestane byt souvisly.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

nj, tak to dopada, kdyz uz clovek micha vrcholovou a hranovou souvislost :)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

Beny: vis, jak dokazat ten 7. priklad? mne se to stale nedari
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od beny »

Him: Mne zatim taky ne..
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od beny »

Him: Mimochodem nevim ani ulohu 5, takze kdybys vedel a chtel naznacit, budu vdecny;-)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

Beny: podle mych odhadu je to dokonce volnejsi nez 2^(|E(G)|), takze to plati.

Preklad toho vzorce je, ze u kazdeho vrcholu mam d moznosti, jestli tam dam okolni hrany - coz je dost overkill.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
beny
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od beny »

Him: Diky!;-)
dobry_den
Matfyz(ák|ačka) level I
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Skuska 5.6.2008

Příspěvek od dobry_den »

Jinak k te sedmicce - ja myslim, ze by se na to mohlo jit sporem. Necht existuje A podmozina E(G) takova, ze |A| < n a G(V, E-A) je nesouvisly. Mejme takovou A nejmensi. Potom se graf rozdeli do dvou komponent souvislosti o (n-k) a (n+k) vrcholech. Potom celkovy soucet stupnu v (n-k) komponente by mel byt (n-k)*n - |A| = n^2 - nk - |A|. To ovsem neni mozne - uvazme graf K_(n-k), tedy uplny graf na (n-k) vrcholech. V nem je soucet stupnu (n-k)(n-k-1) = (n^2 - nk) - (n+k(n-k-1)) < (n^2 - nk) - |A|...

Kdyztak komentujte, je to takovy trochu divny...
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

Dobry_den: Jenom otazka, jak vis, ze se to rozpadne jen na dve komponenty?
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
dobry_den
Matfyz(ák|ačka) level I
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Skuska 5.6.2008

Příspěvek od dobry_den »

No.. Mam nejmensi hranovy rez A. A pri odebrani jedne hrany se mi pocet komponent zvysi maximalne o jednicku...Teda doufam:)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvek od Him »

jo, sorry, to je vlastne i v prednaskach.. me uz to dneska nemysli.. radsi koncim

edit: i kdyz, ty ale odebiras vic jak jednu hranu..
Naposledy upravil(a) Him dne 31. 5. 2009 21:42, celkem upraveno 1 x.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
dobry_den
Matfyz(ák|ačka) level I
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Typ studia: Informatika Bc.
Bydliště: Praha

Re: Skuska 5.6.2008

Příspěvek od dobry_den »

V pohode. Ze by to bylo i v prednasce, o tom nevim, je to spis takova intuice..
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“