[zk] 27.6.2006 10:30

[pasky]

Prikladu bylo pet, kazdy za sest bodu, spodni hranice kvalifikace byla kolem osmi bodu, od dvanacti nebo od trinacti trojka jista, od osmnacti dvojka a od 24 jednicka.

Vyhodil snad jen jednu nebo dve duse, byly i asi dve jednicky, dve dvojky a zbytek trojky ci seda zona.

1. Vytvorujici funkce k (1,-2,3,-4,5,-6,...)

2. Najit maximalni tok v pomerne hnusne siti (cca dvacet vrcholu a spousta hran) (tip: zabere to dost casu, takze pokud neco takoveho u zkousky dostanete, ale chcete se venovat necemu uzitecnejsimu, zkuste najit alespon nejaky dobry horni odhad tim, ze najdete nejaky "uzky" rez)

3. Ma uplny graf na n vrcholech (pro dostatecne velka n) vic koster nebo eulerovskych podgrafu? (Eulerovsky podgraf: kazdy vrchol ma sudy stupen.)

4. Je potreba navrhnout tisteny spoj sestavajici z k rovnobeznych vrstev . Vrstvy jsou propojeny n uzly (uzel je tedy usecka kolma na vrstvy a prochazejici vsemi vrstvami). Kazde dva uzly je treba propojit vodici, kazdy vodic lezi v jedne vrstve a vede od uzlu k uzlu. Zadne dva vodice lezici ve stejne vrstve se nesmi protinat. Ukolem je minimalizovat pocet vrstev pro zadane n. (Matematicka formulace: Uplny graf mate "rozvrstvit" do sjednoceni co nejmene hranove disjunktnich rovinnych podgrafu.)

a) Kolik vrstev je potreba a staci pro n = 5?
a) Kolik vrstev je potreba a staci pro n = 7?
c) Dokazte, ze pro kazde n je $k \ge n/6$.

5. a) Necht G je 3-regularni graf. dokazte, ze G je hranove 2-souvisly prave tehdy, kdyz je vrcholove dvousouvisly.
b) Je analogicke tvrzeni pravdive pro 3-souvislost?
c)* Urcete vsechna prirozena cisla k, pro ktera plati toto tvrzeni: Pro kazdy k-regularni graf G je $k_e(G) = k_v(G)$.

Reseni napisu za chvilku.

[pasky]

1. Vytvorujici funkce k (1,-2,3,-4,5,-6,...)

Kdo se dival na drivejsi pisemky, musel tohle mit. (1,2,3,4,5,6,...) dostanu jako derivaci, tedy 1/(1-x)^2. Zadanou posloupnost prepisu jako ((-1)^0*1, (-1)^1*2, (-1)^2*3, ...), a to je 1/(1-(-1)x)^2 neboli 1/(1+x)^2.

3. Ma uplny graf na n vrcholech (pro "velka" n) vic koster nebo eulerovskych podgrafu? (Eulerovsky podgraf: kazdy vrchol ma sudy stupen)

Snad skoro kazdy dostal za tuhle otazku alespon jeden bod, ktery se daval za to, ze jste tam napsali pocet koster v tom grafu ($n^{n-2}$). Ramcove zbytek: Eulerovske podgrafy odpovidaji nejakym zpusobem prostoru cyklu, jehoz mohutnost se zmeri, oboji se prevede do tvaru $2^neco$ a porovna. Eulerovske podgrafy vyhrajou.

4. Uplny graf mate "rozvrstvit" do sjednoceni co nejmene disjunktnich rovinnych podgrafu.

a) Kolik vrstev je potreba a staci pro n = 5?
a) Kolik vrstev je potreba a staci pro n = 7?
c) Dokazte, ze pro kazde n je $k \ge n/6$.

a) i b) jde na dve vrstvy; na jednu vrstvu jiste ne, protoze to nejsou rovinne grafy, na dvou vrstvach to uz jde nakreslit - tedy dukaz obrazkem.

c) se dokaze pomerne jednoduse pres dusledek Eulera, totiz ze $|E| \le 3|V| - 6$. $|V|$ je n (uplny graf), maximalni pocet hran v rovinnem grafu si oznacime jako $e_r = 3n - 6$. V nejlepsim pripade bude v kazde vrstve tohle maximum hran, tedy vrstev bude treba tolik, aby $ke_r \ge |E|$. $|E|$ je v uplnem grafu n nad dvema, tedy $n(n-1)/2$. Sesypeme dohromady:

$$ k * 3(n-1) \ge n(n-1)/2 $$
$$ k \ge n/6 $$

Q.E.D.

5. a) Necht G je 3-regularni graf. dokazte, ze G je hranove 2-souvisly prave tehdy, kdyz je vrcholove dvousouvisly.
b) Je analogicke tvrzeni pravdive pro 3-souvislost?

a) dokazeme sporem: neni-li vrcholove dvousouvisly, existuje jednovrcholovy rez; z nej nutne do jedne komponenty souvislosti vedou dve hrany, do druhe ale jenom jedna, a kdyz ji zahodime, rozbili jsme souvislost; tedy graf neni hranove dvousouvisly.

Naopak neni-li hranove dvousouvisly, vezmeme jednohranovy rez a zahodime jeden krajni vrchol; tim jsme prisli i o hranu z rezu a graf se rozpadl na dve komponenty souvislosti. Tedy graf neni vrcholove dvojsouvisly.

b) plati take, dokazalo se snad analogicky, akorat se musi pripady rozebrat trochu podrobneji. Nacrtem: neni-li vrcholove trojsouvisly, existuje dvojvrcholovy rez; z kazdeho vrcholu vede do jedne z komponent nejvyse jedna hrana, tedy tyhle hrany zahodime (jen jeste musime proverit pripad, kdy jsou hranou spojeny vrcholy rezu; lze si predstavit situaci, kdy z kazdeho vrcholu utrhneme hranu do jine komponenty souvislosti a pak pujde pres rez stale projit; protoze jsme ale jednu hranu spotrebovali na propojeni, do kazde z komponent z kazdeho rezoveho vrcholu vede jen jedna dalsi hrana, tedy muzeme pro oba vrcholy vybrat tu, ktera vede do stejne komponenty).

Neni-li hranove trojsouvisly, udelame to same jako v (a).

c) tusim, ze az po 3-regularitu to platilo a dal uz ne, hledaly se protipriklady.

[Petrik]

jak mám prosím vás rozvrstvit K7 na dvě roviny??

[pasky]

jak mám prosím vás rozvrstvit K7 na dvě roviny??

V prvni rovine si nakresli C_7 a vyrob triangulaci; treba tak, ze vyberes jeden vrchol z cyklu a ten pospojujes se vsemi uvnitr cyklu, a pak vyberes druhy vrchol a ten zase pospoujes se vsemi vne cyklu. Tim jsi dostal asi nejhustsi mozny rovinny graf na sedmi vrcholech. A v tuhle chvili uz staci jenom na druhe vrstve doplacat zbyvajici hrany, ktere chybi do K_7.

[Necroman]

jak mám prosím vás rozvrstvit K7 na dvě roviny??

V kapitolach z DM pisou, jak ho rozmistit na anuloid, coz je vlastne to same, jen "zadni stranu" anuloidu das do druhe vrstvy, to uz nebude zas tak tezke.

[tutchek]

jak mám prosím vás rozvrstvit K7 na dvě roviny??

[tutchek]

1. Vytvorujici funkce k (1,-2,3,-4,5,-6,...)

Kdo se dival na drivejsi pisemky, musel tohle mit. (1,2,3,4,5,6,...) dostanu jako derivaci, tedy 1/(1-x)^2. Zadanou posloupnost prepisu jako ((-1)^0*1, (-1)^1*2, (-1)^2*3, ...), a to je 1/(1-(-1)x)^2 neboli 1/(1+x)^2.

Alternativne jeste:

(1,-2,3,-4,5,-6,...) = b(x)

a(x) = (1,1,1,1,1,1,1,...) = 1/(1-x)
a'(x) = (1,2,3,4,5,6,...) = 1/(1-x)^2
(0,2,0,4,0,6,....) = x*(2,0,4,0,6,...) = 2x*(1,0,2,0,3,...) = 2x*a'(x^2) = 2x/(1-x^2)^2

b(x) = (1,2,3,4,5,6,...) - 2*(2x*(1,0,2,0,3,...)) = (1,2,3,4,5,6,...) - 4x*(1,0,2,0,3,...) = a'(x) - 4x*a'(x^2)

no a po mnoha upravach dorayite k tomu co psal pasky ;]]