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

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

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

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

Ако је дат граф са чворовима и гранама , његов комплемент , се конструише на следећи начин:

  • и
  • за клику од чворова, важи .