pisemka 5.1.

1. Urcete pocet koster uplneho grafu (pozadoval se i dukaz, ne pouze vysledek). Kolik z techto koster obsahuje pevne zvolenou hranu?

2. Kolik existuje symterickych relaci na n prvkove mnozine?

3. Formulujte lemma o duhovych trojuhelnicich.

4. Kolik nejmene hran musi mit graf na n vrcholech s k komponentami?

5. Necht souvisle grafy G, G' maji stejne velke eulerovske mnoziny. Maji potom stejny pocet hran? Stejny pocet vrcholu?

6. Je dan uplny graf na n vrcholech {1,2,...,n}. Jeho hrana {i,j} ma vahu w({i,j}) = i+j. Najdete vahu kostry s nejmensi moznou vahou.

7. X(V) je mnozina vsech grafu na mnozine vrcholu V s lichym poctem hran. Pro grafy G(V, E), G'(V, E') je definovane castecne usporadani <= takto: G <= G' prave kdyz E je podmozina E' (neostra inkluze). Urcete vsechny minimalni prvky tohoto usporadani.

Velmi strucne reseni:

1. Nejak dokazat, ze pocet koster je n^(n-2). V druhe otazce je nejjedonussi si uvedomit, ze dva vrcholy spojene hranou muzeme povazovat za jeden vrchol a hledame tak pocet koster v uplnem grafu na n-1 vrcholech... proto (n-1)^(n-3)

2. Predstavime-li si matici relace, pak muzeme libovolne volit nuly a jednicky napriklad v horni trojuhelnikove matici (to diky symetrii.. a nemuzeme uz zadne volit na zbyvajicich pozicich v matici), vyjde 2^(n(n+1)).

3. Jen si to spravne pamatovat.. :)

4. Kazda komponenta je "alespon strom" a ten obsahuje vzdy o jedna mene hran nez vrcholu. Odtud n-k.

5. Staci protipriklad. Obecneji ma eulerovska mnozina velikost 2^(E-V+k), kde k je pocet komponent (zde k=1) (a mysli se velikosti mnozin).. odtud plyne jen rovnost E-V = E'-V', takze ani jedna implikace neplati.

6. Nejlepsi je pospojovat kazdy vrchol s jednickou. Clovek si s tim musi malinko pohrat, nakonec vyjde (n-1)(n+4)/2.

7. Jsou to vsechny grafy, ktere obsahuji prave jednu hranu. (+ dokazat par formalnich veci, ze to tak opravdu je..)

Hodne stesti az tam budete sedet :wink:

Mala oprava... ve 2) ma vyjit 2^(n(n+1)/2), kde n(n+1)/2 je pocet prvku horni trojuhelnikove matice.
Jeste drobna poznamka.. na pisemku jsme meli dokonce dve a pul hodiny (na prvnim predterminu meli pouze dve hodiny)

A co kdyby ta relace sice byla symetrická, ale nebyla reflexivní, tzn. že by existoval aspoň jeden prvek x, který by nebyl sám se sebou v relaci? Pak by se výsledek asi musel ještě násobit 2^n, protože by se ještě volily jedničky a nuly v hlavní diagonále, ne? Sice si to neumím představit, ale podle mě je to možný...

dz wrote:A co kdyby ta relace sice byla symetrická, ale nebyla reflexivní, tzn. že by existoval aspoň jeden prvek x, který by nebyl sám se sebou v relaci? Pak by se výsledek asi musel ještě násobit 2^n, protože by se ještě volily jedničky a nuly v hlavní diagonále, ne? Sice si to neumím představit, ale podle mě je to možný...

To prece ne, ty prvky z diagonaly zapocitavas do tech n(n+1)/2 prvku. Takze uz to nicim nenasobis, a to je btw. jasny, ze nemusi byt reflexivni.

dz wrote:A co kdyby ta relace sice byla symetrická, ale nebyla reflexivní, tzn. že by existoval aspoň jeden prvek x, který by nebyl sám se sebou v relaci? Pak by se výsledek asi musel ještě násobit 2^n, protože by se ještě volily jedničky a nuly v hlavní diagonále, ne? Sice si to neumím představit, ale podle mě je to možný...

Ty prvky na hlavni diagonale uz ve vyrazu n(n+1)/2 jsou zapocteny... Mozna narazis na to, ze do horni trojuhelnikove matice nepatri diagonala (ja presne nevim, jak se horni troj. matice definuje)... takze kdyztak presneji volime vsehcny prvky v horni trojuhelnikove matici vcetne diagonaly. Co se tyka reflexivity, tak symetricka relace muze a nemusi byt reflexivni, vetsinou refl. neni.

gmnn wrote:1) Urcete pocet koster uplneho grafu (pozadoval se i dukaz, ne pouze vysledek). Kolik z techto koster obsahuje pevne zvolenou hranu?

(...)

Velmi strucne reseni:

1. Nejak dokazat, ze pocet koster je n^(n-2). V druhe otazce je nejjedonussi si uvedomit, ze dva vrcholy spojene hranou muzeme povazovat za jeden
   vrchol a hledame tak pocet koster v uplnem grafu na n-1 vrcholech... proto (n-1)^(n-3)

(...)

Tohle podle me neni pravda. napr. pro n = 4 by Ti vyslo 3^1 = 3. Jenze tech koster je 8 (pro n = 4 se to da jeste jednoduse rozebrat). Shodou okolnosti jsem dnes tento problem resil a myslim si, ze ten pocet je n^(n-2) - 2*n^(n-3). Proc ? Staci se zkusit zamyslet, jak spocitat pocet koster takovych, ktere obsahuji nejakou hranu e a to pote odecist od poctu koster uplneho grafu.

Jinak jak se prislo zrovna na tech 2*n^(n-3) : napr. se spocita dvema zpusoby dvojice [kostra, hrana kostry]. A to nejprve jako suma pres vsechny hrany takova, ze clen v te sumy je pocet koster, na kterych se podili ona hrana. Je jasne, ze pro kazdou hranu e bude ten pocet koster stejny, jako pro kteroukoli jinou hranu e'. Proto tedy tato suma, neb mame (n nad 2) hran, bude (n nad 2) * K'(e). A K'(e) je ono cislo, ktere rika, na kolika kostrach se podili hrana e.
Tuto sumu ale muzeme vyjadrit jeste jinak. Staci si uvedomit, ze kdyz kazda kostra ma (n-1) a tudiz ta suma je rovna (n-1)*n^(n-2) ; aneb kazda kostra prispeje do te sumy (n-1). Z tehle rovnosti uz neni tezke zjistit, kolik je K'(e).

Snad je to pravda, dnes po IPSku jsem to konzultoval s MJem, a melo by to tak jit. BTW i v kapitolach je na to cviceni, kde je mj. hint, ktery mi nejdriv vubec nebyl jasny, ale jakmile jsem to vyresil, tak je z nej naprosto jasne, co se snazil naznacit.

Staci se zkusit zamyslet, jak spocitat pocet koster takovych, ktere obsahuji nejakou hranu e a to pote odecist od poctu koster uplneho grafu.

Ty prave chces pocitat pocet koster, ktere obsahuji pevnou hranu, tak proc to chces odcitat od poctu vsech koster? Ja uz to psal jednou, ale jinam, tak to napisu i sem. Porad si myslim, ze spravnej vysledek je 2*(n^(n-3)). Sice ti to haluzi vyslo pro 4 vrcholy, ale pro 3 ti to uz nefunguje (kostry jsou dve, ty spocitas jednu).. Jeste jednou podrobneji vysvetlim, jak si myslim, ze by to melo byt: Pocet hran uplneho grafu je (n nad 2) a pocet hran kostry je (n-1). Je zrejmy, ze kdyz uvazim vsech n^(n-2) koster, tak se v nich kazda hrana bude vyskytovat stejnekrat jako jakakoliv jina. Proto se da s trochou predstavivosti pochopit, ze [(n-1)/(n nad 2)]=[x/(n^(n-2))], x je pocet vsech koster, ktery maji 1 stejnou hranu.

Anonymous wrote:

Staci se zkusit zamyslet, jak spocitat pocet koster takovych, ktere obsahuji nejakou hranu e a to pote odecist od poctu koster uplneho grafu.

Ty prave chces pocitat pocet koster, ktere obsahuji pevnou hranu, tak proc to chces odcitat od poctu vsech koster? Ja uz to psal jednou, ale jinam, tak to napisu i sem. Porad si myslim, ze spravnej vysledek je 2*(n^(n-3)). Sice ti to haluzi vyslo pro 4 vrcholy, ale pro 3 ti to uz nefunguje (kostry jsou dve, ty spocitas jednu).. Jeste jednou podrobneji vysvetlim, jak si myslim, ze by to melo byt: Pocet hran uplneho grafu je (n nad 2) a pocet hran kostry je (n-1). Je zrejmy, ze kdyz uvazim vsech n^(n-2) koster, tak se v nich kazda hrana bude vyskytovat stejnekrat jako jakakoliv jina. Proto se da s trochou predstavivosti pochopit, ze [(n-1)/(n nad 2)]=[x/(n^(n-2))], x je pocet vsech koster, ktery maji 1 stejnou hranu.

Sorry, ja resil neco trosku jineho - pocet VSECH koster uplneho grafu bez jedne hrany, tedy vlastne pocet koster uplneho grafu bez poctu koster uplneho grafu obsahujici hranu e (njn, to je tak, kdyz clovek presne vidi, ze tenhle problem resil v ramci tamtoho problemu a jak zacne psat, tak uplne zapomene, co vlastne resi :-)). Takze jsem tam take spocital 2*n^(n-3), prakticky stejnou uvahou (akorat jinak zapsanou). Z te formule tedy vylezla 1 pro n = 3 jen proto, ze jsem pocital pocet koster bez te jedne hrany a ta je skutecne jen 1 (odebranim hrany z K[3] uz dostavame strom, resp. kostru).

Sorry, ja resil neco trosku jineho - pocet VSECH koster uplneho grafu bez jedne hrany, tedy vlastne pocet koster uplneho grafu bez poctu koster uplneho grafu obsahujici hranu e (njn, to je tak, kdyz clovek presne vidi, ze tenhle problem resil v ramci tamtoho problemu a jak zacne psat, tak uplne zapomene, co vlastne resi ). Takze jsem tam take spocital 2*n^(n-3), prakticky stejnou uvahou (akorat jinak zapsanou). Z te formule tedy vylezla 1 pro n = 3 jen proto, ze jsem pocital pocet koster bez te jedne hrany a ta je skutecne jen 1 (odebranim hrany z K[3] uz dostavame strom, resp. kostru).

No myslel jsem si to hned :D Btw ted premyslim, jak to dokazat indukci, mozna to nebude tezky.. Jestli u toho driv neusnu, tak to sem napisu. Nebo to sem nenapisu vubec, protoze zitra mam zkousku a pak uz me to jaksi nebude zajimat.. :D

Anonymous wrote:

Sorry, ja resil neco trosku jineho - pocet VSECH koster uplneho grafu bez jedne hrany, tedy vlastne pocet koster uplneho grafu bez poctu koster uplneho grafu obsahujici hranu e (njn, to je tak, kdyz clovek presne vidi, ze tenhle problem resil v ramci tamtoho problemu a jak zacne psat, tak uplne zapomene, co vlastne resi ). Takze jsem tam take spocital 2*n^(n-3), prakticky stejnou uvahou (akorat jinak zapsanou). Z te formule tedy vylezla 1 pro n = 3 jen proto, ze jsem pocital pocet koster bez te jedne hrany a ta je skutecne jen 1 (odebranim hrany z K[3] uz dostavame strom, resp. kostru).

No myslel jsem si to hned :D Btw ted premyslim, jak to dokazat indukci, mozna to nebude tezky.. Jestli u toho driv neusnu, tak to sem napisu. Nebo to sem nenapisu vubec, protoze zitra mam zkousku a pak uz me to jaksi nebude zajimat.. :D

Hodne stesti, ja mimochodem tez :-)

Wolda wrote:

gmnn wrote:1) Urcete pocet koster uplneho grafu (pozadoval se i dukaz, ne pouze vysledek). Kolik z techto koster obsahuje pevne zvolenou hranu?

(...)

Velmi strucne reseni:

1. Nejak dokazat, ze pocet koster je n^(n-2). V druhe otazce je nejjedonussi si uvedomit, ze dva vrcholy spojene hranou muzeme povazovat za jeden
   vrchol a hledame tak pocet koster v uplnem grafu na n-1 vrcholech... proto (n-1)^(n-3)

(...)

Tohle podle me neni pravda.
(...)

Pod tihou argumentu musim priznat, ze jsem se felil. Totiz v tom mem postupu se nektere puvodne ruzne kostry "slijou" na stejnou kostru.. a presne jak rikas, je to videt treba pro n=4. Tenhle priklad jsem mel v pisemce spatne a pak mi kamos rikal, jak to udelal on a ja jsem hned nevidel v tom tu chybu, tak jsem to sem napsal jako spravne...... Beru zpet, je to spatne, priznavam :roll:

Btw ted me napadlo jeste jedno reseni, ktere dava vysledek 2n^(n-3). Jestli si pamatujete, jak je v ucebnici popsana metoda povykosu, tak z toho se to da odvodit (ale je to asi o neco malo slozitejsi..).
Pri prvnim zpusobu pocitani budeme mit pevnou kostru a budeme pocitat pocet zakorenenych stromu takovych, ze hrana e ma cislo 1. Koren muzeme vybrat n zpusoby a hrany ocislujeme tak, ze hrane e priradime jednicku a ostatnim hranam mame (n-2)! zpusobu (celkem bylo n-1 hran). Oznacime-li hledany pocet koster k', mame dohromady n*(n-2)!k' zpusobu.
Pri druhem zpusobu pocitani budeme kreslit sipky (viz ucebnice). Prvni sipku musime nakreslit na hrane e (priradili jsme ji totiz vzdy cislo 1) a mame presne dva zpusoby jak ji orientovat. Pri vsech dalsich krocich mame n moznosti jak vybrat koncovy vrchol sipky. A kolik mame moznosti pro vyber pocatecniho vrcholu sipky? Musime vybrat komponentu grafu, ze ktere sipka vychazi (pak uz je jednoznacne urcena, protoze vychazi z korene teto komponenty), ale nesmime vybrat prave tu komponentu, ze ktere je koncovy vrchol (jinak bychom vytvareli kruznici). Mame-li v danem momente jiz rozmistenych k sipek, mame tedy (n-k-1) moznosti pro vyber koncoveho vrcholu sipky. Zde je ovsem potreba si uvedomit, ze po nakresleni prvni sipky na hrane e mame jiz o jednu sipku mene, takze (to je asi nejtezsi si rozmyslet) celkovy pocet zpusobu, jak "sipkama vyrobit strom" je soucin
2 [n*(n-2)] * [n*(n-3)] ... [n1]
Dohramady tedy je n(n-2)!k' = 2n^(n-2)(n-2)!, coz dava k'=2n^(n-2). Uf, gratuluju vsem, kteri se docetli uspesne az sem.

gmnn wrote: Dohramady tedy je n*(n-2)!k' = 2n^(n-2)(n-2)!, coz dava k'=2n^(n-2). Uf, gratuluju vsem, kteri se docetli uspesne az sem.

Ja uz nejsem schopny napsat cokoliv bez chyby... :( samozrejme nakonec k'=2*n^(n-3)