Simple Graph Theory Concepts - (LEC 5) PDF

MATHEMATICS IN THE MODERN WORLD NAME OF INSTRUCTOR: MAY SALANSANG  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A graph is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices. vert...

MATHEMATICS IN THE MODERN WORLD NAME OF INSTRUCTOR: MAY SALANSANG  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A graph is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices. vertex edge loop  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A graph is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices. vertex edge loop A loop is an edge connecting a vertex to itself.  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A complete graph is a graph that has an edge connecting every pair of vertices. A M C B Q N E D P O Figure 1 Figure 2  BASIC CONCEPTS OF GRAPH THEORY - Terminologies Two vertices are adjacent if there is an edge joining them. B A E C D Figure 3  BASIC CONCEPTS OF GRAPH THEORY - Terminologies Graphs are considered as equivalent if they have same vertices connected in the same way. A A B C B D C D Figure 4 Figure 5  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A path is an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.A B C F D E Figure 6  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A path is an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.A B C F D E Figure 6 If a path begins and ends with the same vertex, it is a closed path or a circuit or cycle.  BASIC CONCEPTS OF GRAPH THEORY - Terminologies A graph is connected if for any two vertices, there is at least one path that joins them. A bridge is an edge that when you remove makes the graph disconnected. N P A B E F M D C G O Q Figure 7 Figure 8  BASIC CONCEPTS OF GRAPH THEORY - Terminologies The degree of a vertex is the number of edges attached to it.  BASIC CONCEPTS OF GRAPH THEORY – Relationship between vertices, edges and degree of each vertex for complete graphs K1: One Vertex: K2: Two Vertices: K3: Three Vertices: K4: Four Vertices:  BASIC CONCEPTS OF GRAPH THEORY – Relationship between vertices, edges and degree of each vertex for complete graphs K5: Five Vertices:  BASIC CONCEPTS OF GRAPH THEORY – Relationship between vertices, edges and degree of each vertex for complete graphs K5: Five Vertices: Let e be the number of edges in a complete graph. From the results: K1: e = 0, degree of the vertex is 0 K2: e = 1, degree of each vertex is 1  BASIC CONCEPTS OF GRAPH THEORY – Relationship between vertices, edges and degree of each vertex for complete graphs K3: e = 3, degree of each vertex is 2 K4: e = 6, degree of each vertex is 3 K5: e = 10, degree of vertex is 4  BASIC CONCEPTS OF GRAPH THEORY – Relationship between vertices, edges and degree of each vertex for complete graphs A complete graph with n vertices: 1 𝑒𝑛 = 𝑛 𝑛 − 1 for n ≥ 3 while the degree of each 2 vertex is obviously equal to n - 1.  BASIC CONCEPTS OF GRAPH THEORY - Examples The diagram below appears in a book in psychology. It is used to indicate ”transactions” which occur in man- woman relationships.  BASIC CONCEPTS OF GRAPH THEORY - Examples A molecule of the hydrocarbon 2-methylbutane appears in chemistry textbooks as below:  BASIC CONCEPTS OF GRAPH THEORY - Examples The air distance between cities on the routes of Philippine Airlines and another Asian carrier is nicely illustrated on a graph with weighted edges. Graph Coloring One of the subjects studied by mathematicians is graph coloring. The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are given different colors. Graph Coloring One of the subjects studied by mathematicians is graph coloring. The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are given different colors. The smallest number of colors required to color the vertices of a graph is the chromatic number of the graph. Graph Coloring 2- Colorable Graph Theorem. A graph is 2-colorable if and only if it has no circuits that consist of odd number of vertices. Graph Coloring 2- Colorable Graph Theorem. A graph is 2-colorable if and only if it has no circuits that consist of odd number of vertices. Four-Color Theorem. The chromatic number of a planar graph is at most 4. Graph Coloring Example: Find the optimal number of colors for the nodes. F A G B C L H I D E J K Figure 9 Figure 10 Map Coloring A map can be represented by a graph with the different regions as vertices. Two regions are adjacent if they share part of their boundaries. Map Coloring A map can be represented by a graph with the different regions as vertices. Two regions are adjacent if they share part of their boundaries. The graph representing a map is planar. Hence, it needs only 4 colors. Color the Map Draw the corresponding graph and color. Color the Map Draw the corresponding graph and color.  EULER PATHS AND CIRCUITS Euler path - a path that passes through every edge exactly once only - a path that contains all the edges of the graph - begin and end with the odd-degree vertices  EULER PATHS AND CIRCUITS Euler path - a path that passes through every edge exactly once only - a path that contains all the edges of the graph - begin and end with the odd-degree vertices * A graph has an Euler path if and only if no more than two of its vertices have odd degree.  EULER PATHS AND CIRCUITS An Euler circuit of a graph is a closed path that contains all the edges of the graph.  EULER PATHS AND CIRCUITS An Euler circuit of a graph is a closed path that contains all the edges of the graph. A graph that has an Euler circuit is called Eulerian. A connected graph is Eulerian if and only if each vertex has even degree.  EULER’S THEOREM For any connected graph: 1. If all vertices are even, the graph has at least one Euler circuit (which is by definition also as Euler path). An Euler circuit can start at any vertex.  EULER’S THEOREM For any connected graph: 1. If all vertices are even, the graph has at least one Euler circuit (which is by definition also as Euler path). An Euler circuit can start at any vertex. 2. If exactly two vertices are odd, the graph has no Euler circuits but at least one Euler path. The path must begin at one odd vertex and end at the other odd vertex.  EULER’S THEOREM 3. If there are more than two odd vertices, the graph has no Euler path and no Euler circuits.  FLEURY’S ALGORITHM * Before using Fleury’s algorithm, make sure you’ve used Euler’s Theorem to confirm that the graph has an Euler path or Euler circuit.  FLEURY’S ALGORITHM To find an Euler path or Euler circuit: 1. If a graph has no odd vertices, start at any vertex. If the graph has two odd vertices, start at either odd vertex.  FLEURY’S ALGORITHM To find an Euler path or Euler circuit: 1. If a graph has no odd vertices, start at any vertex. If the graph has two odd vertices, start at either odd vertex. 2. Number the edges as you trace through the graph making sure not to traverse any edge twice.  FLEURY’S ALGORITHM To find an Euler path or Euler circuit: 1. If a graph has no odd vertices, start at any vertex. If the graph has two odd vertices, start at either odd vertex. 2. Number the edges as you trace through the graph making sure not to traverse any edge twice. 3. At any vertex where you have a choice of edges, choose one that is not a bridge for the part of the graph that has not yet been numbered.  Examples of Euler Paths and Eulerian Circuits The floor plan of a museum is shown below. Draw a graph showing the plan, with each room represented by a vertex and each edge representing a door between adjoining rooms. Is it possible to walk in the museum passing through each door exactly once?  Examples of Euler Paths and Eulerian Circuits.  APPLICATION OF EULER’S THEOREM A mail carrier has the neighborhood pictured below on his route. He wants to cover each street exactly once without retracing any street. Find a way to accomplish this.  APPLICATION OF EULER’S THEOREM A mail carrier has the neighborhood pictured below on his route. He wants to cover each street exactly once without retracing any street. Find a way to accomplish this. A H G F B C D E  Hamiltonian Paths and Cycles A Hamiltonian path of a graph is a path passing through each vertex of the graph exactly once.  Hamiltonian Paths and Cycles A Hamiltonian path of a graph is a path passing through each vertex of the graph exactly once. If the path is closed, it is called a Hamiltonian cycle. If a graph has a Hamiltonian cycle, it is called Hamiltonian.  Complete Graphs and Hamiltonian Circuits Every complete graph with more than two vertices has a Hamiltonian circuit. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!.  Complete Graphs and Hamiltonian Circuits Every complete graph with more than two vertices has a Hamiltonian circuit. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!. Two Hamiltonian circuits are the same if they pass through the same vertices in the same order, regardless of the vertex where they begin and end. Dirac’s Theorem Let G be a simple connected graph with n ≥ 3 vertices. If 𝑛 the degree of each vertex in G is at least , then G is 2 Hamiltonian. A D E G F B C  TREES A tree is a graph in which any two vertices are connected by exactly one path.  TREES A tree is a graph in which any two vertices are connected by exactly one path. Examples of a tree: A W B C X D Z E F H G Y  TREES Properties of Trees: 1. A tree has no circuits. 2. Trees are connected graphs. 3. Every edge in a tree is a bridge. 4. A tree with n vertices has exactly n-1 edges.  FOREST a forest is an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree. The graph looks like a two sub-graphs but it is a single disconnected graph. There are no cycles in the above graph. Therefore, it is a forest. Spanning Tree A spanning tree for a graph is a tree that results from the removal of as many edges as possible from the original graph without making it disconnected. Spanning Tree Find a spanning tree of the graph: Spanning Tree Sample of a spanning tree of the graph: Minimal Spanning Trees A minimum spanning tree for a weighted graph is the spanning tree for the graph that has the smallest possible sum of the weights. A minimum spanning tree must have one fewer edge than the number of vertices.  Prim’s Algorithm Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which 1. form a tree that includes every vertex 2. has the minimum sum of weights among all the trees that can be formed from the graph  The steps for implementing Prim's algorithm are as follows: 1. Initialize the minimum spanning tree with a vertex chosen at random. 2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree 3. Keep repeating step 2 until we get a minimum spanning tree Example: Example:  Minimal Spanning Trees (Kruskal’s Algorithm) To construct a minimum spanning tree for a weighted graph: 1. Choose the edge with the lowest weight and highlight it in color. 2. Choose the unmarked edge with the next lowest weight that does not form a circuit with the edges already highlighted and highlight it. 3. Repeat until all vertices have been connected. Minimum Spanning Tree Give the minimum spanning tree of the graph. Kruskal’s Algorithm Find a minimal spanning tree: Planar Graph and Euler’s Formula A graph is planar if it can be drawn in such a way that no edges cross. This means that any two edges can meet only at an endpoint. In a planar graph drawn with no crossing edges, if the number of vertices is v, the number of edges is e, and the number of faces is f, v + f = e + 2. PROBLEM SET A film class is making movies in groups. Three digicams are available and each movie must be shot for a whole day. Each student can work on only one movie at a time. Make a graph covering the least number of shooting day. Movie 1: Brian, Angela, Kate Movie 2: Jessica, Vince, and Brian Movie 3: Corey, Brian, and Vince Movie 4: Ricardo, Sarah, and Lupe Movie 5: Sarah, Kate, and Jessica Movie 6: Angela, Corey, and Lupe Note: This is an application of a tree