MMWModule- Elective 1Mathematics-of-Graph PDF

Preview

Summary

Download MMWModule- Elective 1Mathematics-of-Graph PDF

Description

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

MODULE 5 MATHEMATICS OF GRAPHS MODULE OVERVIEW

This module consists of 4 lessons: Graphs and Euler Circuits, Weighted Graphs, Planarity and Euler’s Formula, Graph Coloring. Each lesson was designed as a self-teaching guide. Definitions of terms and examples had been incorporated. Answering the problems in “your turn” will check your progress. You may compare your answers to the solutions provided at the later part of this module in that way you will be able to measure your achievement and as well as the effectiveness of the module. Exercises were prepared as your assignment to measure your understanding about the topics. MODULE LEARNING OBJECTIVES

At the end of the module, you should be able to: • • • • • •

Define basic concepts of graph Construct graph to represent many scenarios. Identify if there exist an Euler Circuit or Euler Path given a certain graph. Analyze and solve a variety of real life problems using Eulerian Graph Theorem Find the least expensive route of travel using Greedy and Edge picking algorithm Determine the chromatic number of a graph and finding a corresponding coloring of the graph to solve a wide assortment of practical problems.

LEARNING CONTENTS (GRAPHS AND EULER CIRCUITS)

5.1 Introduction to Graphs Think of all the various connections we experience in our lives—friends are connected on Facebook, cities are connected by roads, computers are connected across the Internet. A branch of mathematics called graph theory illustrates and analyzes connections such as these. For example, the diagram in Figure 5.1 could represent friends that are connected on Facebook. Each dot represents a person, and a line segment connecting two dots means that those two people are friends on Facebook. This type of diagram is called a graph.

PANGASINAN STATE UNIVERSITY

1

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

Graph

A graph is a set of points called vertices and line segments or curves called edges that connect vertices.(See figure 5.2)

Figure 5.2

Graphs can be used to represent many different scenarios. For instance, the three graphs in Figure 3.2 are the same graph as in Figure 5.1 but used in different contexts. In part (a), each vertex represents a baseball team, and an edge connecting two vertices might mean that the two teams played against each other during the current season. Note that the placement of the vertices has nothing to do with geographical location; in fact, the vertices can be shown in any arrangement we choose. The important information is which vertices are connected by edges.

Figure 5.3

(a)

(b)

(c)

Figure 5.3(b) shows the computer network of a small business. Each vertex represents a computer, and the edges indicate which machines are directly connected to each other. The graph in Figure 5.3(c) could be used to represent the flights available on a particular airline between a selection of cities; each vertex represents a city, and an edge connecting two cities mean that there is a direct flight between the two cities.

Example 1

Constructing a Graph

The following table lists five students at a college. An “X” indicates that the two students participate in the same study group this semester.

PANGASINAN STATE UNIVERSITY

2

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

a. Draw a graph that represents this information where each vertex represents a student and an edge connects two vertices if the corresponding students study together. b. Use your graph to answer the following questions: Which student is involved in the most study groups with the others? Which student has only one study group in common with the others? How many study groups does Laura have in common with the others? Solution a. We draw five vertices (in any configuration we wish) to represent the five students, and connect vertices with edges according to the table.

b. The vertex corresponding to Amber is connected to more edges than the others, so she is involved with more study groups (three) than the others. Kayla is the only student with one study group in common, as her vertex is the only one connected to just one edge. Laura’s vertex is connected to two edges, so she shares two study groups with the others.

Take note ! In constructing graphs, consider the following: • The edges can be drawn either straight or curved. It does NOT matter • The lengths of edges and the placement of the vertices are NOT important • The graph simply illustrates connections between vertices.

The table below lists fi ve mobile phone companies and indicates whether they have agreements to roam onto each other’s networks. Draw a graph that represents this information, where each vertex represents a phone company and an edge connects two vertices if the corresponding companies have a roaming agreement. Then use the graph to answer the questions: Which phone company has roaming agreements with the most carriers? Which company can roam with only one other network?

Your turn 1

PANGASINAN STATE UNIVERSITY

3

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

Let us try to study some graph terminologies that we will encounter in the whole module: Terminologies

Definitions

Connected graph

A graph is connected if there is a path connecting every pair of vertices

Multigraph

A graph with multiple edges between the same vertices. These edges are called parallel or multiple edges.

Disconnected graph

Graph consisting of two different sections.

Loop

Edge that connects a vertex to itself. Vertex 1 has a loop.

Simple graph

Graph that has no loops or multiple edges

Null graph

Graph with vertices, but no edges. It is also an example of disconnected graph

Isolated vertex

Vertex that has no edge incident with it

PANGASINAN STATE UNIVERSITY

Example

4

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

Pendant vertex

Vertex that has one edge incident edge with it. Vertex 6 is a pendant vertex.

Degree of a vertex

Number of edges that meet at a vertex. The degree of the vertex v is denoted by deg(v). Note that a loop of a vertex contributes two to the degree of that vertex.

A E deg(A)=3 deg(B)=5 deg(C)=2

Complete graph

D

B C deg(D)=4 deg(E)=2

Connected graph in which every possible edge is drawn between vertices (w/o any multiple edges)

Question ?n Is the following graph a complete graph?

Consequently, the three graphs shown below are considered equivalent graphs because the edges form the same connections of vertices in each graph.

PANGASINAN STATE UNIVERSITY

5

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

If you have difficulty seeing that these graphs above are equivalent, use the labeled vertices to compare each graph. Note that in each case, vertex B has an edge connecting it to each of the other four vertices, and no other edges exist.

Answer : No. Not every possible edge is drawn. We can add two more edges:

Example 2

Equivalent Graphs

Determine whether the following two graphs are equivalent.

Solution Despite the fact that the two graphs have different arrangements of vertices and edges, they are equivalent. To illustrate, we examine the edges of each graph. The first graph contains six edges; we can list them by indicating which two vertices they connect. The edges are AC, AE, BD, BE, CE, and DE. If we do the same for the second graph, we get the same six edges. Because the two graphs represent the same connections among the vertices, they are equivalent.

Your turn 2

Determine whether the following two graphs are equivalent.

Euler Circuits In the early eighteenth century, the Pregel River in a city called Königsberg (located in modern-day Russia and now called Kaliningrad) surrounded an island before splitting in two. Seven bridges crossed the river and connected four different land areas, similar to the map in figure 5.4

PANGASINAN STATE UNIVERSITY

6

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Module 5: Mathematics of Graph

Figure 5.4

Many citizens of the time attempted to take a stroll that would lead them across each bridge and return them to the starting point without traversing the same bridge twice. None of them could do it, no matter where they chose to start. Try it for yourself with pencil and paper. You will see that it is not easy! To solve the Königsberg bridges problem, we can represent the arrangement of land areas and bridges with a graph. Let each land area be represented by a vertex, and connect two vertices if there is a bridge spanning the corresponding land areas. Then the geographical situation shown in Figure 5.5 becomes the graph shown in Figure 5.6.

Figure 5.5

Figure 5.6

In terms of a graph, the original problem can be stated as follows: Can we start at any vertex, move through each edge once (but not more than once), and return to the starting vertex? Again, try it with pencil and paper. Every attempt seems to end in failure. Before we can examine how Euler proved this task impossible, we need to establish some terminology. Path

A path in a graph can be thought of as a movement from one vertex to another by traversing edges.

PANGASINAN STATE UNIVERSITY

7

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

We can refer to our movement by vertex letters. For example, in the graph in Figure 5.6, one path would be 𝐴– 𝐵– 𝐴– 𝐶 . If a path ends at the same vertex at which it started, it is considered a closed path, or circuit. For the graph in Figure 5.7, the path 𝐴– 𝐷– 𝐹– 𝐺– 𝐸– 𝐵– 𝐴 is a circuit because it begins and ends at the same vertex. The path 𝐴– 𝐷– 𝐹– 𝐺– 𝐸– 𝐻 is not a circuit, as it does not begin and end at the same vertex.

Figure 5.7

Euler Circuit

A circuit that uses every edge, but never uses the same edge twice, is called an Euler circuit. (The path may cross through vertices more than once.)

The path 𝐵– 𝐷– 𝐹– 𝐺– 𝐻– 𝐸– 𝐶– 𝐵– 𝐴– 𝐷– 𝐺– 𝐸– 𝐵 in Figure 5.7 is an Euler circuit. It begins and ends at the same vertex and uses each edge exactly once.(Trace the path with your pencil to verify!) The path 𝐴– 𝐵– 𝐶– 𝐸– 𝐻– 𝐺– 𝐸– 𝐵– 𝐷– 𝐴 is not an Euler circuit. The path begins and ends at the same vertex but it does not use edges DF, DG, or FG. The path 𝐴– 𝐵– 𝐶– 𝐸– 𝐻– 𝐺– 𝐹– 𝐷– 𝐴– 𝐵– 𝐸– 𝐺– 𝐷– 𝐴 begins and ends at A but uses edges AB and AD twice so it is not an Euler circuit. All of this relates to the Königsberg bridges problem in the following way: Finding a path that crosses each bridge exactly once and returns to the starting point is equivalent to finding an Euler circuit for the graph in Figure 5.6. Euler essentially proved that the graph in Figure 5.6 could not have an Euler circuit. Eulerian Graph Theorem

A connected graph is Eulerian if and only if every vertex of the graph is of even degree.

PANGASINAN STATE UNIVERSITY

8

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Example 3

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

Identifying Eulerian Graphs

Which of the following graphs has an Euler circuit?

Solution a. Vertices C and D are of odd degree. By the Eulerian Graph Theorem, the graph does not have an Euler circuit. b. All vertices are of even degree. By the Eulerian Graph Theorem, the graph has an Euler circuit.

Your turn 3

Does the graph shown below have an Euler circuit?

Look again at Figure 5.6, the graph representation of the Königsberg bridges. Because not every vertex is of even degree, we know by the Eulerian Graph Theorem that no Euler circuit exists. Consequently, it is not possible to begin and end at the same location near the river and cross each bridge exactly once. The Eulerian Graph Theorem guarantees that when all vertices of a graph have an even degree, an Euler circuit exists, but it does not tell us how to find one. Because the graphs we will examine here are relatively small, we will rely on trial and error to find Euler circuits. There is a systematic method, called Fleury’s algorithm, that can be used to find Euler circuits in graphs with large numbers of vertices. ( For information on and examples of finding Eulerian circuits, search for “Fleury’s algorithm” on the Internet.)

PANGASINAN STATE UNIVERSITY

9

FM-AA-CIA-15 Rev. 0 10-July-2020

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Example 4

Module 5: Mathematics of Graph

Find an Euler Circuit

Solution Each vertex has a degree of 2, 4, or 6, so by the Eulerian Graph Theorem, the graph is Eulerian. There are many possible Euler circuits in this graph. We do not have a formal method of locating one, so we just use trial and error. One Euler circuit is B–A–F–B–E–F–G–E–D–G–B–D–C–B.

Your turn 4

Example 5

Does the graph at the left have an Euler circuit? If so, find one. If not, explain why.

An Application of Euler Circuits

The subway map below shows the tracks that subway trains traverse as well as the junctions where one can switch trains. Suppose an inspector needs to travel the full length of each track. Is it possible to plan a journey that traverses the tracks and returns to the starting point without traveling through any portion of a track more than once?

PANGASINAN STATE UNIVERSITY

10

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

Solution We can consider the subway map a graph, with a vertex at each junction. An edge represents a track that runs between two junctions. In order to find a travel route that does not traverse the same track twice, we need to find an Euler circuit in the graph. Note, however, that the vertex representing the Civic Center junction has degree 3. Because a vertex has an odd degree, the graph cannot be Eulerian, and it is impossible for the inspector not to travel at least one track twice.

Your turn 5

Suppose the city of Königsberg had the arrangement of islands and bridges pictured below instead of the arrangement that we introduced previously. Would the citizens be able to complete a stroll across each bridge and return to their starting points without crossing the same bridge twice?

Euler Paths Perhaps the Königsberg bridges problem would have a solution if we did not need to return to the starting point. In this case, what we are looking for in Figure 5.6 is a path (not necessarily a circuit) that uses every edge once and only once. We call such a path an Euler path. Euler showed that even with this relaxed condition, the bridge problem still was not solvable. The general result of his argument is given in the following 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. Furthermore, every Euler path must start at one of the vertices of odd degree and end at the other. Furthermore, every Euler path must start at one of the vertices of odd degree and end at the other. A Euler path does not require that we start and stop at the same vertex, while Euler circuit does.

PANGASINAN STATE UNIVERSITY

11

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

Example 6

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

An Application of Euler Paths

A photographer would like to travel across all of the roads shown on the following map. The photographer will rent a car that need not be returned to the same city, so the trip can begin in any city. Is it possible for the photographer to design a trip that traverses all of the roads exactly once?

Solution Looking at the map of roads as a graph, we see that a route that includes all of the roads but does not cover any road twice corresponds to an Euler path of the graph. Notice that only two vertices are of odd degree, the cities Alameda and Dover. Thus we know that an Euler path exists, and so it is possible for the photographer to plan a route that travels each road once. Because (abbreviating the cities) A and D are vertices of odd degree, the photographer must start at one of these cities. With a little experimentation, we find that one Euler path is A–B–C–D–B–F–A–G–F–E–D.

Your turn 6

A bicyclist wants to mountain bike through all the trails of a national park. A map of the park is shown below. Because the bicyclist will be dropped off in the morning by friends and picked up in the evening, she does not have a preference for where she begins and ends her ride. Is it possible for the cyclist to traverse all of the trails without repeating any portions of her trip?

Example 7

An Application of Euler Paths

PANGASINAN STATE UNIVERSITY

12

Study Guide in Mathematics in the Modern World

GE7 Mathematics in the Modern World

FM-AA-CIA-15 Rev. 0 10-July-2020 Module 5: Mathematics of Graph

The floor plan of an art gallery is pictured below. Draw a graph that represents the floor plan, where vertices correspond to rooms and edges correspond to doorways. Is it possible to take a stroll that passes through every doorway without going through the same doorway twice? If so, does it matter whether we return to the starting point?

Solution We can represent the floor plan by a graph if we let a vertex represent each room. Draw an edge between two vertices if there is a doorway between the two rooms, as shown in Figure 5.8.

Figure 5.8

Figure 5.9

The graph in Figure 5.9 is equivalent to our floor plan. If we would like to tour the gallery and pass through every doorway once, we must find a path in our graph that uses every edge once (and no more). Thus we are looking for an Euler path. In the graph, two vertices are of ...