Dopełnienie grafu: Różnice pomiędzy wersjami

'''Dopełnieniem grafu''' (ang. complement of graph) <math>G</math> nazywamy [[graf (matematyka)|graf]] <math>\overline{G}</math>, zawierający te same wierzchołki co graf <math>G</math>, natomiast pomiędzy wierzchołkami grafu <math>\overline{G}</math> istnieje krawędź wtedy i tylko wtedy gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie <math>G</math>.

 

Dla grafu <math>G(V_G, E_G)</math> o wierzchołkach <math>V_G</math> i krawędziach <math>E_G</math>, jego dopełnieniem określa się graf <math>H(V_H, E_H)</math> taki, że:

* <math>V_H = V_G</math> i

* <math>E_H = E_K \setminus E_G</math>, gdzie <math>K^n(V_K, E_K)</math> jest [[Graf pełny|grafem pełnym]] rozmiaru <math>n = |V_G|</math>, <math>V_K=V_G</math>.

 

* Dopełnieniem n-wierzchołkowego grafu regularnego stopnia k jest n-wierzchołkowy graf regularny stopnia n-k-1.

* Dopełnieniem grafu pełnego jest graf nie zawierający krawędzi.

]]

 

* [[Teoria grafów]]

* [[graf (matematyka)]]