Complement de grafic

Complementul unui grafic ( graf invers ) este un grafic care are același set de vârfuri ca și graficul dat , dar în care două vârfuri necoincidente sunt adiacente dacă și numai dacă nu sunt adiacente în .

Formal, pentru un graf simplu și  - mulțimea tuturor submulților de două elemente ale vârfurilor sale - complementul este definit ca o pereche  - un graf cu setul original de vârfuri și cu un set de muchii obținute din graficul complet prin eliminarea celor în graficul dat.

Complementul unui graf gol (conținând doar vârfuri și fără muchii) este un graf complet și invers. O mulțime independentă a unui grafic este o clică în complementul graficului și invers. Complementul oricărui graf fără triunghiuri nu conține gheare .

Un graf auto-complementar  este un graf izomorf cu complementul său. Cografele sunt definite ca grafice care pot fi construite dintr-un singur punct printr-o operație de unire și complement fără legătură. Cografele formează o familie de grafuri autocomplementare — complementul oricărui cograf este un alt cograf (posibil diferit de cel original).

Literatură