Discrete Mathematical Structures by Pearson

10-46 Discrete Mathematical Structures

Solution: Applying BFS, the vertex v

1

is labelled as 0 for j = 0. Then the vertices v

2

and v

3

(adjacent vertices of v

1

) are labelled j = j + 1 = 0 + 1 = 1. The vertices v

4

, v

5

and v

6

are labelled

j = j + 1 = 1 + 1 = 2. The vertices v

7

and v

8

are labelled 2 + 1 = 3. Since v

8

is labelled 3, the length

of a shortest path from v

1

to v

8

is 3.

Now using back-tracking algorithm, since λ(v

8

) = 3, we start with j = 3 and v

j

= v

8

. The

vertices adjacent to v

8

are v

5

and v

6

. Hence, we choose v

5

or v

6

with λ(v

5

) = 2 and assign v

5

= 2.

Next we choose v

3

adjacent to v

5

with λ(v

3

) = 1 and assign v

3

= 1. Finally, we take ...