Комплемент графа

Из Википедије, слободне енциклопедије
Петерсенов граф (лево), и његов комплемент (десно).

У теорији графова, комплемент или инверз графа G је граф H са истим скупом чворова, такав да су два чвора из H суседна ако и само ако та два чвора нису суседна у графу G. То јест, комплемент графа се добија тако што се додају све недостајуће гране, а уклоне оне које су већ биле у графу. Овде се не ради о комплементу скупа графа; само се гране комплементирају.

Формална конструкција[уреди]

Ако је дат граф G(V_G, E_G) са чворовима V_G и гранама E_G, његов комплемент H(V_H, E_H), се конструише на следећи начин:

  • V_H = V_G и
  • за клику K^n(V_K, E_K) од n = |V_G| чворова, важи E_H = E_K \setminus E_G.