Original title: Optimalizace toku grafem
Translated title: Optimization of flow in graph
Authors: Popovič, Viktor ; Lachout, Petr (advisor) ; Kozmík, Václav (referee)
Document type: Bachelor's theses
Year: 2013
Language: slo
Abstract: [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.
Keywords: Graph; numerical algorithm; optimal flow; Graf; numerický algoritmus; optimální tok

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/55464

Permalink: http://www.nusl.cz/ntk/nusl-324753


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses