Teorie grafů

teorie grafů – jedna z novějších matem. disciplín, která se zabývá topologickými vlastnostmi útvarů složených z bodů (uzlů) a jejich spojnic (hran). Tyto útvary se nazývají grafy. Matem. se graf obvykle zapisuje takto: [math]G = (U,H)[/math], kde [math]U[/math] je množina uzlů a [math]H \subset U \times U[/math] je množina hran. Je-li množina [math]U[/math] konečná, pak se příslušný graf nazývá konečný, úplný graf je takový, že [math]H = U \times U[/math], naopak nulový graf je takový, že [math]U = \emptyset[/math] a [math]H = \emptyset[/math]. Multigraf je graf, v němž mezi alespoň jednou dvojicí uzlů z [math]U[/math] existuje větší počet hran než jedna. Hranově ohodnocený graf je takový graf, v němž hranám grafu jsou přiřazeny určité hodnoty (obvykle reálná čísla). Uzlově ohodnocený graf má přiřazeny hodnoty uzlům grafu. Orientovaný graf obsahuje hrany s přiřazeným směrem. Cestou v grafu se nazývá posloupnost orientovaných hran, pro niž platí, že následující hrana začíná v uzlu, v němž končí předcházející. Cyklus je cesta v grafu, která začíná a končí ve stejném uzlu. Řetězem nazýváme cestu bez ohledu na orientaci hran. Souvislý graf je takový, že mezi libovolnými dvěma uzly existuje alespoň jeden řetěz, jenž je spojuje. Acyklický graf neobsahuje žádný cyklus. Strom je souvislý acyklický graf. Síť je souvislý, orientovaný a hranově ohodnocený graf, v němž existuje jeden vstupní uzel (do něho žádná hrana nevstupuje) a jeden výstupní uzel (z něhož žádná hrana nevystupuje). Na grafech a sítích se řeší řada optimalizačních úloh (např. nejkratší cesta v grafu – algoritmus Fordův a Fulkersonův, nejpravděpodobnější cesta apod.). Prakticky nejdůležitější aplikace představují metody síťové nalýzy (metody analýzy kritické cesty), z nichž jsou nejznámější metody CPM, PERT a GERT, jež se používají při řízení složitých projektů.

theory of graphs théorie des graphes Graphentheorie teoria dei grafici

Literatura: Berge, C.: Graphs and Hypergraphs. Amsterdam 1973; Lauber, J. – Hušek, R.: Operační výzkum. Praha 1984.

-- Josef Lauber