[zk] 26.5.

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.

[zk] 26.5.

Příspěvekod Tuetschek » 26. 5. 2006 10:00

Cau, takze zadani:

1) vytvorujici funkce pro (1,0,3,2,5,4,7,6.... )

2) 1 =< a < b =< n jsou prir. cisla, X mnozina mohutnosti n.
dan graf G_{a,b,n} = ( ( X nad a ) sjednoceno s ( X nad b )), { AB : A subset B subset X, |A| = a, |B| = b } ). pro ktera a,b v zavislosti na n ma G_{a,b,n} parovani velikosti ( n nad a )?

3) dokazte, ze ve vrcholove 2-souvislem grafu lezi kazde 2 vrcholy na kruznici

4) dokazte, ze kazdy n-regularni graf na 2n vrcholech je hranove n-souvisly

-------------

1) vytvorujici funkce pro (1,-2,3,-4,5,-6... )

2) dokazte: pro kazda 2 k, n prirozena existuje N prirozene s nasl. vlastnosti. pokud pro lib. mnozinu M obs. N bodu v rovine plati, ze spojnice dvojic bodu z M jsou rovnobezne s (max.) k smery, pak >= n bodu z M lezi na 1 primce.

3) dokazte z kazdy k-regularni bipartitni graf je disj. sjednocenim k perfektnich parovani.

4) a) dokazte, ze v kazdem vrcholove 2-souvislem grafu o >= 4 vrcholech existuje hrana, jejiz kontrakce zachova vrcholovou 2-souvislost
b) rozhodnete, zda v kazdem vrcholove 2-souvislem grafu o aspon 4 vrcholelech zachova kontrakce libovolne hrany vrcholovou 2-souvislost.

------

uff... vysledky a ustni budou nekdy po poledni.
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
 
Příspěvky: 656
Registrován: 15. 6. 2005 12:54
Typ studia: Informatika Mgr.

Příspěvekod Isidor » 26. 5. 2006 13:37

Ja len dodam, ze bodovanie bolo - podla vsetkeho - rovnomerne (za kazdy priklad 8 bodov) :shock:, 2 ludi poslal rovno domov (s tym ale, ze (pred)termin im nezapocita), okolo 13-15 bodov bolo "pozvanie" na ustnu cast, nad 15 uz normalna stupnica, ktoru si nepamatam :)
Inteligentních lidí je menšina. Demokracie je vláda většiny.
Uživatelský avatar
Isidor
Adoptoval Tutcheka
Adoptoval Tutcheka
 
Příspěvky: 247
Registrován: 8. 12. 2004 23:22
Bydliště: mám
Typ studia: Informatika Mgr.

nekteri prezili

Příspěvekod qwertie » 26. 5. 2006 15:50

jsem jeden z poslanych domu, nakonec jsem to vytahl na 3 (neskontroloval jsem si vytvorujici fci a ona byla takova vyzbrklena..) tak mne zkousel a nakonec uznal ze na 3 mam.. Ale pri zkouseni jsem tam byl s divkou ktere tu 3 nedal...
qwertie
Matfyz(ák|ačka) level III
 
Příspěvky: 103
Registrován: 4. 6. 2005 14:49
Bydliště: Vyšehrad

Re: nekteri prezili

Příspěvekod anzo » 26. 5. 2006 16:40

Odchazel jsem jako posledni a pokud vim, tak i ten druhy, co nemel dost bodu, to dal. Takze tenhle termin dali vsichni az na jednu dusi. Pokud ne, omlouvam se za falesne nadeje.


qwertie píše:jsem jeden z poslanych domu, nakonec jsem to vytahl na 3 (neskontroloval jsem si vytvorujici fci a ona byla takova vyzbrklena..) tak mne zkousel a nakonec uznal ze na 3 mam.. Ale pri zkouseni jsem tam byl s divkou ktere tu 3 nedal...
Uživatelský avatar
anzo
Matfyz(ák|ačka) level I
 
Příspěvky: 2
Registrován: 25. 9. 2004 20:10
Typ studia: Informatika Bc.

Příspěvekod jaruch » 26. 5. 2006 17:25

A na co sa pytal na ustnej? Rozobera pisomku, ci dostanete dokazat vetu z prednasky, alebo ako?
Shit shit, who the fuck is shooting us?
I've got a universe to master...
Uživatelský avatar
jaruch
Supermatfyz(ák|ačka)
 
Příspěvky: 380
Registrován: 5. 2. 2005 14:06
Typ studia: Informatika Mgr.

Příspěvekod Eubie » 26. 5. 2006 18:05

Já potřeboval dva body abych měl trojku a dostal jsem Ramseyovy věty, kuratowského, Hallovu, existenci párování v bip. grafu. Měl sem vše správně až na jedno slovo v druhý Ramseyovce. Po zadání vět jsem mu předem řekl, že znění umim v pohodě, ale neumim ani důkaz (takže pokud to nemá cenu, tak ať neplýtvam jeho, svým ani nikoho jiného časem) a vzal to v pohodě. Nakonec sem mu to tam všechno řekl, on viděl, že těm zněním rozumim a trojka byla na světě. Ale nevim, ostatní tam dost mučil s důkazy, tak jsem měl asi štěstí.
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
 
Příspěvky: 295
Registrován: 8. 10. 2005 14:35

Příspěvekod qwertie » 26. 5. 2006 23:24

ja mel FordFulkersonovu Vetu, pocitani binarnich stromu, kostry prez diskriminant... bojoval jsem o 3 a dobyl jsem ji, dukazy rikal ze pokud nebojujem o nejakou lepsi znamku - neni treba....
qwertie
Matfyz(ák|ačka) level III
 
Příspěvky: 103
Registrován: 4. 6. 2005 14:49
Bydliště: Vyšehrad

Příspěvekod Dawe » 28. 5. 2006 10:39

Ahoj lidi moh by někdo nějak objasnit řešení toho druhýho příkladu první skupiny? Nějak jsem to celkově moc nepochopil. A kdyby se chtělo, tak i některý ostatní příklady, i když ty bych asi snad nějak tak věděl...
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
 
Příspěvky: 360
Registrován: 12. 10. 2004 11:32
Bydliště: Doma a nebo na koleji
Typ studia: Informatika Mgr.

Příspěvekod Lada » 28. 5. 2006 18:55

ahoj, chapu to dobre, ze ustni zkouska je jenom pro ty co bojujou o 3 (nebo to maji mezi) a nebo ceka na kazdeho?
Hail to you, champion:o)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

Příspěvekod Dawe » 28. 5. 2006 20:09

Na každýho rozhodně ne, jen na toho kdo tam bude chtít jít o něco bojovat...
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
 
Příspěvky: 360
Registrován: 12. 10. 2004 11:32
Bydliště: Doma a nebo na koleji
Typ studia: Informatika Mgr.

Příspěvekod OjciPojci » 29. 5. 2006 11:40

qwertie píše:... kostry prez diskriminant...


:lol:

....a ja som si furt myslel ze sa to rata cez determinant .....
kona zapriahame hlavou v smere jazdy
Uživatelský avatar
OjciPojci
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 15. 5. 2006 15:02

Příspěvekod laliebijard » 1. 6. 2006 16:00

Nespomenuli by ste si niekto, kolko bodov treba na trojku a na dvojku? (a na jednotku:)
"posteľ sa rozbieha po koľajniciach z modrého medu"

Breton
Uživatelský avatar
laliebijard
Matfyz(ák|ačka) level III
 
Příspěvky: 168
Registrován: 8. 6. 2005 09:26
Typ studia: Informatika Mgr.
Login do SIS: repij4am

Re: [zk] 26.5.

Příspěvekod twoflower » 17. 6. 2006 21:11

Tuetschek píše:
4) dokazte, ze kazdy n-regularni graf na 2n vrcholech je hranove n-souvisly


Nevite nekdo, jak by se dokazalo tohle?
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
 
Příspěvky: 445
Registrován: 22. 9. 2004 20:07
Typ studia: Informatika Ph.D.

Re: [zk] 26.5.

Příspěvekod Tuetschek » 17. 6. 2006 21:32

twoflower píše:
Tuetschek píše:
4) dokazte, ze kazdy n-regularni graf na 2n vrcholech je hranove n-souvisly


Nevite nekdo, jak by se dokazalo tohle?


Uz si to moc nepamatuju, vim ze jsem to tehdy dokazal :D ...

Jde to sporem. Tj. predpokladam, ze existuje hranovy rez =< n - 1. Necht je to minimalni rez, a rozdeluje mnozinu vrcholu grafu na 2 komponenty.
Vezmu si tu mensi z nich (tj. mensi pocet vrcholu nez n, rekneme k) a dokazu, ze i pro nejhorsi pripad, kdy vznikla komponenta je uplny graf,
musely vest jeste nejake hrany pryc, a dostanu tak spor.
Vezmu si nerovnici, jednu stranu vezmu z predpokladu n-regularnosti, a toho ze rez je =< n-1; druhou z poctu hran v uplnem podgrafu.

k*n - (n-1) =< k * (k-1)

Vede to na nejakou kvadratickou rovnici, kde vyjde ze k =< 1 a pro k = 1 takovy rez udelat nejde...

Tak ted nevim, mozna ta rovnice je blbe, urcite to bylo takhle nejak sporem ale temi detaily si jisty uz moc nejsem ... jestli to nekdo vite lip tak me opravte :?
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
 
Příspěvky: 656
Registrován: 15. 6. 2005 12:54
Typ studia: Informatika Mgr.

Re: [zk] 26.5.

Příspěvekod twoflower » 18. 6. 2006 18:08

2Tuetschek: Diky, zkusim vykoumat, jak to dokoncit :)

Tuetschek píše:4) a) dokazte, ze v kazdem vrcholove 2-souvislem grafu o >= 4 vrcholech existuje hrana, jejiz kontrakce zachova vrcholovou 2-souvislost


A tohle nekdo nevite? Zkousel jsem to indukci podle poctu vrcholu, ale zrovna jsem si nasel hezky protipriklad, na kterem ten dukaz spadne :) Nedelalo se to nahodou nejak ve stylu, ze se mi ten graf rozpadne odebranim nejakeho vrcholu na dve komponenty, vezmu z nich tu max. a dovedu to ke sporu?
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
 
Příspěvky: 445
Registrován: 22. 9. 2004 20:07
Typ studia: Informatika Ph.D.

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