Java - Saber si un grafo es bipartido

   
Vista:

Saber si un grafo es bipartido

Publicado por Manuel q (1 intervención) el 29/05/2010 15:57:59
Hola, estoy intentando hacer el siguiente ejercicio.

Un grafo no dirigido G = (V, A), se dice que es bipartido si V se puede
particionar en dos subconjuntos V1 y V2, de manera que para toda arista (v,
w) de A, el nodo v pertenezca a uno de los conjuntos (V1 o V2) y w
pertenezca a la otra partición. Proporcionar un algoritmo con tiempo O(n+a)
para comprobar si un grafo es bipartido o no.

Alguien me lo peude mandar? no consigo hacerlo. Gracias!
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder