Skuska 5.6.2008

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:

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

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

ten 7. priklad by asi mel byt pro n >= 2, jinak to jde rychle vyvratit n = 1.

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.

nj, tak to dopada, kdyz uz clovek micha vrcholovou a hranovou souvislost :)

Beny: vis, jak dokazat ten 7. priklad? mne se to stale nedari

Him: Mne zatim taky ne..

Him: Mimochodem nevim ani ulohu 5, takze kdybys vedel a chtel naznacit, budu vdecny;-)

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.

Him: Diky!;-)

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: Jenom otazka, jak vis, ze se to rozpadne jen na dve komponenty?

No.. Mam nejmensi hranovy rez A. A pri odebrani jedne hrany se mi pocet komponent zvysi maximalne o jednicku...Teda doufam:)

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

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

dobry_den: posledni otazka, ty ale neodebiras jednu hranu, ale potencialne vic.. nebo mi neco jeste unika?

no to jo, ale diky te podmince, ze to je minimalni rez, skoncim okamzite, jakmile se to rozpedne na dve komponenty. a vsechny hrany, ktere jsem odebral, musely byt mezi temito dvema komponentami - jinak by to nebyl minimalni hranovy rez..