Jagiellonian University Repository

Badanie planarności grafów z językiem Python

pcg.skipToMenu

Badanie planarności grafów z językiem Python

Show full item record

dc.contributor.advisor Kapanowski, Andrzej [SAP11015142] pl
dc.contributor.author Dziubek, Kacper pl
dc.date.accessioned 2020-07-26T18:26:04Z
dc.date.available 2020-07-26T18:26:04Z
dc.date.submitted 2015-10-22 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/208343
dc.language pol pl
dc.title Badanie planarności grafów z językiem Python pl
dc.title.alternative Planarity testing with Python pl
dc.type master pl
dc.abstract.pl W pracy przedstawiono podstawy teoretyczne i implementacje w języku Python wybranych algorytmów związanych z przeszukiwaniem grafów, badaniem spójności grafów, oraz z testowaniem planarności grafów. Do przechowywania grafów prostych stworzono klasę Graph. Implementacja powstała na bazie słownika słowników i pozwala przechowywać całe krawędzie jako obiekty klasy Edge. W celu dydaktycznym omówiono algorytmy przeszukiwania grafów w głąb (DFS) i wszerz (BFS). Przedstawione zostały również ich przykładowe implementacje. Szczególna uwaga została poświęcona algorytmowi DFS, który jest podstawą kolejnych algorytmów zaprezentowanych w pracy. W ramach lepszego zrozumienia DFS zaimplementowane zostały algorytmy związane ze spójnością grafów:testowanie spójności,trywialny algorytm znajdowania mostów, algorytm Tarjana znajdowania mostów, trywialny algorytm znajdowania punktów artykulacji i algorytm Tarjana znajdowania punktów artykulacji. W ramach badania planarności zaimplementowano algorytm lewy-prawy.Algorytm lewy-prawy sprawdza czy dany graf jest planarny i jeśli tak, to dla grafu abstrakcyjnego wyznacza graf topologiczny,czyli określa kolejność krawędzi wychodzących z wierzchołków oraz ściany grafu.Każdy algorytm został zaimplementowany jako osobna klasa. Dla wszystkich algorytmów przygotowane zostały testy jednostkowe z wykorzystaniem modułu unittest. Ponadto wykonano eksperymenty komputerowe sprawdzające zgodność rzeczywistej wydajności algorytmów z założeniami teoretycznymi. pl
dc.abstract.en In this work, theoretical foundations and Python implementation of selected algorithms for graph searching, connectivity, and for planarity testing of graphs are presented.The Graph class is created for simple graphs. It uses a dictionary of dictionaries data structure and it allows to store edges as instances of the Edge class.Depth-first search (DFS) and breadth-first search (BFS) algorithms are described theoretically and their sample implementation is provided. Special attention is given to DFS which is essential for many algorithms. In order to better understand DFS properties, we present algorithms for finding bridges, cutnodes, and testing graph connectivity.To test graph planarity, the left-right algorithm is implemented. It checks if an abstract graph is planar. In the case of a planar graph, the left-right algorithm calculates its topological graph (embedding). Then the ordering of the edges around each node is established.Each algorithm was implemented as a separate class. All algorithms were tested with unit tests based on unittest framework. Additionally, computer experiments were conducted to test real performance against theoretical predictions. pl
dc.subject.pl grafy, planarność, przeszukiwanie wszerz, przeszukiwanie w~głąb, punkty artykulacji, mosty, algorytm lewy-prawy, graf topologiczny pl
dc.subject.en graphs, planarity testing, depth-first search, breadth-first search, cutnode, bridge, left-right algorithm, topologial graph pl
dc.contributor.reviewer Marcinek, Roman [SAP11011562] pl
dc.contributor.reviewer Kapanowski, Andrzej [SAP11015142] pl
dc.affiliation Wydział Fizyki, Astronomii i Informatyki Stosowanej pl
dc.identifier.project APD / O pl
dc.identifier.apd diploma-101344-114175 pl
dc.contributor.departmentbycode UJK/WFAIS pl
dc.area obszar nauk ścisłych pl
dc.fieldofstudy informatyka stosowana pl


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)