The Chinese Postman Problem

Pierwszy rozdział zawiera wstępne wiadomości z teorii grafów, w postaci podstawowej terminologii i definicji. Prezentowany jest algorytm Depth First Search służący do wyszukiwania drzewa rozpinającego w grafie spójnym. Dowód poprawności wspomnianego algorytmu został samodzielnie przygotowany przez autora pracy, podobnie jak implementacja w języku R.W rozdziale drugim poruszony jest problem wyszukiwania drogi Eulera w grafie spójnym za pomocą algorytmu Fleury'ego. Wprowadzono pojęcie macierzy wystąpień, której użycie umożliwia reprezentację grafu w pamięci komputera. W przykładowym grafie spójnym wyszukano zamkniętą drogę Eulera, stosując samodzielnie napisany w języku R algorytm Fleury'ego, który wraz ze wspomnianą implementacją algorytmu Depth First Search został dołączony do pracy na płycie CD. Problem chińskiego listonosza jest poruszany bezpośrednio w rozdziale trzecim. W pierwszym podrozdziale przedstawiono teoretyczne podstawy zagadnienia, które umożliwiły sformułowanie i dowód twierdzenia (autorstwa Kwan Mei-Ko), podającego warunki wystarczający i konieczny, na to, aby proponowana trasa listonosza była rozwiązaniem optymalnym. W podrozdziale drugim skupiono się na algorytmie Floyda, wyszukującym najkrótsze drogi pomiędzy wierzchołkami grafu. Jego uzasadnienie teoretyczne zostało przygotowane samodzielnie przez autora pracy. Algorytm konstruujący drzewo zmienne oraz algorytm wyszukujący skojarzenie o maksymalnym koszcie zostały opisane w podrozdziale trzecim. W ostatnim, czwartym podrozdziale, zaprezentowano algorytm Edmondsa, służący do znajdowania rozwiązania optymalnego dla problemu chińskiego listonosza.Końcowy rozdział czwarty w całości skupia się na opracowaniu efektywnego sposobu odśnieżania alejek wokół budynku Wydziału Matematyki i Informatyki UJ. Jest to zadanie znalezienia rozwiązania dla problemu chińskiego listonosza. Przybliżone długości alejek pochodzą ze strony Google Maps. Do obliczeń wykorzystano język Python wraz z biblioteką networkx, zawierającą implementacje rozważanych w pracy magisterskiej algorytmów. Otrzymywane, w wyniku kolejnych kroków algorytmu Edmondsa, grafy i macierze są zamieszczane obok kodu źródłowego.

First chapter contains basic theorems and definitions of graph theory. Depth First Search algorithm is presented with proof which was elaborated by author of the thesis. Accordingly, implementation of Depth First Search in R was also prepared by author and is attached to the master thesis.In the second chapter, there is considered problem of finding Euler circuit in connected graph. Finally, Fleury's Algorithm is described and implemented in R (by author). Notion of incidence matrix is used to make implementation possible. Implementation of Fleury's Algorithm is attached to the master thesis. At the end of the chapter, there is a simple example of connected graph in which Euler circuit is found (with help of implemented Fleury's Algorithm).The Chinese Postman Problem is pondered in the third chapter. In the first subsection, there is shown theoretical background which leads to formulation of Kwan Mei-Ko's theorem. In the second subsection focus is set on the Floyd's algorithm. Theoretical reasoning of correctness of Floyd's algorithm was made by the author. Altenating-Tree Subroutine and Maximum-Weight Matching Algorithm are presented in third subsection. In the last, fourth subsection, there is shown Edmonds' Algorithm which finds solution of The Chinese Postman Problem. In the fourth chapter, there is considered problem of removing snow in efficient way form alleys around building of Department of Mathematics and Informatics. Approximated lengths of alleys comes from Google Maps site. Computations were conducted in Python (library networkx was used). Source code, resulting graphs and tables are presented in the master thesis.