|
Často je třeba orientovat se v komplikovaných vztazích mezi částmi nějakého celku. Řada lidí si při tom pomáhá obrázky podobnými těm, které najdete v této knize: části celku kreslíme jako puntíky, obdélníčky nebo kroužky, vztahy znázorňujeme čarami mezi nimi. Nesymetrické vztahy vyjadřujeme šipkami. Je zřejmé, že takto lze vyjádřit (a nakreslit) prakticky jakékoli vztahy mezi dvojicemi prvků.
Pojem grafu je přirozeným prostředkem k vyjádření párových vztahů, tj. vztahů mezi dvojicemi. Obecnější vztahy (už např. mezi trojicemi) lze nakreslit podstatně obtížněji. Snad proto se těmto obecnějším vztahům mnohdy vyhýbáme a raději volíme jiný, komplikovanější popis téže situace, založený na vztazích párových.
Díky tomu se nelze divit, že pojem grafu (a způsob uvažování, který označujeme jako grafový) je poměrně oblíbený a rozšířený. \medskip
Tato kniha je zaměřena na aplikace grafů.
Některé aplikace jsou zcela zjevné: daný problém "ze života" se přeformuluje na grafovou úlohu, udělá se příslušný graf, který modeluje konkrétní situaci, grafová úloha se nějakým známým postupem vyřeší a získané řešení se přeloží z řeči grafů zpátky "do života".
Často jsou však aplikace grafů skryté: nikde se žádný graf explicite nepoužije, graf zůstává jaksi v pozadí, ale použitý postup řešení má svou paralelu ve světě grafů a lze jej pomocí grafů zdůvodnit.
Umění aplikovat grafy zahrnuje dvě dílčí dovednosti. Především je třeba umět udělat (vymyslet) graf, který modeluje danou situaci (tj. jsou v něm zachyceny vztahy, o které nám jde). Někdy to je zcela triviální (např. při hledání cesty z Kolína do Rokycan), jindy to vyžaduje značnou lstivost.
Dále je třeba umět řešit alespoň ty nejdůležitější grafové úlohy, vědět, které úlohy jsou snadno a rychle řešitelné a které jsou naopak těžké. Také není k zahození, umíme-li převést nějakou (neznámou) úlohu na jinou, kterou dovedeme řešit. Toto umění převádět úlohy má mimochodem mnoho společného s uměním najít grafový model.
Kniha je určena pro technicky zaměřené čtenáře, zejména pro studenty technických vysokých škol. (Většinu textu však bez problémů přečte i středoškolák, který se nebojí používat "zdravý selský rozum".) Vím moc dobře, že tito lidé nemívají zálibu v matematických důkazech. Přesto v knize většinu jednoduchých tvrzení dokazuji. Jsem totiž přesvědčen, že k úspěšnému praktickému používání (nejen) teorie grafů je třeba umět samostatně vymyslet jednoduchý důsledek a korektně jej zdůvodnit. V knize uvedené důkazy můžete chápat jako příklady takových zdůvodnění. Pokud mohu radit, zkuste si nějaké (nejlépe každé) v knize uvedené tvrzení nejprve zdůvodnit sami a teprve potom čtěte důkaz. Konce důkazů jsou pro snazší orientaci označeny čtverečkem: \qed
Mnoho místa je v knize věnováno algoritmům a rozborům jejich fungování. Sleduji tím dva cíle: Při aplikacích se snadno můžete dostat do situace, kdy si musíte pro vaši speciální úlohu nějaký algoritmus vymyslet. Pokud si jej nebudete umět korektně zdůvodnit, snadno se můžete dočkat nečekaných (obvykle nepříjemných) překvapení. Druhý cíl se týká studentů informatiky. Teorie grafů je výborným cvičištěm s nepřeberným množstvím úloh pro výuku programování efektivních algoritmů.
Chci ovšem zdůraznit, že tato knížka není učebnicí navrhování a analýzy efektivních algoritmů. Výklad všelijakých důmyslných datových struktur zde není -- to by knížka byla o hodně tlustší a už by nebyla tak moc o grafech. Výjimku jsem udělal v kapitole 11, kde je velice stručně vysvětlen rozdíl mezi lehkými a těžkými úlohami.
Tato knížka koncepčně vychází z mých dřívějších publikací [Demel88], [Demel91]. Z nich jsem převzal hrubé členění textu na kapitoly a některé obrázky. Většina textu je však přepsána a rozšířena.
V knížce je řada cvičení jednak k počítání, jednak k samostatnému zamyšlení. Výsledky většiny cvičení jsou soustředěny na konci knihy.
Bude-li třeba po vydání této knihy zveřejnit k ní nějaké dodatky, opravy chyb apod., najdete je na Internetu na http://kix.fsv.cvut.cz/~demel/grafy/. Pokud byste mi chtěli napsat své připomínky, pište na adresu <demel zavináč fsv.cvut.cz>.
Děkuji všem, kdo svými připomínkami nebo jakkoli jinak přispěli ke zlepšení tohoto textu. Zejména děkuji za cenné připomínky oběma recenzentům. Děkuji také Ediční radě Akademie věd České republiky za finanční podporu na vydání této knihy. Především však děkuji své ženě Marii, která mi při psaní byla nejen všestrannou oporou, ale také prvním kritikem. Veškeré nedostatky, které v knize zůstaly, však padají na mou hlavu.
| Praha, leden 2002 | Jiří Demel |