Egy irányítatlan G gráf klikkgráfja egy másik K ( G ) gráf, amely a G gráf klikkszerkezetét reprezentálja .
A klikkgráfokat legalább 1968 óta tárgyalják [1] , a klikkgráfok leírását 1971-ben adták [2] .
A G gráf klikkje a G gráf csúcsainak X halmaza , amelynek megvan az a tulajdonsága, hogy X bármely különböző csúcspárja össze van kötve egy éllel G -ben . G maximális klikkje G csúcsainak X klikkje úgy, hogy nincs G-nek olyan Y csúcs - klikje, amely tartalmazza X összes csúcsát és legalább egy másik csúcsot.
Adott egy G gráf , annak K ( G ) klikkgráfja olyan gráf, hogy
A H gráf egy másik gráf K ( G ) klikkgráfja akkor és csak akkor, ha van olyan C klikkhalmaz H -ben, amelynek halmaza lefedi H minden élét úgy , hogy C Helly családot alkot . Ez azt jelenti, hogy ha S egy C részhalmaza azzal a tulajdonsággal, hogy S bármely két elemének van nem üres metszéspontja, akkor Snek magának is kell egy nem üres metszéspontja. A C halmazban lévő klikkeknek azonban nem kell maximális klikkeknek lenniük [2] .
Ha H = K ( G ), akkor létrehozható egy ilyen típusú C család , amelyben minden C -beli klikk G-beli v csúcsnak felel meg, és a G gráf v - t tartalmazó klikkjeiből áll . Ezeknek a klikkeknek mindegyik metszéspontjában v van, tehát H -ben alkotnak egy klikket . Az így megszerkesztett C család rendelkezik a Helly tulajdonsággal, mivel minden olyan C alcsaládnak , amelynek nem üres páronkénti metszéspontja van, meg kell felelnie egy G -beli klikknek, amely kiterjeszthető egy olyan maximális klikkre, amely az alcsalád metszéspontjához tartozik [2] .
Ezzel szemben, ha H -nak van egy Helly C klikkcsaládja, amely lefedi H minden élét , akkor ez egy K ( G ) klikkgráf G -re , amelynek csúcsai H csúcsainak és C elemeinek diszjunkt uniója . Ennek a G gráfnak van éle a C -beli minden nem üres metszéspontú klikkpárhoz, valamint minden H -beli csúcspárhoz és egy C -beli klikkhez, amely ezt tartalmazza. Ez a gráf azonban nem tartalmaz olyan éleket, amelyek összekötik a H csúcspárjait . Ebben a G gráfban a maximális klikkek a H gráf egy csúcsából állnak , és a C - ből származó összes klikk tartalmazza azt, és metszésponti gráfjuk izomorf a H gráfhoz [2] .
Ez a leírás azonban nem vezet hatékony algoritmusokhoz – az a probléma, hogy felismerjük, hogy egy adott gráf klikk gráf -e, NP-teljes [4] .