Complemento de Gráfico

Considere un conjunto A y U denota el conjunto universal, entonces el complemento del conjunto A se puede encontrar por

Ac =U-A.

Pero, un grafo G(v, e) es un conjunto de vértices y aristas, ¿es posible encontrar el Complemento de un grafo? Esta pregunta se responde a continuación. 

Complemento de Gráfico

El complemento de un grafo G es un grafo G’ en el mismo conjunto de vértices que G tal que habrá una arista entre dos vértices (v, e) en G’, si y solo si no hay arista entre ( v, e) en G.

El complemento del gráfico G(v, e) se denota por G'(v, e’).

Nota : El número de vértices permanece sin cambios en el complemento del gráfico.

Ejemplo:

In the above example in graph G there is a edge between (a, d),(a, c),(a, d).
Complement of Graph G is G' having edges between (a, b),(b, c),(b, d). 

Propiedades del gráfico complementado

1. Si E es el conjunto de aristas del grafo G’ entonces E(G’)={ (u, v) | (u, v) ∉ E(G) }

2. La unión del grafo G y su complemento G’ darán un grafo completo (K _n ).

 

3. La intersección de dos gráficos complementarios no tiene bordes, también conocido como gráfico nulo

4. Si G es un grafo inconexo entonces su complemento G’ sería un grafo conexo.

5. El orden de un gráfico y su complemento son iguales. El orden del gráfico es el número de vértices en él.

Ejemplo :

El orden de un gráfico G en un conjunto de vértices viene dado por G={a, b, c, d, e} es el número de vértices en el gráfico G, es decir, 5.

6. El tamaño de un Gráfico y su complemento no pueden ser iguales. El tamaño de un gráfico es el número de aristas que tiene.

Ejemplo:

El tamaño de un gráfico G en el conjunto de aristas es G= {(b, d), (c, e) } es el número de aristas en el gráfico, es decir, 2.

Nota:

1. Si G es un grafo con aristas E y K _n que denotan el grafo completo, entonces el complemento del grafo G puede estar dado por

E(G') = E(Kn)-E(G).

2. La suma de las Aristas de un gráfico Complementario y el gráfico principal es igual al número de aristas en un gráfico completo, n es el número de vértices.

E(G')+E(G) = E(Kn) = n(n-1)÷2.

Preguntas de práctica:

Pregunta 1. Considere un gráfico G simple, donde E denota los bordes y V denota los vértices |E(G)|= 30, |E(G’)|= 36. Halle |V(G)|=?

Solución : 

        We know,
        E(G')+E(G)=E(Kn)=n(n-1)÷2.
        ⇒ 36+30=n(n-1)÷2
        ⇒ 66=n(n-1)÷2
        ⇒ 66×2=n2-n
        ⇒ n2-n-132=0
        ⇒ n2-12n+11n-132=0
        ⇒ n(n-12)+11(n-12)=0
        ⇒ (n-12)(n+11)=0
Therefore, n=12 and n=-11.
Since vertices cannot be negative
n=12.

Pregunta 2 . Considere un gráfico G simple, donde E denota las aristas y V denota los vértices |E(G)|= 12, |V(G)|= 8. Halle el número de aristas en el gráfico complementario |E(G’)|= ?.

Solución : 

       We know,
       E(G')+E(G)=E(Kn)=n(n-1)÷2.
       ⇒ E(G') + 12 =8(8-1)÷2      [here n denotes number of vertices, i.e. given 8]
       ⇒ E(G')+12 = 8(7)÷2
       ⇒ E(G')+12= 4×7
       ⇒ E(G')+12=28
       ⇒ E(G')=28-12
       ⇒ E(G')=16.