Přímé procvičení probraných algoritmů

  1. V následujících grafech najděte minimální kostru:


    1. Hladovým (Kruskalovým) algoritmem.
    2. Jarníkovým (Primovým) algoritmem.
    3. Borůvkovým algoritmem.
  2. Najděte ohodnocený graf, který má jednoznačně určenou minimální kostru, ale jeho hrany nemají vzájemně různá ohodnocení.
  3. Profesor Fishbone tvrdí, že pojem „rozšířitelnost do minimální kostry“ není u základního meta-algoritmu vůbec potřeba a zbytečně meta-algoritmus komplikuje. Navrhuje meta-algoritmus, který postupně prochází libovolné řezy $\delta(W)$ a do minimální kostry přidá libovolnou nejlevnější hranu řezu $\delta(W)$. Meta-algoritmus skončí po přidání $n-1$ hran, protože v ten moment bude mít minimální kostru.

    Rozhodněte, jestli má profesor Fishbone pravdu a své rozhodnutí dokažte.

  4. (Test)
    Dostanete souvislý graf $G=(V,E)$ s cenami hran $c: E\to \RR$. Následující tvrzení mohou, ale nemusí být pravdivé. Vždy buď dokažte, že je tvrzení pravdivé, nebo nalezněte protipříklad.

    1. Pokud má graf $G$ více než $n-1$ hran, tak nejdražší hrana grafu určitě nepatří do minimální kostry.
    2. Jestli je $e$ nejlevnější hranou v grafu $G$, tak určitě patří do minimální kostry.
    3. Pokud je nejlevnější hrana v grafu $G$ určena jednoznačně (ostatní hrany jsou dražší), tak musí být obsažena v každé minimální kostře.
    4. Každá hrana, která je součástí minimální kostry, je nejlevnější hranou nějakého řezu.
    5. Pokud cyklus obsahuje pouze jednu nejlevnější hranu, tak tato hrana patří do minimální kostry.
    6. Nejkratší cesta mezi dvěma vrcholy určitě patří do minimální kostry.
    7. Strom nejkratší cesty obsahuje stejné hrany jako minimální kostra.
    8. Cesta $P$ je $r$-levná, pokud je cena každé hrany na cestě $P$ nejvýše $r$. Pokud graf $G$ obsahuje nějakou $r$-levnou cestu mezi $s$ a $t$, tak i každá minimální kostra $T$ obsahuje $r$-levnou cestu $sTt$.
    9. Minimální kostra je souvislý podgraf takový, že součet cen jeho hran je nejmenší možný.

    Správná odpověď je $114=[011100010]_2$.

Na teorii

  1. Je dáno $n$ bodů v rovině. Definujme ohodnocení hran úplného grafu na těchto bodech tak, že ohodnocením hrany $xy$ bude vzdálenost bodů $x,y$.
    1. Ukažte, že maximální stupeň vrcholu v libovolné minimální kostře je nejvýše $6$.
    2. Ukažte, že existuje minimální kostra, která je rovinná (jejíž hrany se navzájem nekříží).
  2. Dokažte, že neorientovaný graf $G$ s $n$ vrcholy a $k$ komponentami souvislosti má alespoň $n-k$ hran.
  3. Dostanete neorientovaný graf $G=(V,E)$, jehož hrany jsou ohodnoceny navzájem různými kladnými čísly. Dále dostanete vrchol $s\in V$. Je strom nejkratší cesty z $s$ do všech ostatních vrcholů shodný s minimální kostrou? Pokud ano, tak uveďte důvod. Pokud ne, tak uveďte příklad grafu, kde se liší.
  4. Nechť $G$ je neorientovaný ohodnocený graf, $H\subseteq G$ jeho podgraf a $T$ minimální kostra $G$. Ukažte, že $T\cap H$ je obsaženo v nějaké minimální kostře $H$.
  5. (lineální transformace ohodnocení hran)
    Dostanete graf $G=(V,E)$ s ohodnocením hran $c: E\to \RR$. Dokažte, že když je $T\subseteq G$ minimální kostrou v grafu $G$ s ohodnocením $c$, pak je $T$ minimální kostrou i v grafu $G$ s ohodnocením

    1. $f$, kde $f(e)=a\cdot c(e)$, pro nějakou konstantu $a\in \RR$, $a>0$.
    2. $g$, kde $g(e)=c(e)+k$, pro nějakou konstantu $k\in \RR$.
    3. $h$, kde $h(e)=a\cdot c(e)+k$, pro nějaké konstanty $a\in \RR$, $a>0$ a $k\in \RR$.

Na algoritmy

  1. (Maximální kostra)
    Najděte maximální kostru v grafu. Jaká je časová složitost vašeho algoritmu ve srovnání s algoritmy na nalezení minimální kostry?

  2. (Varianty či nevarianty minimální kostry)
    Dostanete graf $G=(V,E)$ s ohodnocením hran $c: E\to \RR$. Nalezněte kostru $T$ s minimálním

    1. $\max\limits_{e\in T} c(e)$.
    2. $\sum\limits_{e\in T} c(e)$.
    3. $\prod\limits_{e\in T} c(e)$, kde $c(e)\geq 0$ pro všechny hrany $e$.

    Čím se od sebe liší algoritmy pro nalezení jednotlivých variant minimální kostry?

  3. Dostanete graf, jehož hrany jsou ohodnoceny pouze čísly $1, 2, \dots , k$. Jak rychle dovedete najít minimální kostru v tomto grafu?

    Dokážete to v čase $\OO(kn+km)$? A v čase $\OO(kn+m)$? No jestli dokážete i to, tak co v čase $\OO((n+m)\alpha(n))$?

  4. Dostanete souvislý neorientovaný graf $G$. Navrhněte algoritmus, který zjistí, jestli z $G$ můžete smazat jednu hranu tak, aby graf zůstal souvislý. Nalezenou hranu vypište. Dovedete snížit časovou složitost vašeho algoritmu až na $\OO(n)$?
  5. Dostanete souvislý neorientovaný graf $G$ s ohodnocením hran $c: E\to \RR$. Navrhněte algoritmus, který najde nejlevnější množinu hran, které můžeme z grafu vymazat tak, aby graf zůstal souvislý, ale už neobsahoval žádnou kružnici.
  6. Jedna velká železniční společnost propojuje $n$ měst po celé Evropě. Některá města jsou propojeny přímým spojením. Fixní náklady na provoz přímého spojení mezi městy $u$ a $v$ jsou $c(uv)$ (bez ohledu na vytíženost spojení, jezdit se musí podle jízdního řádu). S několika přestupy existuje dopravní spojení mezi libovolnou dvojicí měst. Spočtěte, kolik nejvíc by železniční společnost mohla ušetřit, kdyby zrušina nadbytečná přímá spojení. (Stále musí být možné se dostat z libovolného města do libovolného jiného).
  7. Firma Truhlík a syn má ve městě $N$ budov a chce všechny svoje budovy propojit počítačovou sítí. Vedení firmy rozhodlo, ze pro $K$ ($1\le K\le N$) budov zakoupí vysokorychlostní připojení na Internet. Kromě toho mezi některými dvojicemi budov vybudují propojení optickým kabelem.

    Dvě budovy se nacházejí v téže komponentě sítě, pokud lze mezi nimi komunikovat pomocí optických kabelů (buď mají přímé spojení, nebo jsou spojeny nepřímo přes několik jiných budov). Aby bylo možné komunikovat mezi dvěma budovami ležícími v různých komponentách sítě, musí každá z těchto komponent obsahovat aspoň jeden počítač připojený na Internet.

    Soutěžní úloha: Na vstupu jsou dána čísla $N$ a $K$ a pro každou dvojici budov jedno kladné celé číslo $c(AB)=$ cena za propojení budov $A$ a $B$ optickým kabelem . Navrhněte efektivní algoritmus, jenž určí, kterých $K$ budov se má připojit na Internet a které dvojice budov se mají propojit optickým kabelem tak, aby mezi každými dvěma budovami bylo možné komunikovat a přitom aby celková cena za položení optických kabelů byla co nejmenší.

  8. Když chtěl Blátošlap konečně vyprat své ponožky tak, zjistil, že se mu na nich vyvinula celá kolonie neznámých živočichů. Protože to byl genetik, jal se hned tyto živočichy zkoumat a zjistil, ze i když se jedná o jediný druh, jeho zástupci jsou velmi rozmanití. DNA každého jedince má přesně $30$ znaků, které ho charakterizují a které se mohou měnit pouze mutací. Dalším výzkumem zjistil, že v prádelníku má $N$ různých poddruhů (poddruhy se navzájem liší alespoň v jednom znaku), i když jeden z nich převazuje.

    Ihned se dovtípil, že v jeho prádelníku došlo k evoluci. A protože ho zajímá její průběh, byli jste požádáni o vyřešení tohoto problému. Blátošlap Vám zadá $N$ a dále DNA jednotlivých poddruhů. DNA každého druhu je zapsáno binárně jako číslo $X$, $0 \leq X \leq 2^{30}-1$. $i$-tý bit tohoto čísla vyjadřuje, zda je $i$-tý z $30$ znaků přítomen.

    Vaším úkolem je zjistit, jaký poddruh se vyvinul z jakého, a počet mutací, ke kterým muselo při tomto vývoji dojít. Předpokládejte, ze vývoj probíhal tak, že každý poddruh kromě toho, který Vám Blátošlap zadal jako první (to je ten nejpočetnější), se vyvinul právě z jednoho jiného poddruhu. Navíc první zadaný poddruh je původním prapředkem všech poddruhů v prádelníku. Dále předpokládejte, že evoluce probíhala nejjednodušší možnou cestou, a tedy počet mutací v evoluci je nejmenší možný. Počet mutací je součet všech rozdílných znaků mezi každým poddruhem (kromě prvního zadaného) a jeho předkem. Navíc žádný poddruh v Blátošlapově prádelníku nevymřel, všechny evolucí vzniklé poddruhy přežily až do dnešní doby.

    Příklad: Pro $N = 4$ a poddruhy $0$, $3$, $7$, $12$ je hledaná evoluce tato: poddruhy $3$ a $12$ se vyvinuly z poddruhu $0$, poddruh $7$ se vyvinul z poddruhu $3$. Počet mutací, ke kterým muselo v evoluci dojít, je roven $5$.

  9. (Jednoznačnost minimální kostry)
    Dostanete souvislý ohodnocený graf $G$. Navrhněte co nejefektivnější algoritmus, který zjistí, jestli je minimální kostra grafu $G$ určena jednoznačně.

  10. (Počet koster)
    Jak je těžké spočítat, kolik má graf $G$ koster? A jak je těžké spočítat, kolik má ohodnocený graf $G$ minimálních koster? Navrhněte oba algoritmy a uveďte jejich časovou složitost.

  11. (Bottleneck distance)
    Dostanete souvislý ohodnocený graf. Úzké hrdlo na cestě $P$ je hrana $e\in P$, která má nejvyšší cenu. Bottleneck distance mezi vrcholy $u$ a $v$ je minimum z cen úzkého hrdla na všech cestách mezi $u$ a $v$.

    1. Navrhněte algoritmus, který pro každou dvojici vrcholů nalezne jejich bottleneck distance. Analyzujte časovou složitost vašeho řešení.
    2. Co by se změnilo, kdyby úzkým hrdlem byla nejlevnější hrana na cestě? Navrhněte algoritmus, který pro každou dvojici vrcholů nalezne jejich bottleneck distance.
  12. (Druhá nejmenší kostra)
    Když v ohodnoceném grafu $G$ nalezneme minimální kostru $T$, tak z grafu vyhodíme všechny hrany kostry $T$ a dostaneme graf $G’$. Minimální kostra v grafu $G’$ je druhou nejmenší kostrou grafu $G$.

    1. Navrhněte co nejrychlejší algoritmus, který najde druhou nejmenší kostru. Analyzujte jeho časovou složitost.
    2. Co kdybychom chtěli nalézt $k$ nejmenších koster? Jaká by byla časová složitost takového algoritmu?
  13. (Hybridní algoritmus)
    Dostaneme graf $G$ a chceme v něm nalézt minimální kostru. Podívejte se na algoritmus, který v první fázi provede $k$ iterací Borůvkova algoritmu. Ve druhé fázi zkontrahuje nalezené komponenty do vrcholů (viz pomocný graf u Borůvkova algoritmu) a na tento graf pustí Jarníkův algoritmus (s Fibonacciho haldou).

    1. Vyjádřete časovou složitost hybridního algoritmu pomocí $n$, $m$ a $k$.
    2. Pro jakou volbu parametru $k$ bude časová složitost algoritmu nejmenší? Kolik bude časová složitost hybridního algoritmu pro vhodnou volbu $k$?

Aproximační algoritmy využívající minimální kostry

  1. (Steinerovy stromy — dolní odhad pro aproximaci pomocí minimální kostry)
    Uvažujme pouze ohodnocené grafy takové, že ceny jejich hran splňují trojúhelníkovou nerovnost. Najděte graf $G=(V,E)$ a rozdělení jeho vrcholů $V$ na požadované $R$ a Steinerovy $S$ tak, aby cena jeho minimální kostry byla $(2-1/n)$ krát větší než cena jeho optimálního Steinerova stromu ($n=|V|$, kde $V=R\cup S$).

  2. (Problém obchodního cestujícího v grafech s trojúhelníkovou nerovností).1
    Obchodní cestující prodává svůj produkt v $n$ městech. Chce si naplánovat takovou trasu, aby objel všechna města a najel co nejméně kilometrů.

    Dostaneme úplný graf, jehož hrany jsou ohodnoceny kladnými reálnými čísly. Chceme najít Hamiltonovskou kružnici2 nejmenší ceny.

    Obecný problém obchodního cestujícího je $NP$-úplný, ale ve grafech s trojúhelníkovou nerovností lze aproximovat v polynomiálním čase s libovolnou pevnou přesností. V následujících příkladech budeme předpokládat, že ohodnocení hran grafu splňuje trojúhleníkovou nerovnost.

    1. Navrhněte algoritmus, který nalezne řešení problému ochodního cestujícího, které je nevýše $2$krát horší než optimální řešení.
    2. Nalezněte příklad grafu na $n$ vrcholech, ve kterém váš aproximační algoritmus nalezne $2$krát horší řešení, než je to optimální.3