Graph AlgorithmsEuler PathSlide 3Euler Path AlgorithmSlide 5Euler Path Algorithm ExampleSlide 7Euler Path AnalysisHamiltonian Circuit ProblemGraph AlgorithmsMathematical Structures for Computer ScienceChapter 6Copyright © 2006 W.H. Freeman & Co. MSCS Slides Graph AlgorithmsSection 6.2 Euler Path and Hamiltonian Circuit 2Euler PathDEFINITION: EULER PATH An Euler path in a graph G is a path that uses each arc of G exactly once.We want to find if an Euler path exists in graph G.Whether an Euler path exists in a given graph hinges on the degrees of its nodes.A node is even if its degree is even and odd if its degree is odd.THEOREM ON ODD NODES IN A GRAPH The number of odd nodes in any graph is even.Section 6.2 Euler Path and Hamiltonian Circuit 3Euler PathTHEOREM ON EULER PATHSAn Euler path exists in a connected graph if and only if there are either no odd nodes or two odd nodes. For the case of no odd nodes, the path can begin at any node and will end there; for the case of two odd nodes, the path must begin at one odd node and end at the other.The theorem on Euler paths is actually an algorithm to determine if an Euler path exists on an arbitrary connected graph.We make the simplifying assumption that the graph has no loops. If G has loops, we remove them and call the graph H. If H has an Euler path, then so does G, and vice versa.Section 6.2 Euler Path and Hamiltonian Circuit 4Euler Path AlgorithmIn the Euler Path algorithm, the input is a connected graph represented by an n  n adjacency matrix A.The algorithm counts the number of nodes adjacent to each node and determines whether this is an odd or an even number.If there are too many odd numbers, an Euler path does not exist.The variable total keeps track of the number of odd nodes found in the graph.The degree of any particular node, degree, is found by adding the numbers in that node’s row of the adjacency matrix.The function odd results in a value “true” if and only if the argument is an odd integer.Section 6.2 Euler Path and Hamiltonian Circuit 5Euler Path AlgorithmALGORITHM EulerPathEulerPath (n  n matrix A)//Determines whether an Euler path exists in a connected graph with//no loops and adjacency matrix A total = 0 i = 1 while total  2 and i  n do degree = 0 for j = 1 to n do degree = degree + A[i, j ] //find degree of node i (*) end for if odd(degree) then total = total + 1 //another odd degree node found end if i = i + 1 end while if total > 2 then write (“No Euler path exists”) Else write (“Euler path exists”) end ifend EulerPathSection 6.2 Euler Path and Hamiltonian Circuit 6Euler Path Algorithm ExampleGiven the following adjacency matrix:When the algorithm first enters the while loop, total is 0 and i is 1, then degree is 0. Within the for loop, the values of row 1 of the adjacency matrix are added in turn to degree, resulting in a value for degree of 3.The odd function applied to degree returns the value “true,” so the value of total is increased from 0 to 1; one node of odd degree has been found.Section 6.2 Euler Path and Hamiltonian Circuit 7Euler Path Algorithm ExampleThen i is incremented to 2.Neither the bounds on total nor the bounds on the array size have been exceeded, so the while loop executes again for row 2.degree is found to be odd, so the value of total is changed to 2.When the while loop is executed for row 3 of the array, the value of degree is even (4), so total does not change, and the while loop is executed again with i = 4.Row 4 again produces an odd value for degree, so total is raised to 3.This terminates the while loop. There is no Euler path because the number of odd nodes exceeds 2.Section 6.2 Euler Path and Hamiltonian Circuit 8Euler Path AnalysisIn the worst case, the while loop in the algorithm is executed n times, once for each row.Within the while loop, the for loop is executed n times, once for each column.EulerPath is therefore an Θ(n2) algorithm in the worst case.Section 6.2 Euler Path and Hamiltonian Circuit 9Hamiltonian Circuit ProblemA Hamiltonian circuit is a cycle using every node of the graph.A Hamiltonian circuit requires that each and every node of the graph be visited once and only once (except for the start node, which is also the end node)There can be unused arcs but no arc can be used more than once.No efficient algorithm has ever been found to determine if a Hamiltonian circuit