Temat: clique tree - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: Clique graph representations of ptolemaic graphs
Autorzy:: McKee, Terry
Tematy:: Ptolemaic graph
clique graph
chordal graph
clique tree
graph representation; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744102.pdf Link otwiera się w nowym oknie
Opis:: A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special case of the main result: The maximal Pₙ-free connected induced subgraphs of the p-clique graph of a ptolemaic graph G correspond in a natural way to the maximal $P_{n+1}$-free induced subgraphs of G in which every two nonadjacent vertices are connected by at least p internally disjoint paths.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Study of chordal graphs with Python
Badanie grafów cięciwowych w języku Python
Autorzy:: Olak, Małgorzata
Opis:: 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.
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.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Skocz do pozycji: 3.

Tytuł:: Graph classes defined by ordered forbidden structures
Klasy grafów definiowanych przez uporządkowane struktury zabronione
Autorzy:: Solon, Maciej
Opis:: The topic of this thesis is characteristic of graph classes, that are definable by small forbidden structures. In the first chapter we introduce basic definitions and properties of graph classes definable by small forbidden structures. In chapter 2 we characterize all graph classes which are defined by single forbidden structure of size 3; we can find among them comparability and incomparability graphs, chordal graphs and chordal graph complement, graphs without clique of size 3 and graphs without independent set of size 3. In chapter 3 we characterize all graphs defined by two forbidden structures of size 3; among them we can find threshold, permutation, bipartite, interval and unit interval graphs etc. In the final chapter 4 we introduce examples of graph classes, that can be defined by forbidden structures of size 4.
Celem pracy jest scharakteryzowanie klas grafów, które można zdefiniować za pomocą małych struktur zabronionych. W rozdziale 1 przedstawiamy podstawowe definicje i własności klas grafów definiowanych przez struktury zabronione. W rozdziale 2 charakteryzujemy wszystkie klasy grafów definiowanych przez jedną strukturę zabronioną wielkości trzy; wśród tych klas grafów odnajdujemy grafy porównywalności i nieporównywalności, grafy cięciwowe i dopełnienia grafów cięciwowych, grafy bez kliki wielkości trzy, i grafy bez zbioru niezależnego wielkości trzy. W rozdziale 3 charakteryzujemy wszystkie klasy grafów definiowanych przez dwie struktury wielkości trzy: wśród tych klas grafów znajdują się grafy progowe, permutacji, dwudzielne, przedziałowe i równoprzedziałowe, split grafy, itd. W ostatnim rozdziale 4 przedstawiamy przykłady klas grafów, które można zdefiniować za pomocą struktur zabronionych wielkości cztery.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Inne

na półce

Informacja

Wyszukujesz frazę "clique tree" wg kryterium: Temat