Cvičení z Kombinatoriky a grafů I, LS 2007/2008

Cvičení se konají každé úterý v 9:00 v T11 v Tróji. Podmínkou k udělení zápočtu je získání aspoň 20 bodů za vyřešené domácí příklady. Svá řešení můžete odevzdávat na papíře, případně posílat v elektronické podobě na mou adresu (kyncl zavináč kam.mff.cuni.cz), a to ve formátu pdf nebo ps, případně txt (nebudete-li potřebovat psát moc vzorečků), anebo třeba jako naskenovaný obrázek. Na odevzdání budete mít čas do té doby, než si řešení předvedeme na cvičení (minimálně 1 týden od zadání). Všechna tvrzení ve svých řešeních zdůvodněte (i když v zadání není slovo "dokažte"), můžete samozřejmě používat tvrzení a věty dokázané na přednášce nebo na cvičení. Na případných konzultacích se můžeme domluvit osobně nebo e-mailem. Jinak mě občas s trochou štěstí můžete zastihnout v místnosti 125 na Malé Straně.

informace o přednášce

Příklady

Pokud nebudete rozumět zadání, nebo v něm najdete chybu, nebo se vám bude zdát z nějakého jiného důvodu podezřelé, neváhejte mi napsat.

Zadáno Číslo Body Příklad Poznámka

19.2. 1 2 Pro která n lze úplný graf K_n rozložit na hranově disjunktní
a) hamiltonovské kružnice, [1 bod]
b) hamiltonovské cesty? [1 bod] vyřešeno

2 2 Dokažte, že K_n lze rozložit na hranově disjunktní cesty různé délky. vyřešeno

3 4 Dokažte, že K_n lze rozložit na hranově disjunktní cesty délky 2 právě tehdy, když n mod 4 = 0 nebo 1. vyřešeno

4 3 Dokažte, že pro žádné přirozené n nejde šachovnice 4×n proskákat koněm jedním uzavřeným tahem (při kterém navštívíme každé políčko právě jednou). vyřešeno

5 3 Sestrojte nekonečně mnoho grafů, které jsou izomorfní svému doplňku. vyřešeno

26.2. 6 3 Dokažte, že každý úplný orientovaný graf obsahuje hamiltonovskou orientovanou cestu. vyřešeno

7 7 Jaké je nejmenší k = k(n) takové, že každý orientovaný graf, jehož všechny vrcholy mají výstupní stupeň aspoň 2, má orientovanou kružnici délky nejvýše k?

4.3. 8 3 Dokažte, že každý (neorientovaný) graf s n vrcholy a minimálním stupněm 3 obsahuje kružnici délky O(log n).

9 3 Dokažte, že kružnice ohraničující vnitřní stěny v rovinném nakreslení 2-souvislého grafu G tvoří bázi prostoru cyklů (tj. prostoru eulerovských podgrafů) grafu G.

10 2 Nechť A = {a_i,j; i, j = 1, 2, ..., n} je reálná čtvercová matice bez nulových prvků taková, že pro každé i = 1, 2, ..., n platí |a_i,i| ≥ ∑_j≠i |a_i,j|, a navíc aspoň pro jedno i platí ostrá nerovnost. Dokažte, že A je regulární. vyřešeno

11 1 Spočítejte hodnost (v závislosti na n) reálné čtvercové matice A = {a_i,j = i + j; i, j = 1, 2, ..., n}. vyřešeno

12 2 Spočítejte determinant (v závislosti na n) reálné čtvercové matice A = {a_i,j, i, j = 1, 2, ..., n}, kde a_i,i = 2 (pro každé i) a a_i,j = (-1)^|i-j| (pro i ≠ j). vyřešeno

13 3 Najděte minimální možnou hodnost (v závislosti na n) reálné čtvercové matice A = {a_i,j, i, j = 1, 2, ..., n} takové, že a_i,j = t_min(i,j), kde t₁, t₂, ..., t_n jsou různá kladná reálná čísla. vyřešeno

11.3. 14 3 Najděte nejmenší k = k(n) takové, že pro každý nebipartitní graf G na n vrcholech s maticí sousednosti A platí: G je souvislý právě tehdy, když matice A^k neobsahuje nulové prvky. vyřešeno

15 1 Dokažte, že bipartitní graf G na n vrcholech s maticí sousednosti A je souvislý právě tehdy, když matice A^n-1 + Aⁿ neobsahuje nulové prvky.

16 2 Dokažte, že každá reálná čtvercová matice, která má na diagonále všechny prvky větší než 1 a všechny ostatní prvky rovné 1, má kladný determinant. vyřešeno

17 2 Spočítejte počet koster grafu K_m,n.

18 2 Spočítejte počet koster grafu trojrozměrné krychle.

18.3. 19 5 Nechť L^(u) a A^(u) jsou matice, které vzniknou z Laplaceovy matice a matice sousednosti grafu G odebráním u-tého řádku a sloupce. Co spočítá determinant z matice L^(u) + 2A^(u)? (Je to matice, která vznikne z matice L^(u) nahrazením mínus jedniček plus jedničkami.) Ve kterých případech dostaneme počet koster grafu G?

20 2 Dokažte, že v souvislém grafu G platí: množina všech mostů je průnik všech koster. vyřešeno

21 2 Pro které d-regulární grafy má jejich matice sousednosti vlastní číslo -d? vyřešeno

25.3. 22 3 Dokažte, že žádnou konečnou projektivní rovinu nelze reprezentovat pomocí bodů a přímek v (euklidovské) rovině.

1.4. 23 4 Charakterizujte prvky ortogonálního doplňku prostoru cyklů v grafu G (dokažte, že je to množina všech (elementárních) řezů), spočítejte jeho dimenzi a najděte nějakou jeho bázi.

24 2 Pomocí vytvořujících funkcí sestrojte dvojici "falešných" šestistěnných kostek takových, že každá z kostek má na svých stěnách celkem 6 přirozených čísel (čísla se mohou opakovat a kostky mohou být různé), a pro každé přirozené k platí: pravděpodobnost, že při hodu oběma kostkami bude součet padlých čísel k, je stejná jako pro dvojici "pravých" kostek (které mají čísla 1, 2, 3, 4, 5, 6). Poznámka: "falešná" kostka je ta, která není "pravá". vyřešeno

25 2 Spočítejte počet perfektních párování v "žebříkovém" grafu Z_n, jehož vrcholy tvoří mřížku o rozměrech 2 × n a hrany jsou právě hrany této mřižky. (Např. Z₁ = K₂, Z₂ = C₄.)

26 6 Spočítejte počet koster grafu Z_n. (3 body za rekurenci, další 3 body za explicitní vzoreček)

27 2 Najděte vytvořující funkci f pro posloupnost částečných součtů třetích mocnin přirozených čísel, tedy (1, 1 + 8, 1 + 8 + 27, 1 + 8 + 27 + 64, ...). Pomocí funkce f najděte explicitní vzoreček pro n-tý prvek této posloupnosti. vyřešeno

8.4. 28 1 Najděte souvislý graf G s aspoň třemi vrcholy takový, že jeho druhá mocnina G² neobsahuje hamiltonovskou kružnici. (G^k je graf na stejné množině vrcholů jako G, přičemž hranou jsou spojeny právě ty dvojice vrcholů, které mají v G vzdálenost nejvýše k.) vyřešeno

29 4 Dokažte, že pro každý souvislý graf G s aspoň třemi vrcholy platí: pro každé dva různé vrcholy u, v grafu G existuje v grafu G³ hamiltonovská cesta z u do v. Hint: zkuste použít indukci podle velikosti kostry G.

30 2 Najděte 2008-regulární souvislý graf, který není hamiltonovský. vyřešeno

31 3 Pro každé přirozené k najděte graf, který má přesně k hamiltonovských kružnic.

32 2 Pro každé přirozené k najděte graf, který má přesně k perfektních párování.

22.4. 33 3 Nechť S je aspoň 3-prvková podmnožina vrcholů grafu G na n vrcholech taková, že součet stupňů libovolné dvojice vrcholů z S je aspoň n. Dokažte, že v grafu G existuje kružnice, která prochází všemi vrcholy množiny S.

34 5 Dokažte, že pro každé přirozené c existuje N tak, že pro každé obarvení množiny [N] = {1, 2, ..., N} c barvami existuje trojice různých čísel x, y, z stejné barvy, řešící rovnici x + y = 2z (jinými slovy - jednobarevná aritmetická posloupnost délky 3). Zkuste řešit indukcí podle c.

35 5 Dokažte, že pro každé přirozené n existuje N takové, že obarvíme-li hrany úplného grafu G na n vrcholech libovolným množstvím barev, pak v grafu G existují vrcholy v₁, v₂, ..., v_n tak, že je splněná aspoň jedna z následujících podmínek:
1) indukovaný graf G[v₁, v₂, ..., v_n] je duhový (tzn. všechny jeho hrany mají různou barvu)
2) barva hrany v_iv_j, pro i < j, závisí jen na i.

36 24 Rozhodněte, zda v každém obarvení roviny dvěma barvami existuje jednobarevná trojice bodů tvořící vrcholy
a) jednotkového rovnostranného trojúhelníka [2 body]
b) "degenerovaného" trojúhelníka s délkami stran 1, 2, 3. [2 body]
c) "degenerovaného" trojúhelníka s délkami stran 1, 1, 2. [20 bodů]

37 7 Rozhodněte, pro která přirozená čísla k platí: existuje n₀ > 0 takové, že pro všechna přirozená n > n₀ každý souvislý graf na n vrcholech má indukovaný podgraf s přesně k hranami.

29.4. 38 2 Najděte obarvení roviny 7 barvami tak, aby žádné dva body ve vzdálenosti 1 neměly stejnou barvu. vyřešeno

6.5. 39 2 Uvažujme graf Q_n (graf n-dimenzionální krychle), jehož vrcholy tvoří množinu {0, 1}ⁿ a hrany spojují vrcholy lišící se právě v jedné souřadnici. Na grafu Q_n uvažujme síť se zdrojem s = (0, 0, ..., 0) a stokem t = (1, 1, ..., 1), kde všechny hrany mají jednotkovou kapacitu. Sestrojte
a) celočíselný maximální tok [1 bod]
b) maximální tok, který je na všech hranách kladný. [1 bod]

40 2 Určete stupeň hranové souvislosti grafu Q_n.

41 2 Pro n ≥ 3 určete stupeň vrcholové souvislosti grafu K_n \ C_n. vyřešeno

42 3 Dokažte, že graf na n vrcholech s minimálním stupněm d ≥ (n - 1) / 2 je hranově d-souvislý.

43 3 Nechť d ≥ 2. Dokažte, že d-regulární souvislý bipartitní graf je hranově 2-souvislý.

13.5. 44 2 Které 2k-regulární grafy mají k-faktor? (k-faktor grafu G je k-regulární podgraf G obsahující všechny vrcholy G)

45 3 Dokažte, že každý 2k-regulární graf má 2-faktor.

46 5 V menze je 100 stolů uspořádaných do čtvercové mřížky 10 × 10. U každého stolu sedí jeden student a jí svůj oběd. Některé porce však byly nakaženy neznámou infekční chorobou, která se velmi rychle šíří, a to podle následujícího pravidla: má-li dosud nenakažený student aspoň dva nakažené sousedy (sousední jsou jen ti, jejichž stoly sousedí hranou, ne rohem), nakazí se také. Za chvíli se nakazili všichni studenti v menze. Dokažte, že na začátku muselo být nakaženo aspoň 10 porcí.

Zadáno	Číslo	Body	Příklad	Poznámka
19.2.	1	2	Pro která n lze úplný graf K_n rozložit na hranově disjunktní a) hamiltonovské kružnice, [1 bod] b) hamiltonovské cesty? [1 bod]	vyřešeno
	2	2	Dokažte, že K_n lze rozložit na hranově disjunktní cesty různé délky.	vyřešeno
	3	4	Dokažte, že K_n lze rozložit na hranově disjunktní cesty délky 2 právě tehdy, když n mod 4 = 0 nebo 1.	vyřešeno
	4	3	Dokažte, že pro žádné přirozené n nejde šachovnice 4×n proskákat koněm jedním uzavřeným tahem (při kterém navštívíme každé políčko právě jednou).	vyřešeno
	5	3	Sestrojte nekonečně mnoho grafů, které jsou izomorfní svému doplňku.	vyřešeno
26.2.	6	3	Dokažte, že každý úplný orientovaný graf obsahuje hamiltonovskou orientovanou cestu.	vyřešeno
26.2.	7	7	Jaké je nejmenší k = k(n) takové, že každý orientovaný graf, jehož všechny vrcholy mají výstupní stupeň aspoň 2, má orientovanou kružnici délky nejvýše k?
4.3.	8	3	Dokažte, že každý (neorientovaný) graf s n vrcholy a minimálním stupněm 3 obsahuje kružnici délky O(log n).
	9	3	Dokažte, že kružnice ohraničující vnitřní stěny v rovinném nakreslení 2-souvislého grafu G tvoří bázi prostoru cyklů (tj. prostoru eulerovských podgrafů) grafu G.
	10	2	Nechť A = {a_i,j; i, j = 1, 2, ..., n} je reálná čtvercová matice bez nulových prvků taková, že pro každé i = 1, 2, ..., n platí \|a_i,i\| ≥ ∑_j≠i \|a_i,j\|, a navíc aspoň pro jedno i platí ostrá nerovnost. Dokažte, že A je regulární.	vyřešeno
	11	1	Spočítejte hodnost (v závislosti na n) reálné čtvercové matice A = {a_i,j = i + j; i, j = 1, 2, ..., n}.	vyřešeno
	12	2	Spočítejte determinant (v závislosti na n) reálné čtvercové matice A = {a_i,j, i, j = 1, 2, ..., n}, kde a_i,i = 2 (pro každé i) a a_i,j = (-1)^\|i-j\| (pro i ≠ j).	vyřešeno
	13	3	Najděte minimální možnou hodnost (v závislosti na n) reálné čtvercové matice A = {a_i,j, i, j = 1, 2, ..., n} takové, že a_i,j = t_min(i,j), kde t₁, t₂, ..., t_n jsou různá kladná reálná čísla.	vyřešeno
11.3.	14	3	Najděte nejmenší k = k(n) takové, že pro každý nebipartitní graf G na n vrcholech s maticí sousednosti A platí: G je souvislý právě tehdy, když matice A^k neobsahuje nulové prvky.	vyřešeno
	15	1	Dokažte, že bipartitní graf G na n vrcholech s maticí sousednosti A je souvislý právě tehdy, když matice A^n-1 + Aⁿ neobsahuje nulové prvky.
	16	2	Dokažte, že každá reálná čtvercová matice, která má na diagonále všechny prvky větší než 1 a všechny ostatní prvky rovné 1, má kladný determinant.	vyřešeno
	17	2	Spočítejte počet koster grafu K_m,n.
	18	2	Spočítejte počet koster grafu trojrozměrné krychle.
18.3.	19	5	Nechť L^(u) a A^(u) jsou matice, které vzniknou z Laplaceovy matice a matice sousednosti grafu G odebráním u-tého řádku a sloupce. Co spočítá determinant z matice L^(u) + 2A^(u)? (Je to matice, která vznikne z matice L^(u) nahrazením mínus jedniček plus jedničkami.) Ve kterých případech dostaneme počet koster grafu G?
	20	2	Dokažte, že v souvislém grafu G platí: množina všech mostů je průnik všech koster.	vyřešeno
	21	2	Pro které d-regulární grafy má jejich matice sousednosti vlastní číslo -d?	vyřešeno
25.3.	22	3	Dokažte, že žádnou konečnou projektivní rovinu nelze reprezentovat pomocí bodů a přímek v (euklidovské) rovině.
1.4.	23	4	Charakterizujte prvky ortogonálního doplňku prostoru cyklů v grafu G (dokažte, že je to množina všech (elementárních) řezů), spočítejte jeho dimenzi a najděte nějakou jeho bázi.
	24	2	Pomocí vytvořujících funkcí sestrojte dvojici "falešných" šestistěnných kostek takových, že každá z kostek má na svých stěnách celkem 6 přirozených čísel (čísla se mohou opakovat a kostky mohou být různé), a pro každé přirozené k platí: pravděpodobnost, že při hodu oběma kostkami bude součet padlých čísel k, je stejná jako pro dvojici "pravých" kostek (které mají čísla 1, 2, 3, 4, 5, 6). Poznámka: "falešná" kostka je ta, která není "pravá".	vyřešeno
	25	2	Spočítejte počet perfektních párování v "žebříkovém" grafu Z_n, jehož vrcholy tvoří mřížku o rozměrech 2 × n a hrany jsou právě hrany této mřižky. (Např. Z₁ = K₂, Z₂ = C₄.)
	26	6	Spočítejte počet koster grafu Z_n. (3 body za rekurenci, další 3 body za explicitní vzoreček)
	27	2	Najděte vytvořující funkci f pro posloupnost částečných součtů třetích mocnin přirozených čísel, tedy (1, 1 + 8, 1 + 8 + 27, 1 + 8 + 27 + 64, ...). Pomocí funkce f najděte explicitní vzoreček pro n-tý prvek této posloupnosti.	vyřešeno
8.4.	28	1	Najděte souvislý graf G s aspoň třemi vrcholy takový, že jeho druhá mocnina G² neobsahuje hamiltonovskou kružnici. (G^k je graf na stejné množině vrcholů jako G, přičemž hranou jsou spojeny právě ty dvojice vrcholů, které mají v G vzdálenost nejvýše k.)	vyřešeno
	29	4	Dokažte, že pro každý souvislý graf G s aspoň třemi vrcholy platí: pro každé dva různé vrcholy u, v grafu G existuje v grafu G³ hamiltonovská cesta z u do v. Hint: zkuste použít indukci podle velikosti kostry G.
	30	2	Najděte 2008-regulární souvislý graf, který není hamiltonovský.	vyřešeno
	31	3	Pro každé přirozené k najděte graf, který má přesně k hamiltonovských kružnic.
	32	2	Pro každé přirozené k najděte graf, který má přesně k perfektních párování.
22.4.	33	3	Nechť S je aspoň 3-prvková podmnožina vrcholů grafu G na n vrcholech taková, že součet stupňů libovolné dvojice vrcholů z S je aspoň n. Dokažte, že v grafu G existuje kružnice, která prochází všemi vrcholy množiny S.
	34	5	Dokažte, že pro každé přirozené c existuje N tak, že pro každé obarvení množiny [N] = {1, 2, ..., N} c barvami existuje trojice různých čísel x, y, z stejné barvy, řešící rovnici x + y = 2z (jinými slovy - jednobarevná aritmetická posloupnost délky 3). Zkuste řešit indukcí podle c.
	35	5	Dokažte, že pro každé přirozené n existuje N takové, že obarvíme-li hrany úplného grafu G na n vrcholech libovolným množstvím barev, pak v grafu G existují vrcholy v₁, v₂, ..., v_n tak, že je splněná aspoň jedna z následujících podmínek: 1) indukovaný graf G[v₁, v₂, ..., v_n] je duhový (tzn. všechny jeho hrany mají různou barvu) 2) barva hrany v_iv_j, pro i < j, závisí jen na i.
	36	24	Rozhodněte, zda v každém obarvení roviny dvěma barvami existuje jednobarevná trojice bodů tvořící vrcholy a) jednotkového rovnostranného trojúhelníka [2 body] b) "degenerovaného" trojúhelníka s délkami stran 1, 2, 3. [2 body] c) "degenerovaného" trojúhelníka s délkami stran 1, 1, 2. [20 bodů]
	37	7	Rozhodněte, pro která přirozená čísla k platí: existuje n₀ > 0 takové, že pro všechna přirozená n > n₀ každý souvislý graf na n vrcholech má indukovaný podgraf s přesně k hranami.
29.4.	38	2	Najděte obarvení roviny 7 barvami tak, aby žádné dva body ve vzdálenosti 1 neměly stejnou barvu.	vyřešeno
6.5.	39	2	Uvažujme graf Q_n (graf n-dimenzionální krychle), jehož vrcholy tvoří množinu {0, 1}ⁿ a hrany spojují vrcholy lišící se právě v jedné souřadnici. Na grafu Q_n uvažujme síť se zdrojem s = (0, 0, ..., 0) a stokem t = (1, 1, ..., 1), kde všechny hrany mají jednotkovou kapacitu. Sestrojte a) celočíselný maximální tok [1 bod] b) maximální tok, který je na všech hranách kladný. [1 bod]
	40	2	Určete stupeň hranové souvislosti grafu Q_n.
	41	2	Pro n ≥ 3 určete stupeň vrcholové souvislosti grafu K_n \ C_n.	vyřešeno
	42	3	Dokažte, že graf na n vrcholech s minimálním stupněm d ≥ (n - 1) / 2 je hranově d-souvislý.
	43	3	Nechť d ≥ 2. Dokažte, že d-regulární souvislý bipartitní graf je hranově 2-souvislý.
13.5.	44	2	Které 2k-regulární grafy mají k-faktor? (k-faktor grafu G je k-regulární podgraf G obsahující všechny vrcholy G)
	45	3	Dokažte, že každý 2k-regulární graf má 2-faktor.
	46	5	V menze je 100 stolů uspořádaných do čtvercové mřížky 10 × 10. U každého stolu sedí jeden student a jí svůj oběd. Některé porce však byly nakaženy neznámou infekční chorobou, která se velmi rychle šíří, a to podle následujícího pravidla: má-li dosud nenakažený student aspoň dva nakažené sousedy (sousední jsou jen ti, jejichž stoly sousedí hranou, ne rohem), nakazí se také. Za chvíli se nakazili všichni studenti v menze. Dokažte, že na začátku muselo být nakaženo aspoň 10 porcí.