[zk] 26.5.
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
[zk] 26.5.
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.
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.
- Isidor
- Adoptoval Tutcheka
- Příspěvky: 247
- Registrován: 8. 12. 2004 23:22
- Typ studia: Informatika Mgr.
- Bydliště: mám
- Kontaktovat uživatele:
Ja len dodam, ze bodovanie bolo - podla vsetkeho - rovnomerne (za kazdy priklad 8 bodov) , 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.
-
- Matfyz(ák|ačka) level III
- Příspěvky: 103
- Registrován: 4. 6. 2005 15:49
- Typ studia: Informatika Bc.
- Bydliště: Vyšehrad
nekteri prezili
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...
- anzo
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 25. 9. 2004 21:10
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: nekteri prezili
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...
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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í.
- laliebijard
- Matfyz(ák|ačka) level III
- Příspěvky: 168
- Registrován: 8. 6. 2005 10:26
- Typ studia: Informatika Mgr.
- Login do SIS: repij4am
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: [zk] 26.5.
Nevite nekdo, jak by se dokazalo tohle?Tuetschek píše: 4) dokazte, ze kazdy n-regularni graf na 2n vrcholech je hranove n-souvisly
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Re: [zk] 26.5.
Uz si to moc nepamatuju, vim ze jsem to tehdy dokazal ...twoflower píše:Nevite nekdo, jak by se dokazalo tohle?Tuetschek píše: 4) dokazte, ze kazdy n-regularni graf na 2n vrcholech je hranove n-souvisly
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.
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: [zk] 26.5.
2Tuetschek: Diky, zkusim vykoumat, jak to dokoncit
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?Tuetschek píše:4) a) dokazte, ze v kazdem vrcholove 2-souvislem grafu o >= 4 vrcholech existuje hrana, jejiz kontrakce zachova vrcholovou 2-souvislost