Cvičení z Algoritmů a grafů II. v LS16/17

Cvičení probíhají každou středu od 11:00 v učebně 1442 (budova A).


Podmínky zápočtu

Body lze získat za:

Zápočet je za

Konzultace

Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229 (prvočíslo!).

kontakt: tomas.valla@fit.cvut.cz

Studijní materiály

K dispozici je vývojová verze studijních textů, které pokrývají některé kapitoly z předmětu. K něčemu se mohou hodit tyto texty.

Mentální trénink

Kdo si chce trénovat své algoritmické myšlení nad rámec cvičení (nebo zkrátka jen řešit pěkné úlohy ve volném čase), má možnost.

Doporučuji následující dva zdroje:

Předchozí zdroje obsahují takřka nekonečnou zásobu zajímavých algoritmických úloh, od lehkých po brutální, včetně vzorového řešení, u KSP i s rozsáhlou sadou studijních materiálů.


Obsah cvičení

22.2.

Podmínky na zápočet. Pro jaké kombinace K a N existuje K-regulární graf na N vrcholech? Relace "mezi vrcholy u a v vede cesta" je ekvivalence na vrcholech grafu G a třídy této ekvivalence jsou přesně komponenty souvislosti grafu G. Pro A matici sousednosti grafu G je na pozici i,j v A^k počet sledů délky k.

1.3.

Orientovaný graf bez izolovaných vrcholů je silně souvislý právě tehdy, když obsahuje uzavřený orientovaný sled procházející všemi hranami. Nechť A je matice sousednosti grafu G, uvažme matici A+I; potom pozice i,j v matici (A+I)^k udává existenci sledu délky nejvýše k mezi i,j. Aplikace Havlovy věty na soubory stupňů. Každý vrcholově 2-souvislý graf je hranově 2-souvislý, opačně to neplatí. Každý vrcholově 2-souvislý graf obsahuje kružnici. Graf je 2-souvislý právě tehdy, když každé dva vrcholy leží na společné kružnici.

8.3.

Bylo suplování.

15.3.

Hledání max.toku v zadané síti. Dokazování a vyvracení skutečností ohledně toků. Protipříklad na to, proč nelze volit zlepšující cesty orientované. Jsou-li váhy celočíselné, FF se vždy zastaví. Vícezdrojové a vícestokové toky v síti.

22.3.

Algoritmus, který v orientovaném grafu najde vrchol takový, ze kterého existuje cesta do všech ostatních (nebo řekne, že neexistuje). Máme uhelné doly D_1,...D_n a továrny T_1,...,T_m, i-tý důl vytěží d_i uhlí, j-tá továrna potřebuje t_j uhlí aby mohla vyrábět, je dán bipartitní graf, mezi jakými doly a továrnami lze vozit uhlí; mohou všechny továrny vyrábět? k_e(G)≤δ(G) a k_v(G)≤δ(G). Konstrukce G, kde k_e(G)<δ(G) a k_v(G)<δ(G). Stupeň souvislosti grafu K_{n,m}. Stupeň vrcholové souvislosti grafu K_n\C_n. Algoritmus na zjištění stupně hranové souvislosti.

29.3.

Algoritmus na zjištění stupně hranové souvislosti: zjistěte, jak ho urychlit na O(n.složitost toků). Ukažte, že pro 3-regulární G je k_e(G)=k_v(G). Hrany K_n jdou rozložit na n-1 PP. PP v 3-reg. grafu obsahuje všechny mosty. Na louce svišti a díry, svišť uběhne d metrů než zaútočí orel, do díry se vleze 1 (nebo k) svišť, kolik se jich zachrání. Šachovnice s dírami, lze kompletně pokrýt dominovými kostkami? Šachovnice s dírami, kolik lze umístit věží, aby se neohrožovaly (přes díru se ohrožují/neohrožují).

5.4.

Pro n>3 mějme množinový systém A_1,...,A_n na n-prvkové množině X, kde |A_i|=n-3; tento systém má SRR. Ukažte, že CNF formule, která má v každé klauzuli právě n proměnných a každá proměnná se vyskytuje nejvýše n-krát, je vždy splnitelná. K_5 bez hrany a K_3,3 bez hrany jsou rovinné grafy. V rovinném grafu bez trojúhelníku platí m≤2n-4 a existuje v něm vrchol stupně nejvýše 3. Relace obloukové souvislosti je ekvivalence. Rovinnost či nerovinnost 3- a 4-rozměrné hyperkrychle. Nakreslení K_5, K_6 bez křížení na toroid.

12.4.

Najděte rovinný graf o minimálním stupni 5. Kolik musí mít nejméně vrcholů? Pro jaké nejmenší k dokážete pro každé dost velké n sestrojit rovinný graf s n vrcholy, z toho k vrcholy stupně právě 5 a ostatní s vyšším stupněm? Jak bude znít Eulerova formule pro graf s k komponentami souvislosti? Dokažte nerovinnost K_3,3 přímo pouze použitím Jordanovy věty o kružnici. Jak vypadá duál nakreslení grafu krychle. Nezávislost, klikovost a barevnost několika grafů. Graf d-rozměrné krychle je bipartitní. Pro každý graf existuje pořadí vrcholů takové, že FirstFit na něm dá přesně chromatické číslo grafu.

19.4.

Pro každý graf G je \alpha(G) ≥ |V(G)| / \chi(G). Pro zadané k najděte strom a pořadí jeho vrcholů takové, že na něm FirstFit použije alespoň k barev. FirstFit na K_{n,n} vždy dá 2. Floyd-Warshallovi stačí jediná matice, a jak v něm i vypisovat nejkratší cesty. Fibonacciho čísla rostou exponenciálně rychle, součtový vzoreček z přednášky. Opakování Fibonacciho haldy. Operace FHBuild. Lineární posloupnost operací, která v FH vytvoří lineárně hluboký stromeček. FHExtractMin nejde udělat rychleji než logaritmicky.

26.4.

Psali jsme písemku.

3.5.

Jak najít matici nejkratších vzdáleností pro strom. Všechny (2,3)-stromy pro klíče 1,...,5 a (2,4)-stromy pro klíče 1,...,6. Příklad na insertování a mazání do (a,b)-stromu. Minimum a následník v (a,b)-stromech. Join v (a,b)-stromech. Příklad systému hashovacích funkcí, který se nechová dobře.

10.5.

Nakreslení K_5 jedním tahem. Kdy je graf nakreslitelný jedním ne nutně uzavřeným tahem. Existence HK v mřížkách. K_{6,8} nemá HK. Příklady grafů, které mají/nemají HK a eul.tah. Protipříklad grafu bez troj.nerovnosti pro apx.alg. na TSP. Line graf eulerovského grafu je eulerovský.

Úlohy k vyřešení