04 Abril, 2020, 02:51 *
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: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Cobertura de vértices de un grafo bipartito  (Leído 115 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.105



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

Sea [texx]G[/texx] un grafo bipartito con bipartición [texx]U[/texx] y [texx]W.[/texx] Sea [texx]\{X,X'\}[/texx] una bipartición de [texx]U[/texx] y [texx]\{Y,Y'\}[/texx] una biparticion de [texx]W.[/texx] Suponga que el conjunto [texx]N(X):=\displaystyle\bigcup_{x\in X}N(x)\subseteq Y[/texx]. Demuestre que [texx]Y\cup X'[/texx] es una cobertura de vértices de [texx]G.[/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, 10:30 »

Hola

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

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

Por ser una grafo bipartito toda arista une vértices de [texx]U[/texx] con vértices de [texx]W[/texx].

Sea [texx]e[/texx] una arista, dado que [texx]U=X\cup X'[/texx] y la arista tiene un vértice [texx]U[/texx]:

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

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

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!