Název: Optimalizace toku grafem
Překlad názvu: Optimization of flow in graph
Autoři: Popovič, Viktor ; Lachout, Petr (vedoucí práce) ; Kozmík, Václav (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2013
Jazyk: slo
Abstrakt: [eng] [cze]
When it comes to maximization of effectively or minimizing of cost, optimization represents the key activity. There is a number of practical examples that can be implemented into Theory of Graphs and subsequently optimized. This thesis includes the introduction to transportation problem where the consumer demand is met by the lowest price. Also there is maximum flow problem which is to transfer maximum of commodity (petroleum, gas...) through the network where each edge has a capacity restriction. We will also look into the alternative situations where we will maximize the flow along with minimizing of cost. To resolve these problems we will establish numeric algorithms like distribute method, labeling algorithm, shortest augmented path algorithm, and Preflow-Push algorithms. We will also illustrate functionality on example which confirm appropriate application of algorithms and differences among them. Optimalizace je důležitá každodenní činnost, ať už chceme maximalizovat efektivitu nebo minimalizovat náklady. Mnoho problémů z praxe umíme převést do teorie grafů a následně optimalizovat. V této práci se budeme věnovat dopravnímu problému, který spočívá v uspokojení požadavků všech odběratelů za co nejnižší cenu. Další je problém maximálního toku, kde chceme sítí, v které má každá hrana kapacitní omezení, přepravit co nejvíce komodity (ropa, plyn, …). Také se podíváme na jeho alternaci v případě, že spolu s maximalizací toku chceme zároveň minimalizovat náklady. Na řešení těchto problémů si zavedeme numerické algoritmy jako metodu řádkových a sloupcových čísel, značkovací algoritmus, algoritmus nejkratší zvětšující se cesty a Preflow-Push algoritmus. Jejich funkčnost si nakonec předvedeme na příkladě, kde se potvrdí správnost algoritmů a jejich rozdíly.
Klíčová slova: Graf; numerický algoritmus; optimální tok; Graph; numerical algorithm; optimal flow

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/55464

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-324753


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce