10 Abril, 2020, 05:44 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Mostrar que X es un clique ssi X es independiente  (Leído 118 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.110



Ver Perfil WWW
« : 06 Diciembre, 2019, 00:19 »

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

Hola, sabemos que [texx]X[/texx] es un clique si [texx]\forall u,v\in X, \{u,v\}\in E[/texx].

En línea

"Haz de las Matemáticas tu pasión".
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 09 Diciembre, 2019, 16:48 »

Hola

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

Hola, sabemos que [texx]X[/texx] es un clique si [texx]\forall u,v\in X, \{u,v\}\in E[/texx].

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

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!