Report

5.4 Graph Models (part I – simple graphs) • Graph is the tool for describing real-life situation. • The process of using mathematical concept to solve real-life problems is called modeling Example: Using graph to represent the picture of the seven bridges of Konigsberg Vertices represent the banks and lands Edges represent the bridges Draw a graph to model this city More examples: (textbook, page 170: Bridges of Madison County) (www.coursecompass.com, #23, 25) 5.5 Euler’s Theorems • Who is Leonhard Euler? Euler’s Theorem 1 a) If a graph has any odd vertices, then it cannot have an Euler Circuit b) If a graph is connected and every vertex is an even vertex, then it has at least one Euler circuit • Euler’s Theorem 2 a) If a graph has more than two odd vertices then it cannot have an Euler path b) If a graph is connected and has exactly two odd vertices, then it has an Euler path, starting at one odd vertex and ending at the other. Determine if the graph has an Euler circuit, an Euler path or neither of these No, neither Yes, an Euler path Yes, an Euler circuit • Euler’s Theorem 3 a) The sum of the degrees of all the vertices of a graph equals twice the number of edges. b) A graph always has an even number of odd vertices 5.4 Graph Models (part II –graphs) Model for a security guard Model for the mail carrier • Look at page 177: Models for security guard and mail carrier 5.6 Fleury’s Algorithm Algorithm on finding an Euler’s path or circuit • Use a vertex to start (make sure you choose the odd vertex if the graph has an Euler path) • Do not go through any bridge of the untraveled part of the graph unless it is the only way you can go A B C D F E 1 2 3 4 5 6 7 8 1 10 18 2 3 11 19 4 12 20 5 6 13 21 7 14 22 8 9 15 16 23 24 17 25 26 27