Graph theory

Tato bakalářská práce popisuje základní teoretické a praktické informace na téma "Teorie grafů". Celkem je rozdělena na tři hlavní kapitoly. V první kapitole se zaměřuje na teoretické vymezení včetně historického vývoje a základních pojmů z dané terminologie. Tato terminologie je potřebná pro pochopení termínů a postupů z následujících kapitol. Taktéž jsou součástí této kapitoly obrázky, které mají usnadnit pochopení textu. Následně je druhá kapitola věnovaná popisu nejznámějších metod grafického řešení úloh, s jejich praktickým využitím na vymyšlených příkladech. Ve třetí kapitole jsou zobrazeny dvě známé úlohy. Jedná se o "Úlohu čínského listonoše" a "Úlohu obchodního cestujícího". U každého typu úlohy se nachází teoretický popis, matematický model a příslušné řešení (použitý software Lingo). Práce je následně ukončena shrnutím, možným rozšířením a vlastními postřehy autora.

This thesis describes basic theoretical and practical information about "Graph theory". Work is divided into three main chapters. The first chapter is focused on theoretical definition. It includes historical overview as well as it describes basic terminology of the topic. This terminology is necessary for better understanding of terms and procedures in following chapters. The first chapter also includes a number of pictures, which should clarify the text. The second chapter is devoted to the description of basic methods for solving graphic tasks, with practical use on the imaginary examples. The third chapter describes the two well known problems: "The chinese postman problem" and "The traveling salesman problem". Each of them contains a theoretical description, a mathematical model and a corresponding solution (by using Lingo software). Thesis concludes with overall summary, possible extensions and author's own findings.