Admin: finalizován tvar zápisu autorů hesel

2017-12-11T16:03:50Z

finalizován tvar zápisu autorů hesel

Admin: import na produkční server

2017-12-10T16:57:10Z

import na produkční server

Nová stránka

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ů.

<div class="translations">
theory of graphs
théorie des graphes
Graphentheorie
teoria dei grafici
</div>

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

-- ''[[:Kategorie:Aut: Lauber Josef|Josef Lauber]]'' 
[[Kategorie:Aut: Lauber Josef]]
[[Kategorie:Metodologie/matematicko-statistické metody v sociologii]]
[[Kategorie:VSgS]]

@@ Řádek 30: / Řádek 30: @@
 ''Lauber, J.'' – ''Hušek, R.'': Operační výzkum. Praha 1984.
--- ''[[:Kategorie:Aut: Lauber Josef|Josef Lauber]]''<br />
+''[[:Kategorie:Aut: Lauber Josef|Josef Lauber]]''<br />
 [[Kategorie:Aut: Lauber Josef]]
 [[Kategorie:Metodologie/matematicko-statistické metody v sociologii]]
 [[Kategorie:VSgS]]

Teorie grafů - Historie editací

Admin: finalizován tvar zápisu autorů hesel

Admin: import na produkční server