# [zk] 27.6.2006 10:30

<{ForumPost(poster="pasky", timestamp=2006-06-27 15:30:19)}>
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.
<{/ForumPost}>

<{ForumPost(poster="pasky", timestamp=2006-06-27 16:04:06)}>

 > pasky wrote: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.
<{/ForumPost}>

<{ForumPost(poster="Petrik", timestamp=2006-06-27 21:27:55)}>
jak mám prosím vás rozvrstvit K7 na dvě roviny??
<{/ForumPost}>

<{ForumPost(poster="pasky", timestamp=2006-06-27 21:56:57)}>

 > Petrik wrote: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.
<{/ForumPost}>

<{ForumPost(poster="Necroman", timestamp=2006-06-27 22:38:28)}>

 > Petrik wrote: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.
<{/ForumPost}>

<{ForumPost(poster="tutchek", timestamp=2006-06-29 16:39:40)}>

 > Petrik wrote:jak mám prosím vás rozvrstvit K7 na dvě roviny??

[http://download.matfyz.info/kag/grafyKAG.jpg](http://download.matfyz.info/kag/grafyKAG.jpg)
<{/ForumPost}>

<{ForumPost(poster="tutchek", timestamp=2006-06-29 16:47:27)}>

 > pasky wrote:
 >  > pasky wrote: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 ;]]
<{/ForumPost}>