[zk] 5.6.2006

[zk] 5.6.2006

Attachments:

• kombagra.JPG

pls, premozte sa niekto a dajte sem aj riesenia, zvlast ten 2 a 4 priklad su nie zrovna zrejme. Riesenia vam vysvetloval pred vysledkami tak ich sem napiste.... a tiez by sa zisla druha varianta pisomky

vdaka

hydrant

Ten 4 příklad se řešil pomocí důkazu Tuteho věty. K muselo být liché (to je kvůli počtu vrcholů s lichým stupněm).
2 jsem neměl vůbec.
Šel jsem za ním, že mám jeden příklad špatně ohodnocenej (chyběl mi bod do dvojky). Tak jsem se o tom tak nějak bavily, pak se zeptal na Hamiltonovskou kružnici, co o ní vím a tak. Pak mi celkem spokojeně napsal 2 - teda snad, ještě jsem se nekoukal... :-)
Jinak říkal, že mu opravující říkaly, že byla písemka těžší než minule, takže bylo hodnocení asi takové:

1 - 32-25
2 - 24 - 17
3 - 16 - ?
zkoušení ?
4 - ?

Ten zbytek ať kdyžtak někdo doplní (myslím, že 8 bodů ještě bylo na ústní).
Skupina byla jen jedna ( alespoň z toho co ukazoval jak se to má řešit).

trojak 12-16
ustni 7-11

sem byl az dotad na ustnim a nakonec sem vymlatil trojku, coz s mym "formalnim" zapisem se skoro uspech, ale i z ustniho se da bojovat o dvojku a mozna i vyse

Tak jsem ted prisel domu z ustni, skoncil jsem asi v 18:40... nektery tam jeste mozna jsou... Dostal jsem: co vim o Hamiltonovskejch kruznicich, Pocet koster pres determinant, Hallovu vetu... Mel jsem 8 bodu z pisemny, napsal jsem mu to vsechno s def, lemmatama a dukazama tak nakonec za 2.

Co tam jeste padalo byl obchod. cestujici, edmondsuv zahradni alg, projektivni roviny s dukazem |P| = |P'|, dusledky hallovi vety ( to je to lemma pro bipart. graf a doplneni lat. obdelniku na ctverec). Jednu dusi se tam zeptal na pocet lat. ctvercu radu n... no vic si uz nak nevybavuju.

No koukam na ten 2. priklad. Mnozina B je vlastne prostor rezu grafu Kn.
Takze dim bude n-1.
Jen zatim netusim co presne by bylo bazi.

snail wrote:No koukam na ten 2. priklad. Mnozina B je vlastne prostor rezu grafu Kn.
Takze dim bude n-1.
Jen zatim netusim co presne by bylo bazi.

Bazou su nieco ako vsetky "hviezdy", to jest jedna partita ma velkost 1. Ak som to teda nepoplietol...

Posilam "navody" k prikladum. No, spis jsou to navrhy. Je to hodne nepresny, neco je asi uplne spatne, tak me kdyztak opravte. Ja mel 3 a jsem rad, ze mam kombinatoriku za sebou... 8)

1, -4, 9, -16, 25, -36
druha derivace, myslim posunout, pricist radu 1, 2, 3, ... a substituce -x za x

2. (z tohohle jsem mel 0 bodu, takze reseni moc nevim...)

a) Musi se dokazat, ze je uzavrene na nasobeni: trivialni (0, 1)
scitani: Scitani je XOR. Je treba dokazat, ze kdyz A a B jsou uplne bip. grafy a C = A + B tak C je take.
Je dobre nakreslit si obrazek. - Napred cele mnoziny vrcholu. Ta se rozdeli na dve casti. - Dve partity. Pri scitani se to cele rozdeli na 4 casti. Z toho, ze scitani je xor vyplyne, ze hrany vysledneho poscitaneho grafu pujdou jen pres sousedni ctvrtiny. Ne nijak jinak. Z toho se uvidi, ze vysledny graf C je uplny bipartijni

b) n-1
Bazi tvori grafy "hvezdice". - Jedna parita ma velikost 1, stupen vrcholu na ni je n-1. Je jich n, ale dve jsou linearne zavisle

c)
To nevim. Ale zajimave je, ze v GF(2) neplati, ze kdyz je E ortogonalni doplnek B, tak musi mit neprazdny prunik.
Ale delalo by se to nejak pomoci tech hvezdic...

d)
Hvezdice

3. a)
   Kdyz odendam Ham. kruznici, zbyde podgraf stupne 1. - Perf. parovani
   Nebo pomoci toho, ze kdyz je lichy stupen, musi byt sudy pocet vrcholu, takze Ham. kruznice je suda. - Ze sude vytvorit perf. parovani
   b)
   asi jako a) (mam perf. par => mam 1-faktor)
   c)
   Petersen, nebo treba dva K4... (to je uz hodne spatne, kdyz me nenapadlo ani tohle...)
   d) asi jako c)

4. Kdyby bylo k sude, je lichy pocet vrcholu (myslim). Tedy nemuze byt perf. par.
   K liche. Pomoci Tuttovy vety. Vime, ze pocet vrcholu je sudy. Kdyz vyberu nejaky vrcholovy rez (vrcholy po jejichz odebrani je graf nesouvisly) vime, ze z kazde liche komponenty musi jit aspon k cest do A. Dohromady kl. Z a vede |A|k cest. Ty musi vest do lichych komponent a i do sudych. Tedy:
   kl <= k|A| tedy
   k <= |A|

Snad jsem tim nikoho moc nezmatl. Jeste to radsi promyslete. Ja s kombinatorikou koncim. Definitivne. Jupi!!!! :D

Ke? Asi jsem ještě někde v labu zapomněl uložený heslo či co - někdo to sem dal pod mým jménem. No ať se stydí! :twisted:

2.c To uz neni tezke: plati, ze bipartitni grafy neobsahuji liche kruznice. Takze prunik libovolneho bipartitniho grafu s kruznici ma sudy pocet hran. Jinymi slovy, skalarni soucin vektoru prislusneho bip. grafu a kruznice je sude cislo, tedy 0. Z toho uz plyne ortogonalita.

gask: ja jsem to teda nebyl, ale jeden znamy povidal, ze to sem dal "pod nejakou kockou, ktera byla tady prihlasena, kdyz se nalogoval":))

Hugo wrote:gask: ja jsem to teda nebyl, ale jeden znamy povidal, ze to sem dal "pod nejakou kockou, ktera byla tady prihlasena, kdyz se nalogoval":))

Už se mi tu byl osobně omluvit. Prej jsem byl loglej pod explorerem, což je divný. Ale asi jsem ho někdy použil, zaškrtl políčko a zapomněl na něj...nu což. :twisted:

ty brdo, takove matfyzacke slusnosti...to ja bych se jen skodolibe pochechtaval..:)