Ahojte, takze mam za sebou skusku z grafov. Po 5-hodinovom cakani na uja Skovieru sme zacali po 13-tej hodine, pretoze mu vykradli pivnicu a policajti ho nechceli pustit... Moje otazky boli: 1. Toky v sietach 2. Mengerova teorema 3. Dokazte, ze strom ma najviac jeden 1-faktor. Chcel co najdetajlnejsie dokazy na papier, "aby som si to mohol iba prebehnut a skontrolovat to". U mna sa opytal na dve trivialne veci k dokazu Mengerovej teoremy, ostatne si iba pozrel. Takze moja konverzacia s nim trvala asi 20 sekund. Tym, ktori sa uz neukazu pred sviatkami v skole prajem vesele etc. ----------------------------------------------------- Takze moje priklady boli: 1. Bipartitne parenia 2. Veta o zafarbeni planarneho grafu 5 farbami 3. Ak mame 2-suvisly graf, tak dokazte, ze bod a hrana, ktora neobsahuje dany bod, lezia na kruznici. ----------------------------------------------------- 1. Eulerov Polyedralny vzorec a jeho dosledky 2. Brooks 3. G je K regularny graf a neparnym poctom vrcholov N.Potom Chi'(G)=1. Priklad som nevedel vyriesit a tak som skoncil za 2. ----------------------------------------------------- Nazdar, 1. Mengerova veta 2. Nikde nulove toky na grafoch (malo to nejaku suvislost s k-tokmi) 3. Dokazat, ze strom ma najviac jeden 1-faktor. do druheho som ani nezatal, ostatne (1 a 3) som vyriesil trochu s problemami a dostal som trojku. ----------------------------------------------------- 1. chvatalova teorema o ham. grafoch 2. priestory cyklov 3. dokazte ze ziaden vrcholovy rez v k-kritickom grafe neindukuje kompletny podgraf. ( k-kriticky graf je graf s chrom. cislom k pri ktorom pri odobrati lub. vrchola znizime chrom. cislo a vrcholovy rez je mnozina vrcholov po ktorej odobrati sa graf rozpadne na komponenty ) ----------------------------------------------------- 1. Kuratowski Graf je planarny <=> ak neosahuje ako podgraf subdiviziu K5 ani K33 2. Ko"nig o pareni # hran v max pareni = # vrcholov v min pokryti 3. rad(G) <= diam(G <= 2*rad(G) 1. som mal intuitivne 2. komplet, ale nevedel som pouzitie ani suvislosti 3. poslabsie, ale spravne ----------------------------------------------------- Hi,... Uvidom nieco o tom ako to bezi. Ak niekto potrebuje odpisovat tak nech ide ako p rvy, vyzera ze skoviera si chodi pre postu t.j. asi tak 1/2 hod nie je v kanclik u, ale nezarucujem. Bomby sa daju pouzivat bez problemov, mna sa na dobre sprave ny dokaz ani ne Co som dostal: 1. Farbenie hran - napisal som Koniga s dokazom a chcel este znenie Viziga 2. Ford-Fulk. veta + dokaz (Mal som) 3. Nech G je graf v ktorom je hamiltonovska kruznica a S ja vlastna neprazdna po dmnozina V(G), tak c(G-S)<=|S|+1. Kde to c je pocet komponentov grafu. V poznamkach je jedna velmi podobna v4eta, dokaz sa robi rovnako az na to ze to +1 potrebujeme v baze indukcie. Toto som vedel na 80% dostal som dvojku. Inac skoviera je fakt celkom mily, t.j nerype velmi, skoro vo bec, mne dal len jednu otazku k vizingovi ze kolkymi fabami mozeme zafarbit kubi cky graf. A to priamo vypliva z viziga Keso ----------------------------------------------------- 1. Vizing 2. Toky v grupach 3. jednoznacne hranovo 3 zafarbitelny graf je hamiltonovsky (hrany jednej farby tvoria 1-faktor, druhej farby tiez, ked tieto dva 1-faktory spojim, dostanem 2-faktor, t.j. vsetky stupne parne, bud je to kruznica (potom je hamiltonovska), alebo je to system disj.kruznic, tam jednu prefarbim a dalej z def. jednoznacnosti , ktoru dostanete, sa to dotiahne ) kacena... ----------------------------------------------------- Caute vsetci, co ste este nemali grafy! Moje otazky boli 1. Hamiltonovske grafy 2. Farbenia planarnych grafov + Heawood 3. Ak je graf hamiltonovsky alebo eulerovsky, potom jeho hranovy graf je hamiltonovsky. ----------------------------------------------------- caute! 1. Eulerov polyedralny vzorec 2. Brooks cize klasika a treti priklad: 3. Ak G je d-regularny graf neparneho radu (pocet vrcholov G je neparny), potom sa da hranovo zafarbit len d + 1 farbami ( chi'(G) = d + 1 ). Dokaz: (je lahky) ======== najprv (podla Vizinga) pre G plati: d <= chi'(G) <= d + 1 indukcia na d : d-regularny graf == kazdy vrchol ma stupen d 1) baza: d = 2 kruznica, ma neparny pocet vrcholov => ma aj neparny pocet hran => treba aspon 3 farby. 2) d > 2 sporom (ako inac): majme d-regularny graf, a majme jeho farbenie hran d farbami. (*) vyberme si lubovolnu farbu f a z grafu G odstranime vsetky hrany takejto farby. pretoze kazdy vrchol ma stupen d, a mame d farieb hran, musi z neho viest aj hrana farby f. teda vykonanim (*) znizime stupen kazdeho vrchola o 1 => ziskame (d-1)-regularny graf G1; na tento graf G1 zase aplikujeme (*), atd. takto ziskame konecnu postupnost grafov: G ---> G1 ---> G2 ---> ... ---> Gn | | | | d-reg (d-1)-reg (d-2)-reg ... 2-reg. ale takymto sposobom sme ziskali 2-regularny graf Gn s ofarbenim hran 2 farbami, ale to je SPOR s 1), teda ani farbenie hran grafu G s d farbami nemoze existovat. ...snad to nekomu pomoze... c u +++ PeTeR +++ ----------------------------------------------------- 1. tutt. o 1-faktore 2. celocis. toky, toky na grupach, k-toky 3. priklad z cvik: dokazte, ze lubov. (vrchol.) rez k-kritic. grafu neindukuje kompletny podgraf Mat ----------------------------------------------------- Nazdarte, moje otazky: 1.Menger + na konci sa ma este spytal na dosledok pre 2 vrcholy 2. z planarnych grafov - stereograficka projekcia + pouzitie - dualne grafy + pouzitie 3.Dokazat: Pre kazdy strom T plati, ze Rad(T)='Diam(G)/2' ('x' - horna cela cast x) M&P ----------------------------------------------------- Caute vsetci. Tu su moje priklady z Teorie Grafov. 1. Toky v sietach. 2. Petersenova veta (Kazdy kubicky graf bez mostov ma 1 faktor) 3. Blokovy graf= B grafu G je strom. G 1. som mal, nemal som len dokaz Ford-Fulkersona. 2 Vsetko az na dokaz pomocnej Lemmy. 3 Lahky, mal som Vysledok skusky=3 Vela stastia. ----------------------------------------------------- 1. Kuratowski 2. Existencia 1-faktorov, 2-f. a faktorizacii v reg. grafoch 3. chromaticky index v kompletnych grafoch (rada- zratajte K_{2k+1} a podla toho K_2k) ----------------------------------------------------- 1. Brooksova veta 2. Eulerova veta o planarnych grafoch + dosledky 3. Dokazat ze kazdy suvisly graf sa da rozdelit aspon na 2 dominantne podgrafy. ----------------------------------------------------- moje otazky : 1.Farbenie planarnych grafov 2. toky na grupach a k-toky 3. Dokazte, ze kazdy uzavrety neparny sled obashuje kruznicu neparnej dlzky ... 3. dokazuje sa to indukciou ----------------------------------------------------- 1. 1-faktor 2-faktor 2. farbenie planarnych 3. kubicky graf, existuje kostra T, ze G-E(T) je acyklicky mam to za dva, farbenie som si velmi necital, bol som tam asi 15-20 minut pozdravuje pepe ----------------------------------------------------- Nazdar spolubojovnici! Toto uz pre moc ludi aktualne nebude, ale snad aspon pre niekoho... 1) Parenie v bipartitnych grafoch 2) Ford-Fulkerson aj algoritmus 3) Ak G neobsahuje kruznicu parnej dlzky potom jeho bloku su tvaru K1, K2 alebo kruznica neparnej dlzky, teda C(2k+1) Skovieru som uplne odrovnal tym, ze som zapisal vyse styroch velkych listov. Bol z toho dost mimo, a tak sa ma spytal, ci nechcem zapisat cely zosit? Len som sa pousmial a podal som index. V dalsich bojoch vela stastia, Rado ----------------------------------------------------- Cafte artikulacie. 1. 2. ako vzdy 3. Dokazte, ze kazdy suvisly graf, ktory nie je blok obsahuje aspon dva bloky, z ktorych kazdy ma len 1 artikulaciu. (3. Urobte si blokovy graf(strom)a je to jasne (listy)) ----------------------------------------------------- Caute ti, co este nemate grafy! Trochu neskoro, ale predsa pisem aj svoje otazky: 1. Mengerova teorema 2. Chromaticky polynom 3. Dokazte, ze kazdy sled neparnej dlzky obsahuje neparnu kruznicu. - robi sa to indukciou na dlzku sledu Este by som chcela poznamenat, ze som prisla na zaujimavu vec. Neviem, ci plati stale, ale mozne to je. Skoviera totiz dava vety s menom porade. Aspon na nasom termine to tak bolo. Prvy dostal Koniga a Halla pre parenie (skrytych za otazku parenie na bipartitnych grafoch), dalsi tu dalsiu vetu s menom (nepamatam sa, ako sa vola) a ja ako tretia som dostala Mengera, ktory nasleduje. Nie je zarucene, ze to tak robi vzdy, ale vyzera to tak.