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.

Skuska 5.6.2008

Příspěvekod rb » 5. 6. 2008 15:57

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

Doplněk od posledního

Příspěvekod Petr2 » 5. 6. 2008 17:04

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í!
Petr2
 

Re: Skuska 5.6.2008

Příspěvekod Him » 31. 5. 2009 15:33

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 ;)
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ěvekod beny » 31. 5. 2009 17:29

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.
beny
Matfyz(ák|ačka) level I
 
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.
Login do SIS: benat7am

Re: Skuska 5.6.2008

Příspěvekod Him » 31. 5. 2009 17:41

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ěvekod Him » 31. 5. 2009 17:46

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 ;)
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ěvekod beny » 31. 5. 2009 17:53

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.
Login do SIS: benat7am

Re: Skuska 5.6.2008

Příspěvekod beny » 31. 5. 2009 18:30

Him: Mimochodem nevim ani ulohu 5, takze kdybys vedel a chtel naznacit, budu vdecny;-)
beny
Matfyz(ák|ačka) level I
 
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.
Login do SIS: benat7am

Re: Skuska 5.6.2008

Příspěvekod Him » 31. 5. 2009 18:43

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 ;)
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ěvekod beny » 31. 5. 2009 20:15

Him: Diky!;-)
beny
Matfyz(ák|ačka) level I
 
Příspěvky: 14
Registrován: 31. 1. 2008 12:51
Typ studia: Informatika Bc.
Login do SIS: benat7am

Re: Skuska 5.6.2008

Příspěvekod dobry_den » 31. 5. 2009 20:32

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...
dobry_den
Matfyz(ák|ačka) level I
 
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Bydliště: Praha
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvekod Him » 31. 5. 2009 20:36

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 ;)
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ěvekod dobry_den » 31. 5. 2009 20:38

No.. Mam nejmensi hranovy rez A. A pri odebrani jedne hrany se mi pocet komponent zvysi maximalne o jednicku...Teda doufam:)
dobry_den
Matfyz(ák|ačka) level I
 
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Bydliště: Praha
Typ studia: Informatika Bc.

Re: Skuska 5.6.2008

Příspěvekod Him » 31. 5. 2009 20:41

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 Him dne 31. 5. 2009 20:42, celkově upraveno 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 ;)
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ěvekod dobry_den » 31. 5. 2009 20:42

V pohode. Ze by to bylo i v prednasce, o tom nevim, je to spis takova intuice..
dobry_den
Matfyz(ák|ačka) level I
 
Příspěvky: 25
Registrován: 3. 2. 2008 14:36
Bydliště: Praha
Typ studia: Informatika Bc.

Další

Zpět na DMI011 Kombinatorika a grafy I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron