Grafo complemento

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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[editar]

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 K^n:=(V_K, E_K) de n = |V| vértices,
E' = E_K \setminus E.

Aplicaciones[editar]

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[editar]