Autor Tema: Cobertura de vértices mínima en el k-cubo

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

06 Diciembre, 2019, 04:25 am
Leído 859 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 una cobertura de veértices mínima en el \( k \)-cubo.

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

09 Diciembre, 2019, 02:19 pm
Respuesta #1

Luis Fuentes

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

Encuentre una cobertura de veértices mínima en el \( k \)-cubo.

El \( k \)-cubo tiene \( 2^k \) vértices y \( 2^{k-1}k \) aristas.

Los vértices pueden representarse como:

\( V=\{(x_1,x_2,\dots,x_k)|x_i\in \{0,1\}\} \)

Las aristas unen pares de vértices que tan solo difieren en una coordenada. Cada vértice tiene grado \( k \), es decir, está unido a \( k \)-aristas.

Una cobertura de vértices es un conjunto de vértices de manera que toda arista incide el alguno de ellos.

Dado que cada vértice tiene grado \( k \) y hay \( 2^{k-1}k \) aristas, una cobertura tiene que tener en este caso al menos:

\( \dfrac{2^{k-1}k}{k}=2^{k-1} \) vértices.

Comprueba que el conjunto de vértices:

\( V_+=\{(x_1,x_2,\dots,x_k)\in V|x_1+x_2+\ldots+x_k\textsf{ es par}\} \)

es una cobertura del \(  \)k-cubo.

Si no te sale no te limites a un: "no lo entiendo, explícalo mejor". Explica que has intentado y la dificultad concreta que encuentras.

Saludos.