Diferencia entre revisiones de «Grafo complemento»

En [[teoría de grafos]], el '''grafo complemento''' o '''complementario''' de un [[grafo]] es otro grafo, con el mismo conjunto de [[vértice (teoría de grafos)|vértices]] del original, y tal que dos vértices delestán nuevoconectados grafopor sonuna [[arista (teoría de grafos)|adyacentesarista]] [[bicondicional|si y solo si]] noesa sonarista no adyacentesexiste en el primero.<ref name=WF13.c4>{{harvsp|Wasserman|Faust|2013|loc=«Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.}}</ref> Para obtener el complemento de un grafo, se deben completar todas las aristas faltantes para hacerlo [[grafo completo|completo]], y quitar todas las aristas del grafo ''G'' original. Este concepto no debe confundirse con el del [[complemento de un conjunto]], pues solo se complementan las aristas.

== ConstrucciónDefinición formal ==

Dado un grafo ''<math>G:=(V,E)''</math>, con ''<math>V''</math> su conjunto de vértices, <math>n=|V|</math>, y ''<math>E''</math> su conjunto de aristas o arcos, el '''grafo complemento''' de ''<math>G'',</math> ''es el grafo <math>G':=(V',E')'', está</math> dadodefinido por:

* ''<math>V' '' = ''V''</math>, y

* Para un [[clique]] <math>K^n:E'=(V_KE_K\setminus E</math>, donde <math>E_K)</math> es el conjunto de vértices del [[grafo completo]] <math>n K_n= |(V|, E_K)</math> vértices,.