Wykres ilorazowy
W teorii grafów graf ilorazowy Q grafu G jest grafem, którego wierzchołki są blokami podziału wierzchołków G i gdzie blok B sąsiaduje z blokiem C , jeśli jakiś wierzchołek w B sąsiaduje z pewnym wierzchołkiem w C pod względem do zbioru krawędzi G . Innymi słowy, jeśli G ma zbiór krawędzi E i zbiór wierzchołków V i R to relacja równoważności indukowana przez podział, to graf ilorazu ma zbiór wierzchołków V / R i zbiór krawędzi {([ u ] R , [ v ] R ) | ( u , v ) ∈ mi ( sol )}.
Bardziej formalnie, wykres ilorazowy jest obiektem ilorazowym w kategorii wykresów. Kategoria grafów jest konkretyzowalna - odwzorowanie grafu na jego zbiór wierzchołków czyni go kategorią konkretną - więc jej obiekty można traktować jako „zbiory z dodatkową strukturą”, a graf ilorazowy odpowiada grafowi indukowanemu na zbiorze ilorazowym V / R jego zbioru wierzchołków V . Ponadto istnieje homomorfizm grafu ( mapa ilorazowa ) z wykresu do wykresu ilorazowego, wysyłając każdy wierzchołek lub krawędź do klasy równoważności, do której należy. Intuicyjnie odpowiada to „sklejaniu” (formalnie „identyfikowaniu”) wierzchołków i krawędzi grafu.
Przykłady
Graf jest trywialnie sam w sobie wykresem ilorazowym (każdy blok podziału jest pojedynczym wierzchołkiem), a wykres składający się z pojedynczego punktu jest wykresem ilorazowym dowolnego niepustego wykresu (podział składający się z pojedynczego bloku wszystkich wierzchołków ). Najprostszy nietrywialny graf ilorazowy to taki, który uzyskuje się przez identyfikację dwóch wierzchołków ( identyfikacja wierzchołków ); jeśli wierzchołki są połączone, nazywa się to skróceniem krawędzi .
Specjalne rodzaje ilorazu
Kondensacja grafu skierowanego to wykres ilorazowy, w którym silnie połączone składowe tworzą bloki podziału. Tej konstrukcji można użyć do wyprowadzenia skierowanego grafu acyklicznego z dowolnego skierowanego grafu.
Wynikiem jednego lub więcej skróceń krawędzi w grafie nieskierowanym G jest iloraz G , w którym bloki są połączonymi składowymi podgrafu G utworzonego przez skrócone krawędzie. Jednak w przypadku ilorazów bardziej ogólnie, bloki podziału, z którego wynika iloraz, nie muszą tworzyć połączonych podwykresów.
Jeśli G jest wykresem pokrywającym inny wykres H , to H jest wykresem ilorazowym G . Bloki odpowiedniej partycji są odwrotnymi obrazami wierzchołków H pod mapą pokrywającą. Jednak mapy pokrywające mają dodatkowe wymaganie, które nie jest prawdziwe w przypadku ilorazów, aby mapa była izomorfizmem lokalnym.
Złożoność obliczeniowa
Jest NP-zupełny , mając n -wierzchołkowy wykres sześcienny G i parametr k , aby określić, czy G można otrzymać jako iloraz grafu planarnego z n + k wierzchołków.