Autor Tema: Conjunto independiente maximal 2

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

04 Noviembre, 2019, 03:02 am
Leído 855 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Encuentre un conjunto independiente maximo en el \( k \)-cubo.

Hola, sabemos que un conjunto es independiente si \( \forall u,v\in X \), se tiene que \( \{u,v\}\notin E. \)
"Haz de las Matemáticas tu pasión".

04 Noviembre, 2019, 11:27 am
Respuesta #1

Luis Fuentes

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

Encuentre un conjunto independiente maximo en el \( k \)-cubo.

Hola, sabemos que un conjunto es independiente si \( \forall u,v\in X \), se tiene que \( \{u,v\}\notin E. \)

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 \( k \)-cubo es \( 2^{k-1} \). Nota que dad un \( k \)-cubo podemos considerar los \( k-1 \)-cubos dados por los vertices:

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

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

Saludos.