Chapter 8a - Graphs and Circuits PDF

CHAPTER 8. The Mathematics of Graph– Graphs and Euler Circuits Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1. define a graph; 2. describe...

CHAPTER 8. The Mathematics of Graph– Graphs and Euler Circuits Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1. define a graph; 2. describe some types and families of graphs; 3. find Euler paths and circuits; and 4. solve real-world problems involving Euler paths and circuits. challenge… The Konigsberg Problem Can you walk through each bridge exactly once?  challenge… The Konigsberg Problem Can you walk through each bridge exactly once? A 6 4 1 5 B D 2 3 7 C Historical background Leonard Euler (1707-1783) – American mathematician and logician introduced this formal definition of relation GRAPH THEORY is a branch of mathematics which illustrates and analyzes connections between objects. Applications of Graph Theory Biology and Genetics Urban Planning Finance and Stock Market Analysis Telecommunications Circuit Design  GRAPH is a set of points called vertices and line segments or curves called edges.  Two vertices are adjacent if they have a common edge.  Two edges are adjacent if they share a common vertex  A loop is an edge, the endpoints of which are the same vertex.  Multiple edges are two or more edges that are incident to the same two vertices. 1 𝑢 𝑎 loop 𝑒5 𝑒1 𝑦 𝑣 𝑒6 𝑒 5 𝑒7 2 𝑓 𝑒10 𝑏 6 𝑒4 𝑒8 𝑐 𝑒9 𝑥 𝑤 3 multiple 𝑑 4 𝑒3 edges 𝑮 𝑯 GRAPH is a set of points called vertices and line segments or curves called edges. Moreover, a graph is simple if it has no loops or multiple edges. 1 𝑢 𝑎 𝑒5 𝑒1 𝑦 𝑣 𝑒6 𝑒 5 𝑒7 2 𝑓 𝑒10 𝑏 6 𝑒4 𝑒8 𝑐 𝑒9 𝑥 𝑤 4 𝑒3 3 𝑑 𝑮 𝑯 NOT SIMPLE SIMPLE CONNECTED GRAPH A graph is connected if there is at least a path that connects two vertex sets. 𝑬 𝑫 3 1 2 4 𝑭 DISCONNECTED GRAPH A graph is disconnected if there is no path to connect two vertex sets. 3 1 2 4 𝑰 𝑱 NULL GRAPH It is a graph in which no edge is drawn between any two vertices. 1 5 2 4 3 𝑴 𝑵 COMPLETE GRAPH It is a graph in which every possible edge is drawn between the vertices. Moreover, this implies that any two vertices are adjacent. BIPARTITE GRAPH A graph is bipartite if it is possible to divide all its vertices into two disjoint subsets such that every edge in the graph connects a vertex in one subset to a vertex in the other subset. 𝑢1 𝑣1 𝑥1 𝑥2 𝑥3 𝑢2 𝑣2 𝑦1 𝑦2 𝑦3 𝑢3 𝑣3 𝑷 𝑸 𝑹 DIRECTED GRAPH It is a graph where all the edges are directed from one vertex to another. It is also called a digraph. 𝑫 TREE GRAPH It is an undirected graph in which any two vertices are connected by exactly one path. EQUIVALENT GRAPHS Two or more graphs are equivalent if the edges form the same connections of vertices. 𝑷 𝑸 𝑹 EQUIVALENT GRAPHS Are the graphs below equivalent? EQUIVALENT GRAPHS Are the graphs below equivalent? PATH A path in a graph is a sequence of edges which joins a sequence of distinct vertices. 𝑢1 − 𝑢5 − 𝑢2 − 𝑢3 𝑣5 − 𝑣4 − 𝑣3 − 𝑣1 − 𝑣2 CIRCUIT A circuit is a closed path/cycle where a path ends at the same vertex at which it started. 𝒖𝟏 − 𝑢5 − 𝑢2 − 𝑢3 − 𝑢4 − 𝒖𝟏 𝒗𝟏 − 𝑣2 − 𝑣3 − 𝑣4 − 𝑣5 − 𝒗𝟏  EULER PATH EULER CIRCUIT It is a path where each edge It is a circuit/cycle where each in a graph is traversed once edge in a graph is traversed and starts and ends at a once and starts and ends at different vertex. the same vertex. 𝟏−2−3−4−5−1−𝟒 𝟏−2−3−4−5−𝟏 Find an Euler circuit in the figure below: (Page 232, Figure 6.5) A-B-C-E-H-G-F-D-G-E-B-D-A  DEGREE It refers to the number of edges that OF A VERTEX is incident at a vertex. 𝑨 This means that the degree of a vertex indicates the number edges connected to that vertex. 𝑑𝑒𝑔 𝐴 = 2 𝑬 𝑩 𝑑𝑒𝑔 𝐵 = 4 𝑑𝑒𝑔 𝐶 = 3 𝑑𝑒𝑔 𝐷 = 3 𝑫 𝑪 𝑑𝑒𝑔 𝐸 = 4 EULERIAN GRAPH THEOREM Eulerian Graph Theorem A connected graph is Eulerian if and only if every vertex of the graph is of even degree. Furthermore, the graph is Eulerian if it has an Euler circuit. Which of the following graphs is Eulerian? (Page 233, Example 3) APPLICATION OF EULERIAN GRAPH THEOREM (Page 234, Example 5) Is it possible to plan a journey that traverse the tracks and returns to the starting point without traveling through any portion of a track more than once?  EULER PATH THEOREM Euler Path Theorem A connected graph contains an Euler path if and only if the graph has two vertices of odd degree with all other vertices of even degree. Which of the following has an Euler path? (Page 233, Example 3) recall… The Konigsberg Problem Can you walk through each bridge exactly once? THE KONIGSBERG PROBLEM Can you walk through each bridge exactly once? Historical background Leonard Euler (1707-1783) – American mathematician and logician introduced this formal definition of relation APPLICATION OF EULER PATH THEOREM (Page 236, Example 6) Is it possible for the photographer to design a trip that traverses all the roads exactly once? APPLICATION OF EULER PATH THEOREM (Page 236, Check your progress 6) Is it possible for the cyclist to traverse all of the trails without repeating any portions of the trip? APPLICATION OF EULER PATH THEOREM (Page 236, Example 7) APPLICATION OF EULER PATH THEOREM 𝑩 𝑪 𝑫 𝑬 𝑨 𝑭 (Solution, Page 237, Example 7) End of Discussion…