Autor Tema: Cobertura de vértices de un grafo bipartito

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

06 Diciembre, 2019, 04:45 am
Leído 857 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Sea \( G \) un grafo bipartito con bipartición \( U \) y \( W. \) Sea \( \{X,X'\} \) una bipartición de \( U \) y \( \{Y,Y'\} \) una biparticion de \( W. \) Suponga que el conjunto \( N(X):=\displaystyle\bigcup_{x\in X}N(x)\subseteq Y \). Demuestre que \( Y\cup X' \) es una cobertura de vértices de \( G. \)
"Haz de las Matemáticas tu pasión".

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

Luis Fuentes

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

Sea \( G \) un grafo bipartito con bipartición \( U \) y \( W. \) Sea \( \{X,X'\} \) una bipartición de \( U \) y \( \{Y,Y'\} \) una biparticion de \( W. \) Suponga que el conjunto \( N(X):=\displaystyle\bigcup_{x\in X}N(x)\subseteq Y \). Demuestre que \( Y\cup X' \) es una cobertura de vértices de \( G. \)

Entiendo que \( N(X) \) es el conjunto de vértices vecinos de \( X \), es decir, vértices unidos por una arista a alguno de \( X \).

Por ser una grafo bipartito toda arista une vértices de \( U \) con vértices de \( W \).

Sea \( e \) una arista, dado que \( U=X\cup X' \) y la arista tiene un vértice \( U \):

- O bien \( e \) tiene algún extremo en \( X' \),
- O bien \( e \) tiene un extremo en \( X \). Pero entonces su otro extremo es un vecino de \( X \) y por hipótesis está en \( Y. \)

Es decir hemos probado que toda arista tiene un extremo en \( X' \) ó en \( Y \); por tanto \( X'\cup Y \) es una cobertura de vértices.

Saludos.