Mathematics

Thinking Mathematically

7th Edition

You are required to purchase the access code for MyLab/Mastering (MyMathLab).

Thinking Mathematically – eText (w/Access Code – MyMathLab ) – ISBN # 9780134705095

ANSWER

Graph Theory

1. Modelling relationships using graphs

Graphs are used to create simplified and abstract models to problems. A graph models relationships by describing an arbitrary domain presenting it as a connected graph of nodes. The graph’s components includes elements called vertices and edges also referred to as nodes and links. Vertex are represented by a circle while edge by a line or an arrow as shown below

Vertex

Edge

For instance, modelling the following relationship using a graph.

Seth and Mark are friends and both play tennis. This can be modelled as

Is friends with

plays                              plays

1. Euler path and using Fleury’s Algorithm to find possible Euler paths

In a graph Euler path is a path which passes via all the edges of a graph only once. As such, it starts from a different edge and ends at a different edge. For the Euler path to exist, it is necessary for the graph to be connected.

A              C

E

D

B

Using Fleury’s Algorithm, we find Euler paths such as

1. E-D-C-A-B-D
2. E-D-B-A-C-D

• D-C-A-B-D-E

The graph has many Euler paths

• Euler circuit and using Fleury’s Algorithm to find possible Euler circuits

In a graph Euler circuit is a circuit that passes via all the edges of the graph only once. The circuits begins and ends with the same vertex.

Example.

A                                                    E

C

B                                           F

D

Using Fleury’s Algorithm the possible Euler circuits are;

1. A-B-D-C-D-F-E-C-A
2. C-D-C-A-B-D-F-E-C

• F-E-C-A-B-D-C-D-F

There are many Euler circuits