Study of series-parallel graphs with Python

Praca prezentuje implementację w języku Python wybranych algorytmów dla grafów szeregowo-równoległych. Grafy szeregowo-równoległe (sp-grafy) są to grafy planarne z dwoma wyróżnionymi wierzchołkami, przy czym grafy są tworzone rekurencyjnie za pomocą trzech operacji: szeregowej, równoległej i jackknife. Najprostszym sp-grafem jest pojedyncza krawędź. W pracy rozważane są jedynie sp-grafy proste nieskierowane. W pracy opisano wiele właściwości sp-grafów i wykorzystano je do implementacji wydajnych algorytmów, na ogół działających z liniową złożonością obliczeniową.Zbudowano generatory dla przypadkowych sp-grafów, sp-drzew i k-drzew. Przygotowano algorytm rozpoznawania sp-grafów, który buduje sp-drzewo dla danego sp-grafu. Znalezione sp-drzewo jest wykorzystywane w algorytmach stosujących metodę programowania dynamicznego do znajdowania największego zbioru niezależnego, najmniejszego zbioru dominującego, największego skojarzenia, najmniejszego pokrycia wierzchołkowego. Podano algorytmy do kolorowania wierzchołków sp-grafu i do znajdowania doskonałego uporządkowania wierzchołków (PEO) dla uzupełnienia cięciwowego danego sp-grafu.Dodatkowo przygotowano algorytm do znajdowania PEO dla uzupełnienia cięciwowego grafu Halina. Graf Halina jest grafem planarnym, zbudowanym z płaskiego rysunku drzewa, posiadającego co najmniej cztery wierzchołki, bez wierzchołków stopnia dwa. Wszystkie liście drzewa, w kolejności wyznaczonej przez rysunek drzewa, są połączone krawędziami tworzącymi cykl zewnętrzny. Grafy Halina i sp-grafy należą do grafów o ograniczonej szerokości drzewowej.Python implementation of selected algorithms for series-parallel graphs is presented. Series-parallel graphs (sp-graphs) are planar graphs with two distinguished vertices, formed recursively by three composition operations: series,parallel, and jackknife. The simplest sp-graph is a single edge. In this work, simple undirected sp-graphs are considered only. Many properties of sp-graphs are described and used to implement efficient algorithms working, as a rule, with linear complexity. Generators for random sp-graphs, sp-trees, and k-trees are built. The algorithm for recognizing sp-graphs and building a corresponding sp-tree is prepared. An sp-tree is used in dynamic programming algorithms finding a maximum independent set, a minimum dominating set, a maximum matching, a minimum vertex cover. Algorithms for sp-graph vertex coloring and for a perfect elimination ordering (PEO) of a chordal completion are given. Additionaly, the algorithm for a PEO of a chordal completion for a Halin graph is given. A Halin graph is a planar graph constructed from a planar drawing of a tree having four or more vertices, no vertices of degree two, by adding an outer cycle of edges connecting all leafs of the tree in the cyclic order. Halin graphs and sp-graphs are graphs of bounded treewidth