Autor Tema: Determinar si los grafos son bipartitos

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

09 Diciembre, 2014, 11:05 pm
Leído 2662 veces

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Debo determinar si los grafos presentados en el archivo adjunto son bipartitos. En cuánto al primer grafo aun no logro determinar si lo es o no.



El segundo lo resolví de esta manera. Determiné que los vértices tienen grado par. Ahora, supongamos que el grafo es bipartito. Es decir, se pueden elegir dos conjuntos de vértices \( U,V \) tales que \( U\cup V=N \) y \( U\cap V=\emptyset \). Como la cantidad de vértices es impar, supongamos sin pérdida de generalidad que \( |U|>|V| \).

En este caso, como los vértice en \( U \) tienen grado par y \( |U|>|V| \) se tiene que al menos un vértice en \( V \) tiene grado mayor que 2. Lo cual es una contradicción.

Por tanto, \( G_2 \) no es bipartito. ¿Está bien?


El primero acepto ayuda.

09 Diciembre, 2014, 11:57 pm
Respuesta #1

elcristo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,193
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

Sí, está bien, pero también puedes argumentar de la siguiente forma:

Para el 2, como hay un ciclo de longitud impar, entonces el grafo no puede ser bipartito.

Este mismo argumento te sirve para el primero también. Coges a-b-g-a, es un ciclo, tiene longitud 3, luego el grafo ya no puede ser bipartito.

Para el caso 2 empiezas a recorrer todas las puntas de la estrella y acabas llegando al mismo punto, como son 7, ciclo longitud impar, no bipartito.

Saludos.

10 Diciembre, 2014, 12:03 am
Respuesta #2

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Hola, gracias. No sabía que un grafo cíclico con camino de longitud impar no es bipartito. Ya lo busco para argumentar mejor.   :)

10 Diciembre, 2014, 06:37 pm
Respuesta #3

elcristo

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,193
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

La argumentación a esto es muy sencilla.

Si es bipartito significa que existen 2 subconjuntos, X e Y tal que las aristas sólo conectan vértices de X con vértices de Y. Entonces, evidentemente, el grafo es 2-colorable. Es decir, se puede pintar con 2 colores, X de uno e Y de otro. Sin embargo, si tenemos un ciclo de longitud impar, coloreamos el primer vértice de rojo por ejemplo, el segundo de negro, el tercero, por ser vecino del segundo, tiene que tener color rojo (si no, no sería 2-colorable) sin embargo, si lo pintamos rojo, es vecino del primero, así que nos quedan 2 colores unidos por la misma arista, lo cual no puede ser en una coloración, luego el grafo no puede ser bipartito.

Esa es otra forma de ver si un grafo es bipartito o no, ver si se puede pintar de 2 colores.

Saludos.