Autor Tema: Grafo bipartito

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

27 Octubre, 2019, 10:13 pm
Leído 510 veces

Julio_fmat

  • Héroe
  • Mensajes: 2,235
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Sea \( G \) un grafo bipartito con bipartición \( U \) y \( W \) tal que \( \left |{U}\right |\ge \left |{W}\right |. \) ¿Es verdad que \( \alpha(G)=\left |{U}\right | \)?
"Haz de las Matemáticas tu pasión".

28 Octubre, 2019, 07:57 am
Respuesta #1

Luis Fuentes

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

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

Entiendo que \( \alpha(G) \) 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 \( U \) es claramente de vértices independientes luego \( \alpha(G)\geq \left |{U}\right | \).

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

Saludos.

09 Diciembre, 2019, 03:26 am
Respuesta #2

Julio_fmat

  • Héroe
  • Mensajes: 2,235
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola

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

Entiendo que \( \alpha(G) \) 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 \( U \) es claramente de vértices independientes luego \( \alpha(G)\geq \left |{U}\right | \).

Pero, ojo, podría haber un conjunto más grande. Por ejemplo si \( W \) 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?
"Haz de las Matemáticas tu pasión".

09 Diciembre, 2019, 08:21 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,534
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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 \( W \)?.

Observa este: los puntos azules son los vértices de \( U \) y los rojos de \( W \). ¿Qué conclusión sacas?.



Saludos.