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!
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
0
