Study of chordal graphs with Python

W pracy przedstawiono implementację w języku Python wybranych algorytmów dla grafów cięciwowych. Graf nieskierowany jest cięciwowy, jeżeli każdy cykl o długości większej niż trzy zawiera cięciwę, czyli krawędź łączącą dwa niekolejne wierzchołki cyklu. Grafy cięciwowe należą do rodziny grafów doskonałych i można je rozpoznać w czasie liniowym. Niektóre problemy trudne dla ogólnych grafów mogą być rozwiązane w czasie wielomianowym dla grafów cięciwowych. W pracy opisano wiele właściwości grafów cięciwowych i wykorzystano je do implementacji wydajnych algorytmów, w większości przypadków uzyskano liniową złożoność obliczeniową. Zaimplementowano trzy algorytmy wyszukiwania doskonałego uporządkowania wierzchołków (PEO): algorytm wierzchołków simplicjalnych, przeszukiwanie największej liczności (MCS), leksykograficzne przeszukiwanie wszerz. PEO zastosowano do rozpoznawania i generowania grafów cięciwowych, kolorowania grafów, znajdowania największej kliki, znajdowania wszystkich klik maksymalnych, znajdowania największego zbioru niezależnego.Zaimplementowano algorytm znajdowania uporządkowania najmniejszego stopnia (MDO) dla grafu ogólnego. MDO wykorzystano do kolorowania grafów cięciwowych, znajdowania największej kliki w grafie cięciwowym, oraz w algorytmie MMD. Opisano problem uzupełnienia cięciwowego dowolnego grafu nieskierowanego i podano dwie metody przybliżone wyznaczania szerokości drzewowej: algorytm MMD (dolne ograniczenie) i heurystykę najmniejszego stopnia (górne ograniczenie).W celu zapewnienia wysokiej jakości kodu źródłowego wykorzystano narzędzia języka Python do stworzenia testów jednostkowych. Sprawdzono praktyczną złożoność obliczeniową wszystkich algorytmów.Python implementation of selected graph algorithms for chordal graphs is presented. An undirected graph is chordal if every cycle of length greater than three has a chord - an edge joining two nonconsecutive vertices of the cycle. Chordal graphs belong to the family of perfect graphs and they can be recognized in polynomial time. Several problems that are hard for general graphs may be solved in polynomial time for chordal graphs. Many properties of chordal graphs are described and used to implement efficient algorithms, mostly with the linear complexity. Three algorithms for finding a perfect elimination ordering (PEO) of a chordal graph are presented: the simplicial vertices algorithm, maximum cardinality search (MCS), and lexicographic breadth-first search. PEO is used for chordal graph recognition and generation, graph coloring, finding a maximum clique, finding all maximal cliques, finding a maximum independent set. The algorithm for finding a minimum degree ordering (MDO) is implemented for general graphs. MDO is used for chordal graph colouring, finding a maximum clique, and in the MMD algorithm. A chordal completion problem is discussed and two approximate methods for finding the treewidth of graphs are shown: the MMD algorithm (a lower bound) and the minimal degree heuristic (an upper bound).The Python unit testing framework is used to assure high quality of source code. Real computational complexity of all algorithms was checked