Discrete Mathematics (Eng) Chapter 8 : Applications on Graph

Which of the following are problems we discussed last week. Those problems can apply the graph model and develop an algorithm to solve them .

• Minimum Spanning Tree

• Heuristic search

• Shortest Path

• Travelling salesman problem

Which are properties of graph that we found in Minimum Spanning Tree problem ?

• directed

• connected

• simple

• weighted

Which of the following are the name of algorithms for solving Minimum Spanning Tree.

• Kruskal's

• Prim's

• Dijkstra's

• Euclidean

Which statements are TRUE for Prim's algorithm

• Must sort all edge values by weight first

• The tree obtained at each step of the method is always a connected graph

• Do not select edges that create a cycle with the tree being constructed

• The choices of edges to select for MST are every unselected edge left in the graph.

How much is

(#of steps of Kruskal's algorithm * 100) +

the total weight of MST of this graph ?

ie. using 4 steps and weight = 15 -> 415

Which of the following is not the initialization for the Dijkstra's algorithm?

• d[i] = 0 for all node i

• d[s] = 0 for the source node s

• p[s] = 0

• Known[i] = FALSE for all node[i]

From the Dijkstra's table, which node is the source ?

From the Dijkstra's table, which node is the next s (the node to be considered) for the next step ?

From this Dijkstra's table, which of the following is NOT the shortest path we can derive.

• K-M-L

• L-N-O

• L-M-K-P

• L-M-K

• L-M-N