jac

MO417 - Questão para a prova oral

Número:

Enunciado: Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V. Sua bipartição pode ser definida pela paridade das distâncias de todos os vértices em relação a um vértice s escolhido arbitrariamente: o conjunto U consiste dos vértices a uma distância par de s e o conjunto V consiste dos vértices a uma distância ímpar de s. Para calcular as distâncias dos vértices em relação a s pode-se aplicar a busca em largura.

Dado o grafo abaixo determine quais vértices pertencem a U e quais pertencem a V.

a) U={2,4,6} e V={1,3,5}

b) U={1,3,6} e V={2,4,5}

c) U={1,4,5,6} e V={2,3}

d) U={1,3,4,5} e V={2,6}

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo