Question

8. (Ufrj) A figura a seguir representa um grafo, isto é, umconjunto de pontos (nós) ligados por segmentos (arestas).Se X e Y são dois nós do grafo, designamos por d(X, Y) omenor número de arestas necessárias para ir de X a Y ,percorrendo exclusivamente um caminho sobre as arestasdo grafo (assim, por exemplo, d(N, R) = 3).
a) Determine d(A, B).
b) Identifique os nós X e Y para os quais d(X, Y) é máximo.Nesse caso, quanto é d(X, Y)?

Answer 1

a)
O caminho mais curto para ir de A até B, tem que passar por M, O, J e B (4 nós), logo:
d(A,B) = 4

b)
O caminho de A até C passa por 6 nós: M,O, J, E, F, C, este é o d(x, y) máximo.
d(A,C) = 6

Answer 2

Olá!! Eu não entendi a letra b.

Se eu fizesse o caminho de A até C descrito abaixo

A - M - L - K - J - E - F - C

Eu teria d(A,C)= 7.

Então, essa não deveria ser a resposta?