.

0 (hodnocen0 x )

(11.8) Půjčeno:59x 

BK

Vyd. 1.

Praha : Academia, 2002

257 s. : il.

ISBN 80-200-0990-6 (váz.)

Obsahuje předmluvu, obrázky, grafy, rejstřík

Bibliografie s. 251-252

Teorie grafů - aplikace - učebnice vysokošk.

000034240

Předmluva 9 // 1 Základní pojmy 11 // 1.1 Definice grafu 11 // 1.2 Orientované a neorientované grafy 14 // 1.3 Důležité množiny hran a vrcholů 15 // 1.4 Porovnávání grafů 17 // 1.5 Sledy a odvozené pojmy 19 // 1.6 Speciální grafy 21 // 1.7 Kořenový strom 21 // 1.8 Matice popisující graf 24 // 1.9 Způsoby zadávání grafů 25 // 1.10 Zpracování grafů na počítači 27 // 1.11 Optimalizační úlohy 31 // 1.12 Množiny, relace a zobrazení 32 // 2 Aplikace úloh o cestách 37 // 2.1 Druhy modelů a úloh 37 // 2.2 Změny stavů a posloupnosti operací 38 // 2.3 Paralelně probíhající činnosti 41 // 2.4 Hledání statických konfigurací 44 // 3 Prohledávání grafů 47 // 3.1 Značkování vrcholů 47 // 3.2 Prohledávání grafu do šířky 49 // 3.3 Prohledávání grafu do hloubky 52 // 4 Pojmy založené na neorientovaných cestách 57 // 4.1 Souvislost 57 // 4.2 Stromy a kostry 58 // 4.3 Minimální kostra 61 // 4.4 Stupně souvislosti 65 // 5 Pojmy založené na orientovaných cestách 67 // 5.1 Silná souvislost 67 // 5.2 Acyklické grafy 73 // 5.3 Kořen a kořenový strom 77 // 5.4 Tranzitivní uzávěr a redukce 79 // 5.5 Jádro grafu a hry 83 // 6 Nejkratší cesty 85 // 6.1 Typy úloh a základní fakta 85 // 6.2 Základní schéma výpočtu vzdáleností 89 // 6.3 Algoritmy pro obecné grafy 94 // 6.4 Algoritmy pro acyklické grafy 98 // 6.5 Nezáporné délky hran 100 // 6.6 Využití dodatečné informace 102 // 6.7 Výpočet matice vzdáleností 103 // 6.8 Hledám cyklů se zápornou délkou 106 // 7 Algebraické souvislosti úloh o sledech 109 // 7.1 Polookruh a uzavřený polookruh 110 // 7.2 Úlohy o spojeních a jejich aplikace 114 // 7.3 Algoritmy úloh o spojeních 119 // 7.4 Elementární úpravy grafu 122 // 7.5 Signální toky 126 // 8 Toky v síti 129 // 8.1 Základní pojmy a úlohy 129 //

8.2 Aplikace toků v sítích 134 // 8.3 Maximální tok a minimální řez 139 // 8.4 Přípustná cirkulace 146 // 8.5 Obecné vlastnosti toků 149 // 8.6 Nejlevnější cirkulace 152 // 8.7 Algoritmus Out of Kilter 154 // 9 Párování 161 // 9.1 Základní pojmy, úlohy a aplikace 161 // 9.2 Párování v obecných grafech 163 // 9.3 Párování v bipartitních grafech 167 // 9.4 Přiřazovací úloha 171 // 10 Eulerovské tahy 177 // 10.1 Základní pojmy a aplikace 177 // 10.2 Existence a hledání eulerovských tahů 179 // 10.3 Úloha čínského pošťáka 182 // 11 NP-těžké úlohy 185 // 11.1 Časová složitost 185 // 11.2 Backtracking 189 // 11.3 Metoda větví a mezí 191 // 11.4 Heuristické algoritmy 196 // 12 Hamiltonovské cesty a kružnice 197 // 12.1 Základní pojmy, aplikace a vzájemné převody 197 // 12.2 Vzájemné převody úloh 199 // 12.3 Existenční hamiltonovské úlohy 202 // 12.4 Optimalizační hamiltonovské úlohy 203 // 13 Barevnost, nezávislost, kliky 211 // 13.1 Definice a základní fakta 211 // 13.2 Zjišťování barevnosti 216 // 13.3 Hledání maximálních nezávislých množin 219 // 14 Rovinné grafy 223 // 14.1 Nakreslení grafu a topologický rovinný graf 223 // 14.2 Duální grafy 226 // 14.3 Vlastnosti rovinných grafů 229 // 14.4 Charakterizace rovinných grafů 230 // 15 Cirkulace a potenciály 231 // 15.1 Vektorový prostor cirkulací 231 // 15.2 Potenciály a potenciálové rozdíly 234 // 15.3 Vztahy cirkulací a potenciálových rozdílů 238 // 15.4 Analýza elektrické sítě 240 // Výsledky cvičení 243 // Literatura 251 // Rejstřík 253 // Přehled značení // 257