Question

b) Given the following graph: AC ACE CEG C- ACE Is this graph has an Euler cycle? Justify your answer. 12 marks] i) Use the breadth first search algorithm to find a spanning tree in the above h. Assume vertex A is the root and the vertices are ordered Show clearly each step of how the algorithm is performed and present your answer in a table with three columns, the first column is the number of steps, the second column is the queue for the search algorithm and the third column is the edges of the resulting spanning tree. grap alphabetically [4 marks]

Answer 1

i)

Note:- A path in a multigraph G that includes exactly once all the edges of G and has different first and last vertices is called Euler Path. If this path has the same initial and terminal vertices, we call it an Euler Circuit/Cyle. And a neccesary and sufficent condition for Euler Cycle in a Graph is that every vertices should have an even degree. Where degree is the edges leaving a vertex.

Here in the given graph: The degree of vertices D,A and B are 2 but degree is 3 for E and C. hence there isnt an Euler Cycle in the given graph.