Edición de «Grafo complemento»

[[Archivo:Complement_graph_sample.png|thumb|El [[grafo de Petersen]] (a la izquierda) y su grafo complemento (a la derecha).]]
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 están conectados por una [[arista (teoría de grafos)|arista]] [[bicondicional|si y solo si]] esa arista no existe 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 pueden completar todas las aristas faltantes para hacerlo [[grafo completo|completo]], y quitar todas las aristas del grafo ''G'' original. Note que esta definición aplica tanto para [[grafo dirigido|grafos dirigidos]] como [[grafo no dirigido|no dirigidos]].<ref name=WF13.c4/> Este concepto no debe confundirse con el del [[complemento de un conjunto]], pues solo se complementan las aristas.

Por definición, los conjuntos de aristas de un grafo y su grafo complemento forman una [[partición de un conjunto|partición]]; es decir, su intersección es [[conjunto vacío|vacía]] y su unión es el conjunto de todas las aristas posibles que tendría el grafo completo del mismo número de vértices.<ref name=WF13.c4/>

Se llama [[grafo autocomplementario]] a aquel que es [[isomorfismo de grafos|isomorfo]] a su propio complemento.

Este tipo de grafos no debe confundirse con el [[grafo inverso]]. Si dos vértices de un grafo no están conectados por aristas, el grafo inverso conservará dicha ausencia de aristas, mientras que el grafo complemento los conectará con aristas en ambos sentidos. Asimismo, si dos vértices de un grafo dirigido están conectados en ambos sentidos, el grafo inverso conservará dichas aristas, mientras que el grafo complemento eliminará las aristas entre ambos vértices.<ref name=WF13.c4/>

== Definició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')</math> definido por:

* <math>V'=V</math>, y
* <math>E'=E_K\setminus E</math>, donde <math>E_K</math> es el conjunto de aristas del [[grafo completo]] <math>K_n=(V, E_K)</math>.

== Aplicaciones ==

El grafo complemento se utiliza en muchos ámbitos de la teoría de grafos y en demostraciones, tales como la [[Teoría de Ramsey]] o diferentes reducciones para pruebas de [[NP-completo|NP-Completitud]].

== Véase también ==
* [[Grafo inverso]]

== Referencias ==
{{listaref}}

== Bibliografía ==
* {{cita libro |apellido1=Wasserman |nombre1=Stanley |apellido2=Faust |nombre2=Katherine |título=Análisis de redes sociales: Métodos y aplicaciones |editorial=Centro de Investigaciones Sociológicas |ubicación=Madrid |año=2013 |año-original=1994 |oclc=871814053 |isbn=978-84-7476-631-8}}

{{Control de autoridades}}
[[Categoría:Familias de grafos|Complemento]]