Simple view
Full metadata view
Authors
Statistics
Algorytmy kolorowania krawędzi grafów
Selected graph algorithms for edge coloring
grafy dwudzielne, grafy planarne, kolorowanie krawędzi, twierdzenie Vizinga
bipartite graphs, planar graphs, edge coloring, Vising’s theorem
W pracy przedstawiono implementację w języku Python wybranych algorytmów kolorowania krawędzi grafów. Zebrano wyniki teoretyczne dla grafów pełnych oraz dwudzielnych. Przygotowane zostały również testy poprawności i testy złożoności obliczeniowej korzystające ze standardowych modułów Pythona (unittest, timeit).Zaimplementowano pięć algorytmów kolorowania krawędzi grafów: dla grafu pełnego, dla grafu dwudzielnego pełnego, dla grafu dwudzielnego pro- stego, dla grafu dwudzielnego regularnego, oraz dla grafu planarnego. Stworzono również generator grafów planarnych z ograniczonym największym stopniem wierzchołka.Podczas implementacji korzystano z pakietu graphtheory rozwijanego w Instytucie Fizyki UJ. Przeprowadzono również migrację pakietu z Pythona 2 do Pythona 3.
Python implementation of selected graph algorithms for edge coloring is pre- sented. Known theoretical results for complete graphs, and bipartite graphs are collected. Tests for correctness and computational complexity are provi- ded, were standard Python modules are used (unittest, timeit).The algorithms for a proper edge coloring for selected graphs are pre- sented: complete graphs, complete bipartite graphs, simple bipartite graphs, regular bipartite graphs and planar graphs. Planar graph generators are pro- vided where the maximum vertex degree is limited.The graphtheory package is used during implementation. Package migration from Python 2 to Python 3 is done.
| dc.abstract.en | Python implementation of selected graph algorithms for edge coloring is pre- sented. Known theoretical results for complete graphs, and bipartite graphs are collected. Tests for correctness and computational complexity are provi- ded, were standard Python modules are used (unittest, timeit).The algorithms for a proper edge coloring for selected graphs are pre- sented: complete graphs, complete bipartite graphs, simple bipartite graphs, regular bipartite graphs and planar graphs. Planar graph generators are pro- vided where the maximum vertex degree is limited.The graphtheory package is used during implementation. Package migration from Python 2 to Python 3 is done. | pl |
| dc.abstract.pl | W pracy przedstawiono implementację w języku Python wybranych algorytmów kolorowania krawędzi grafów. Zebrano wyniki teoretyczne dla grafów pełnych oraz dwudzielnych. Przygotowane zostały również testy poprawności i testy złożoności obliczeniowej korzystające ze standardowych modułów Pythona (unittest, timeit).Zaimplementowano pięć algorytmów kolorowania krawędzi grafów: dla grafu pełnego, dla grafu dwudzielnego pełnego, dla grafu dwudzielnego pro- stego, dla grafu dwudzielnego regularnego, oraz dla grafu planarnego. Stworzono również generator grafów planarnych z ograniczonym największym stopniem wierzchołka.Podczas implementacji korzystano z pakietu graphtheory rozwijanego w Instytucie Fizyki UJ. Przeprowadzono również migrację pakietu z Pythona 2 do Pythona 3. | pl |
| dc.affiliation | Wydział Fizyki, Astronomii i Informatyki Stosowanej | pl |
| dc.area | obszar nauk ścisłych | pl |
| dc.contributor.advisor | Kapanowski, Andrzej - 100452 | pl |
| dc.contributor.author | Wlazło, Piotr | pl |
| dc.contributor.departmentbycode | UJK/WFAIS | pl |
| dc.contributor.reviewer | Kapanowski, Andrzej - 100452 | pl |
| dc.contributor.reviewer | Cieśla, Michał - 101020 | pl |
| dc.date.accessioned | 2020-07-28T00:38:03Z | |
| dc.date.available | 2020-07-28T00:38:03Z | |
| dc.date.submitted | 2019-09-20 | pl |
| dc.fieldofstudy | informatyka | pl |
| dc.identifier.apd | diploma-133402-229788 | pl |
| dc.identifier.project | APD / O | pl |
| dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/235714 | |
| dc.language | pol | pl |
| dc.subject.en | bipartite graphs, planar graphs, edge coloring, Vising’s theorem | pl |
| dc.subject.pl | grafy dwudzielne, grafy planarne, kolorowanie krawędzi, twierdzenie Vizinga | pl |
| dc.title | Algorytmy kolorowania krawędzi grafów | pl |
| dc.title.alternative | Selected graph algorithms for edge coloring | pl |
| dc.type | licenciate | pl |
| dspace.entity.type | Publication |