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

Из Википедије, слободне енциклопедије

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

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

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

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