Graful complementar
Fie un graf neorientat.
Se numește graf complementar al lui un graf cu proprietatea că conține aceleași noduri (), iar conține toate muchiile care nu aparțin lui .
Cu alte cuvinte, graful complementar conține toate muchiile care nu apar în graful de referință (ne putem gândi la el ca fiind „graful opus”).
Un graf neorientat și complementarul său:
Toate (și doar) muchiile care nu apar în graful inițial apar în complementar.
Publicitate
Proprietățile grafului complementar
- suma muchiilor unui graf neorientat și ale complementarului său este (numărul maxim de muchii pentru un graf cu n noduri);
- un graf neorientat are un singur graf complementar;
- graful complet are complementar graful nul (și invers).