- Grafo complemento
-
Un grafo de Petersen (a la izquierda) y su grafo complemento (a la derecha).En teoría de grafos, el complemento o inverso de un grafo G:=(V,E) es un grafo G':=(V,E'), con el mismo conjunto de vértices y tal que dos vértices de G' son adyacentes si y sólo si no son adyacentes en G. Para obtener el complemento de un grafo, se deben completar todas las aristas faltantes para hacerlo completo, y quitar todas las aristas del grafo G original. Este concepto no debe confundirse con el del complemento de un conjunto, pues sólo se complementan las aristas.
Se llama grafo autocomplementario a aquél que es isomorfo a su propio complemento.
Construcción formal
Dado un grafo G:=(V,E), con V su conjunto de vértices y E su conjunto de aristas o arcos, el grafo complemento de G, G':=(V',E'), está dado por:
- V' = V, y
- Para un clique Kn: = (VK,EK) de n = | V | vértices,
.
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-Completitud.
Referencias
- Bondy, John Adrian; Murthy, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html, páginas 6 y 29.
- Diestel, Reinhard (2005), Graph Theory (3a edición), Springer, ISBN 3-540-26182-6. Edición electrónica, página 4.
Categoría:- Familias de grafos
Wikimedia foundation. 2010.
