17/02/2020, 18:12:54 *
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: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Conjunto independiente maximal 2  (Leído 92 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.083



Ver Perfil WWW
« : 03/11/2019, 23:02:11 »

Encuentre un conjunto independiente maximo en el [texx]k[/texx]-cubo.

Hola, sabemos que un conjunto es independiente si [texx]\forall u,v\in X[/texx], se tiene que [texx]\{u,v\}\notin 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: 45.967


Ver Perfil
« Respuesta #1 : 04/11/2019, 07:27:54 »

Hola

Encuentre un conjunto independiente maximo en el [texx]k[/texx]-cubo.

Hola, sabemos que un conjunto es independiente si [texx]\forall u,v\in X[/texx], se tiene que [texx]\{u,v\}\notin E.[/texx]

Utiliza este ejercicio:

http://rinconmatematico.com/foros/index.php?topic=111112.msg439342;topicseen#msg439342

Prueba que cualquiera de los dos subconjuntos que dan al grafo estructura de grafo bipartito son un conjunto independiente máximo.

Que es independiente es obvio; para ver que es máximo, razona por inducción que el número máximo posible de vértices independientes en un [texx]k[/texx]-cubo es [texx]2^{k-1}[/texx]. Nota que dad un [texx]k[/texx]-cubo podemos considerar los [texx]k-1[/texx]-cubos dados por los vertices:

[texx]V_0=\{(a_1,a_2,\ldots,a_{n-1},0)\}[/texx]
[texx]V_1=\{(a_1,a_2,\ldots,a_{n-1},1)\}[/texx]

y cualquier conjunto maximal de vértices del [texx]k[/texx]-cubo intersecado con [texx]V_0[/texx] y [texx]V_1[/texx] no puede tener más vértices que el número máximo de vértices independientes en el [texx](k-1)[/texx]-cubo.

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!