2009. Poslední aktualizace: 19. května First Prev Next Last Go Back Full Screen Close Quit

Teorie grafů zadání úloh

letní semestr 2008/2009

Poslední aktualizace: 19. května 2009

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Obsah Úloha číslo 1

5

Úloha číslo 2

6

Úloha číslo 3

7

Úloha číslo 4

8

Úloha číslo 5

9

Úloha číslo 6

10

Úloha číslo 7

11

Úloha číslo 8

12

Úloha číslo 9

13

Úloha číslo 10

14


Úloha číslo 11

15

Úloha číslo 12

16

Úloha číslo 14

17

Úloha číslo 15

18

Úloha číslo 18

19

Úloha číslo 19

20

Úloha číslo 23

21

Úloha číslo 26

22

Úloha číslo 27

23

Úloha číslo 28

24

Úloha číslo 30

25


Úloha číslo 32

26

Úloha číslo 33

27

Úloha číslo 34

28

Úloha číslo 35

29


Úloha číslo 1 1. určete počet jednoduchých cyklů grafu

2. určete počet trojúhelníků v grafu


Úloha číslo 2 Ukažte, že v každé skupině aspoň dvou lidí, existují vždy dva s přesně stejným počtem přátel ve skupině.


Úloha číslo 3 Ukažte, že v-conn(G) ≤ e-conn(G) ≤ deg(G) pro libovolný graf.


Úloha číslo 4 Obtížnost: ∗∗ Ukažte: jestliže e-conn(G) ≥ 2 pro graf G, pak každé dva vrcholy v G jsou spojeny alespoň dvěma hranově disjunktními cestami.


Úloha číslo 5 Které dvojice grafů na následujícím obrázku jsou isomorfní a proč?


Úloha číslo 6 Ukažte: jestliže dva grafy jsou isomorfní, potom musí existovat bijekce mezi množinami jejich vrcholů taková, že odpovídající si uzly mají tentýž stupeň a leží v tomtéž počtu jednoduchých cyklů.


Úloha číslo 7 Jsou následující grafy vrcholově, silně hranově či hranově symetrické?


Úloha číslo 8 Ukažte: jestliže G je regulární graf a deg(G) = 3, pak v-conn(G) = e-conn(G). Najděte příklad grafu G, jenž je regulární, deg(G) > 3 a v-conn(G) 6= e-conn(G).


Úloha číslo 9 Najděte příklad grafu, který je • hranově symetrický, ale ne vrcholově symetrický (obtížnost: ∗) • vrcholově symetrický, ale ne hranově symetrický (obtížnost: ∗)


Úloha číslo 10 Ukažte, že následující grafy jsou bipartitní:


Úloha číslo 11 Obtížnost: ∗ Ukažte: Graf je bipartitní tehdy a jen tehdy, když neobsahuje žádný cyklus liché délky.


Úloha číslo 12 Určete kostru pro následující graf.

Kolik různých koster tento graf má?


Úloha číslo 14 Ukažte, že každý graf G je prostorový. To jest, že jeho uzly mohou být zobrazeny do bodů trojrozměrného prostoru tak, že žádné přímkové hrany spojující odpovídající uzly grafu G se neprotínají ani s jinými hranami, ani s body reprezentujícími uzly grafu G. (Návod: zobrazte k-tý uzel grafu G na bod (k, k 2 , k 3 ).)


Úloha číslo 15 Určete šířku bisekce následujících grafů.


Úloha číslo 18 Ukažte, že binární strom má nejvýše jedno perfektní párování.


Úloha číslo 19 Dva lidé hrají hru na grafu G = (V, E), kde |V | > 2, střídavým vybíráním rozdílných uzlů tak, aby vznikla cesta. Poslední hráč schopný vybrat uzel vyhrává. Ukažte, že existuje vítězná strategie pro prvního hráče tehdy a jen tehdy, když G nemá žádné perfektní párování.


Úloha číslo 23 Nechť G = (V, E) je bipartitní graf s birozdělením vrcholů do množin A = {a1 , . . . , an } a B = {b1 , . . . , bm }. Každé hraně (ai , bj ) přiřaďte proměnnou xij . Nechť MG = {mij } je m × n matice taková, že mij = xij , pokud (ai , bj ) ∈ E a mij = 0 jinak. Ukažte, že G má perfektní párování tehdy a jen tehdy, když det(MG ) není identicky roven 0.


Úloha číslo 26 Ukažte, že χ0 (G) = deg(G) + 1 pro Petersenův graf:


Úloha číslo 27 Ukažte, jak obarvit hrany bipartitního grafu Km,n pomocí deg(Km,n ) barev.


Úloha číslo 28 Ukažte: jestliže M1 a M2 jsou disjunktní párování grafu G s |M1 | > |M2 |, pak existují disjunktní párování M1 0 a M2 0 taková, že |M1 0 | = |M1 | − 1, |M2 0 | = |M2 | + 1 a M1 ∪ M2 = M1 0 ∪ M2 0 .


Úloha číslo 30 Ukažte, že pro každé n ≥ 1 existuje orientovaný graf Gn s 2n + 3 uzly, jenž má přesně 2n Hamiltonových cest (a může být považován za zakódování všech binárních řetězců délky n).


Úloha číslo 32 Navrhněte algoritmus pro konstrukci Eulerova tahu v grafu (za předpokladu, že existuje) a aplikujte jej pro návrh Eulerova tahu v grafu na následujícím obrázku:


Úloha číslo 33 Navrhněte Hamiltonův cyklus pro graf na obrázku:

(To je abstrakce původní Hamiltonovvy hádanky zvané „Cesta kolem světaÿ, jež vedla ke konceptu Hamiltonova cyklu – hádanka byla, samozřejmě, trojrozměrná.)


Úloha číslo 34 Najděte všechny různé minimální kostry grafu na následujícím diagramu:


Úloha číslo 35 Použijte Kruskalův a Primův algoritmus k návrhu minimální kostry grafu na následujícím obrázku:


2009. Poslední aktualizace: 19. května First Prev Next Last Go Back Full Screen Close Quit

Recommend Documents