CGU-NET | UGC NET CS 2015 Dic – II | Pregunta 4

Considere el gráfico que se muestra a continuación:

Los dos conjuntos distintos de vértices, que hacen que el gráfico sea bipartito, son:

(A) (v1, v4, v6); (v2, v3, v5, v7, v8)
(B) (v1, v7, v8); (v2, v3, v5, v6)
(C) (v1, v4, v6, v7); (v2, v3, v5, v8)
(D) (v1, v4, v6, v7, v8); (v2, v3, v5)

Respuesta: (C)
Explicación: un gráfico bipartito es un gráfico cuyos vértices se pueden dividir en dos conjuntos independientes, U y V, de modo que cada borde (u, v) conecta un vértice de U a V o un vértice de V a U. En otras palabras, para cada arista (u, v), u pertenece a U y v a V, o u pertenece a V y v a U. También podemos decir que no hay arista que conecta vértices de un mismo conjunto.
(v1, v4, v6, v7);
(v2, v3, v5, v8) es un conjunto de vértices de gráfico bipartito.
Entonces, la opción (C) es correcta.

Cuestionario de esta pregunta