Wykres klikowy - Clique graph
W teorii wykres , A wykres klika o nieukierunkowane grafu G jest kolejnym wykresem K ( G ), która stanowi strukturę klik w G .
Grafy klikowe były omawiane co najmniej w 1968 roku, a charakterystyka grafów klikowych została podana w 1971 roku.
Formalna definicja
Klika grafu G jest zestaw X wierzchołków G z własności, że każda para różnych wierzchołków X przylegają w G . Maksymalna klika grafu G to klika X wierzchołków G , taka, że nie ma żadnej kliki Y wierzchołków G, która zawiera wszystkie X i co najmniej jeden inny wierzchołek.
Biorąc pod uwagę 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 leżące poniżej kliki w G mają co najmniej jeden wspólny wierzchołek.
Wykres klika K ( G ) można również scharakteryzować jako wykresu przecięcia z klik maksymalnego o G .
Charakteryzacja
Graf H jest grafem kliki K ( G ) innego grafu wtedy i tylko wtedy, gdy istnieje zbiór C klik w H, których suma pokrywa wszystkie krawędzie H , tak że C tworzy rodzinę Helly . Oznacza to, że jeśli S jest podzbiorem C z własnoś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ć maksymalnymi klikami.
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 . Skonstruowana w ten sposób rodzina C ma własność Helly'ego, ponieważ każda podrodzina C z niepustymi przecięciami parami musi odpowiadać klikie w G , którą można rozszerzyć do maksymalnej kliki należącej do przecięcia podrodziny.
I odwrotnie, gdy H ma rodzinę Helly 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 wykres G ma krawędź dla każdej pary klik w C z niepustym przecięciem oraz dla każdej pary wierzchołków H i kliki w C, która go zawiera. Nie zawiera jednak żadnych krawędzi łączących pary wierzchołków w H . Każda maksymalna klika w tym grafie G składa 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 .
Ta charakterystyka nie prowadzi jednak do wydajnych algorytmów: problem rozpoznania, czy dany graf jest grafem klikowym, jest NP-zupełny .