Wykres kliki
W teorii grafów graf klik nieskierowanego grafu G jest innym grafem K ( G ) reprezentującym strukturę klik w G .
Wykresy klik były omawiane co najmniej już w 1968 r., A charakterystyka wykresów klik została podana w 1971 r.
Definicja formalna
Klika grafu G jest zbiorem X wierzchołków grafu G z tą właściwością, że każda para różnych wierzchołków w X sąsiaduje w G . Maksymalną kliką grafu G jest klika X wierzchołków grafu G taka, że nie ma kliki Y wierzchołków grafu G , która zawiera wszystkie wierzchołki X i co najmniej jeden inny wierzchołek.
Mając dany graf G , jego graf kliki K ( G ) jest grafem takim, że
- każdy wierzchołek K ( G ) reprezentuje maksymalną klikę G ; I
- dwa wierzchołki K ( G ) sąsiadują ze sobą, gdy podstawowe kliki w G mają co najmniej jeden wspólny wierzchołek.
Graf klik K ( G ) można również scharakteryzować jako wykres przecięcia maksymalnych klik G .
Charakteryzacja
Graf H jest grafem klik K ( G ) innego grafu wtedy i tylko wtedy, gdy istnieje zbiór C klik w H , którego suma obejmuje wszystkie krawędzie H , tak że C tworzy rodzinę Helly . Oznacza to, że jeśli S jest podzbiorem C z tą właściwością, że każde dwa elementy S mają niepuste przecięcie, to samo S również powinno mieć niepuste przecięcie. Jednak kliki w C niekoniecznie muszą być klikami maksymalnymi.
Gdy H = K ( G ), można skonstruować rodzinę C tego typu, w której każda klika w C odpowiada wierzchołkowi v w G i składa się z klik w G zawierających v . Wszystkie te kliki mają v na swoim przecięciu, więc tworzą klikę w H . Rodzina C skonstruowana w ten sposób ma właściwość Helly, ponieważ każda podrodzina C z niepustymi przecięciami parami musi odpowiadać kliki w G , którą można rozszerzyć do maksymalnej kliki należącej do przecięcia podrodziny.
I odwrotnie, gdy H ma rodzinę Helly'ego C swoich klik, obejmującą wszystkie krawędzie H , to jest to graf kliki K ( G ) dla grafu G , którego wierzchołki są rozłączną sumą wierzchołków H i elementów C . Ten graf G ma krawędź dla każdej pary klik w C z niepustym przecięciem oraz dla każdej pary wierzchołka H i kliki w C , która go zawiera. Nie zawiera jednak żadnych krawędzi łączących pary wierzchołków w H . Maksymalne kliki na tym grafie G składają się z jednego wierzchołka H wraz ze wszystkimi klikami w C , które go zawierają, a ich wykres przecięcia jest izomorficzny z H .
Jednak ta charakterystyka nie prowadzi do wydajnych algorytmów: problem rozpoznania, czy dany graf jest grafem kliki, jest NP-zupełny .