08 Abril, 2020, 11:48 *
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: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Grafo bipartito  (Leído 196 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.108



Ver Perfil WWW
« : 27 Octubre, 2019, 18:13 »

Sea [texx]G[/texx] un grafo bipartito con bipartición [texx]U[/texx] y [texx]W[/texx] tal que [texx]\left |{U}\right |\ge \left |{W}\right |.[/texx] ¿Es verdad que [texx]\alpha(G)=\left |{U}\right |[/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 : 28 Octubre, 2019, 03:57 »

Hola

Sea [texx]G[/texx] un grafo bipartito con bipartición [texx]U[/texx] y [texx]W[/texx] tal que [texx]\left |{U}\right |\ge \left |{W}\right |.[/texx] ¿Es verdad que [texx]\alpha(G)=\left |{U}\right |[/texx]?

Entiendo que [texx]\alpha(G)[/texx] es el máximo número de vértices no adyacentes dos a dos posible (el número de independencia del grafo).

Entonces en tal grafo bipartito el conjunto [texx]U[/texx] es claramente de vértices independientes luego [texx]\alpha(G)\geq \left |{U}\right |[/texx].

Pero, ojo, podría haber un conjunto más grande. Por ejemplo si [texx]W[/texx] tiene algún vértice de grado cero. Así que la igualdad no tiene porque ser cierta.

Saludos.
En línea
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.108



Ver Perfil WWW
« Respuesta #2 : 08 Diciembre, 2019, 23:26 »

Hola

Sea [texx]G[/texx] un grafo bipartito con bipartición [texx]U[/texx] y [texx]W[/texx] tal que [texx]\left |{U}\right |\ge \left |{W}\right |.[/texx] ¿Es verdad que [texx]\alpha(G)=\left |{U}\right |[/texx]?

Entiendo que [texx]\alpha(G)[/texx] es el máximo número de vértices no adyacentes dos a dos posible (el número de independencia del grafo).

Entonces en tal grafo bipartito el conjunto [texx]U[/texx] es claramente de vértices independientes luego [texx]\alpha(G)\geq \left |{U}\right |[/texx].

Pero, ojo, podría haber un conjunto más grande. Por ejemplo si [texx]W[/texx] tiene algún vértice de grado cero. Así que la igualdad no tiene porque ser cierta.

Saludos.

Muchas Gracias, entonces la igualdad no es cierta en general. No me queda claro el ejemplo que pones, puedes explicarlo mejor?
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 #3 : 09 Diciembre, 2019, 04:21 »

Hola

Muchas Gracias, entonces la igualdad no es cierta en general. No me queda claro el ejemplo que pones, puedes explicarlo mejor?

No me cansaré de insistir: deberías de esforzarte tu primero en concretar más tu duda. ¿Qué has entendido del ejemplo?¿qué no has entendido?¿has dibujado algún grafo bipartito en las condiciones en que te he indicado, con un vértice de grado cero en [texx]W[/texx]?.

Observa este: los puntos azules son los vértices de [texx]U[/texx] y los rojos de [texx]W[/texx]. ¿Qué conclusión sacas?.



Saludos.

* bipartitioindep.jpg (15.45 KB - descargado 10 veces.)
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!