Autor Tema: Mostrar que X es un clique ssi X es independiente

0 Usuarios y 1 Visitante están viendo este tema.

06 Diciembre, 2019, 04:19 am
Leído 825 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre que \( X \) es un clique en un grafo \( G \) si y solo si \( X \) es un conjunto independiente en \( \overline{G} \). Demuestre entonces que \( \omega(G)=\alpha(\overline{G}). \)

Hola, sabemos que \( X \) es un clique si \( \forall u,v\in X, \{u,v\}\in E \).

"Haz de las Matemáticas tu pasión".

09 Diciembre, 2019, 08:48 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Demuestre que \( X \) es un clique en un grafo \( G \) si y solo si \( X \) es un conjunto independiente en \( \overline{G} \). Demuestre entonces que \( \omega(G)=\alpha(\overline{G}). \)

Hola, sabemos que \( X \) es un clique si \( \forall u,v\in X, \{u,v\}\in E \).

Simplemente, si  \( \{u,v\}\in E(G) \) entonces \( \{u,v\}\not\in E(\overline{G}) \) y por tanto que todo par de vértices de \( X \) este unido por una arista en \( G \) equivale a que todo par de vértices en \( X \) no está unido por ninguna arista en \( \bar G \), es decir, equivale a que \( X \) es un conjunto independiente en \( \bar G \).

Saludos.