Faceți clic pe grafic

Graficul clică al unui grafic nedirecționat G este un alt grafic K ( G ) care reprezintă structura clică a graficului G .

Graficele clicurilor au fost discutate cel puțin din 1968 [1] , iar o descriere a graficelor clicurilor a fost dată în 1971 [2] .

Definiție

O clică a unui grafic G este o mulțime X de vârfuri ale unui grafic G care are proprietatea că orice pereche de vârfuri distincte ale lui X este conectată printr-o muchie în G . Clica maximă a lui G este o clică X de vârfuri a lui G , astfel încât să nu existe nicio clică a vârfurilor Y a lui G care să conțină toate vârfurile lui X plus cel puțin un alt vârf.

Având în vedere un grafic G , graficul său clică K ( G ) este un grafic astfel încât

Note

Proprietăți

Un grafic H este un grafic de clică K ( G ) al altui grafic dacă și numai dacă există o mulțime C de clicuri în H a cărei mulțime acoperă toate marginile lui H astfel încât C formează o familie Helly . Aceasta înseamnă că dacă S este o submulțime a lui C cu proprietatea că oricare două elemente ale lui S au o intersecție nevide, atunci S trebuie să aibă în sine o intersecție nevidă. Cu toate acestea, clicurile din setul C nu trebuie să fie clicuri maxime [2] .

Dacă H  = K ( G ), se poate construi o familie C de acest tip în care fiecare clică din C corespunde unui vârf v din G și este formată din clicuri ale graficului G care conține v . Aceste clicuri au toate v la intersecția lor, deci formează o clică în H . Familia C astfel construită are proprietatea Helly, deoarece orice subfamilie C cu o intersecție perechi nevidă trebuie să corespundă unei clicuri în G care poate fi extinsă la o clică maximă care aparține intersecției subfamiliei [2] .

În schimb, dacă H are o familie de clicuri Helly C care acoperă toate muchiile lui H , atunci este un grafic de clică K ( G ) pentru G , ale cărui vârfuri sunt uniunea disjunsă a vârfurilor lui H și elementelor lui C . Acest grafic G are o muchie pentru fiecare pereche de clicuri din C cu o intersecție nevidă și pentru fiecare pereche de vârfuri din H și o clică din C care o conține. Totuși, acest grafic nu conține muchii care conectează perechi de vârfuri în H . Clicile maxime din acest grafic G constau dintr-un vârf al graficului H cu toate clicurile din C care îl conțin, iar graficul lor de intersecție este izomorf cu graficul H [2] .

Totuși, această descriere nu conduce la algoritmi eficienți - problema recunoașterii dacă un graf dat este un graf clic este NP-complet [4] .

Vezi și

Note

  1. Hamelink1968 , p. 192–197.
  2. 1 2 3 4 Roberts și Spencer, 1971 , p. 102–108.
  3. Szwarcfiter, Bornstein, 1994 , p. 331–336.
  4. Alcón, Faria, de Figueiredo, Gutierrez, 2009 , p. 2072–2083.

Literatură

Link -uri