Reference no: EM1348318

Question 1: Correctly match each of the following descriptions to a graph below by inserting the letter of the description that correctly describes the graph in the open box under the graph.  

 (A) The graph has both an Euler circuit and a Hamilton circuit. 

 (B) The graph has an Euler circuit but does not have a Hamilton circuit. 

 (C) The graph does not have an Euler circuit but does have a Hamilton circuit. 

 (D) The graph does not have an Euler circuit and does not have a Hamilton circuit. 

Question 2. A graph G has a set of vertices V = {1, 2, 3, 4, 5, 6, 7} and a set of edges  E = {(1,4), (1,5), (2,5), (2,6), (3,2), (3,4), (4,5) (4,6), (3,7), (5,7)}. Draw the  graph G. 

Question 3: Construct the incidence and adjacency matrices for each of the following graphs.

Question 4: Consider the adjoining connected graph consisting of 8 nodes and 10 edges. 

Answer the following questions regarding this graph. 

 (a) Does this graph contain an Euler circuit? If  your answer is yes, describe the circuit. If your  answer is no, explain why there is no Euler circuit.  

 (b) Does this graph contain an Euler path? If  your answer is yes, describe the path. If your answer is no, explain why there is  no Euler path.  

 (c) Does this graph contain a Hamilton circuit? If your answer is yes, describe  the circuit. If your answer is no, explain why there is no Hamilton circuit. 

Question: 5. The adjoining diagram is a graph with five nodes (or vertices) labelled A, B, C, D and E. The lengths of the edges joining the nodes are shown on the graph.  

 a) Find all Hamilton paths going from node A to node B.  

 b) Find the lengths of each of the Hamilton paths from node A to node B. 

Question 6. Consider the following digraphs. Draw their corresponding incidence matrices.