Badanie grafów Hamiltona z językiem Python

master
dc.abstract.enpl
Python implementation of selected graph algorithms connected with Hamiltoniangraphs are presented. Graphs interface based on two clases is used.The Edge class represents directed weighted edges. The Graph class is forsimple weighted graphs, directed and undirected.In this work, two graphs traversing algorithms are implemented: breadth-firstsearch (BFS) and depth-first search (DFS). The recursive algorithm based onDFS is implemented, for finding all Hamiltonian paths and cycles in directedor undirected graphs.In the case of weighted undirected graphs, the travelling salesman problemis considered. The exact (brute force) algorithm based on DFS is given.Several heuristic algorithms are presented: the nearest neighbor algorithm,the repeated nearest neighbor algorithm, and the sorted edge algorithm. Forthe metric travelling salesman problem, 2-approximation algorithm is shown,which is based on the minimum spanning tree.In the case of directed graphs, the topological sorting algorithm is implemented.Two additional functions are given: for transitivity testing oftournaments and for finding a Hamiltonian path in tournaments.The important part of the work is a range of theorems on Hamiltoniancycles, with many educational examples. The algorithms solving the travellingsalesman problem were tested for the complexity and the accuracy.
dc.abstract.plpl
W pracy przedstawiono implementację w języku Python wybranych algorytmówzwiązanych z grafami Hamiltona. Wykorzystano interfejs dla grafówoparty na dwóch podstawowych klasach Edge i Graph. Klasa Edge reprezentujekrawędzie skierowane z wagą. Klasa Graph reprezentuje grafy proste ważone,skierowane i nieskierowane.W pracy zaimplementowano dwa algorytmy przeszukiwania grafów: algorytmprzeszukiwania wszerz (BFS), oraz algorytm przeszukiwania w głąb(DFS). Zaimplementowano algorytm rekurencyjny na bazie DFS, który znajdujewszystkie ścieżki i cykle Hamiltona w grafach skierowanych i nieskierowanych.Dla grafów nieskierowanych ważonych zbadano problem komiwojażera.Zaimplementowano algorytm dokładny na bazie DFS, oraz szereg algorytmówprzybliżonych: algorytm najbliższych sąsiadów, algorytm najbliższychsąsiadów z powtórzeniami, algorytm sortowania krawędzi. Dla metrycznegoproblemu komiwojażera przedstawiono algorytm 2-aproksymacyjny, bazującyna minimalnym drzewie rozpinającym. Omówiono również trzy metaheurystyki,które są stosowane w kontekście problemu komiwojażera.Dla grafów skierowanych acyklicznych zaimplementowany został algorytmsortowania topologicznego, na bazie DFS. Stworzono również funkcjedo badania tranzytywności turnieju (grafu pełnego skierowanego), oraz doznajdywania ścieżek Hamiltona w turniejach.Ważną częścią pracy są zestawienia twierdzeń matematycznych, któredotyczą cykli Hamiltona, z wieloma przykładami edukacyjnymi. Dla algorytmówrozwiązujących problem komiwojażera wykonane zostały testy wydajnościowe,oraz testy dokładności.
dc.affiliationpl
Wydział Fizyki, Astronomii i Informatyki Stosowanej
dc.areapl
obszar nauk ścisłych
Kapanowski, Andrzej - 100452
dc.contributor.authorpl
Szestało, Piotr
dc.contributor.departmentbycodepl
UJK/WFAIS
dc.contributor.reviewerpl
Marcinek, Roman - 100088
dc.contributor.reviewerpl
Kapanowski, Andrzej - 100452
dc.date.accessioned
2020-07-26T18:26:16Z
dc.date.available
2020-07-26T18:26:16Z
dc.date.submittedpl
2015-10-22
dc.fieldofstudypl
informatyka stosowana
dc.identifier.apdpl
diploma-101347-128594
dc.identifier.projectpl
APD / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/208346
dc.languagepl
pol
dc.subject.enpl
graph theory, Hamiltonian graphs, breadth-first search, depth-firstsearch, topological sorting, travelling salesman problem, metaheuristics, tournament
dc.subject.plpl
teoria grafów, grafy hamiltonowskie, przeszukiwanie wszerz,przeszukiwanie w głąb, sortowanie topologiczne, problem komiwojażera, metaheurystyki,turniej
dc.titlepl
Badanie grafów Hamiltona z językiem Python
dc.title.alternativepl
Study of Hamiltonian graphs with Python
dc.typepl
master
dspace.entity.type
Publication
Affiliations

## * The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

###### Views per city
Dublin
2
Wroclaw
2
Bayreuth
1

No access

No Thumbnail Available