What is Graph Theory?


Graph theory is a branch of mathematics concerned about how networks can be encoded and solved.


Applications for Graph Theory:

1- Making and organizing timetables.
2- Studying molecules in physics and chemistry.
3- Finding optimal paths for transportation purposes.
4- Colouring maps.

Important Terms and Definitions:

Term	Defintion
Graph	Also called a network is a collection of lines joined together.
Edge	Lines in a graph are called edges.
Vertex	Dots or nodes are referred to as vertices.
Path	Connected series of edges.
Circuit	A path that begins and ends at the same vertex.
Connected Network	Is a network that has at least one path joining each pair of vertices.
Complete Network	Is a network in which every pair of vertices is joined by an edge (line).

* A Graph is considered traceable if it has all the vertices connected to at least one other node (vertex) and ALL edges can be traveled exactly once in a continuous path.

* If all the verticies of a graph are of even degree, then the graph is tracable. Also, if a graph has two verticies of odd degree and the rest are even, then the graph is tracable.


Example 1

Make networks of the following maps:

Map 1




Solution

- Start by lettering the areas in the map as follows:



- Then make a network by drawing a point for each letter and then connect the dots of the letters which areas are touching or are adjacent to each other, as follows:



Map 2

Try this one out...






Solution








Example 2

Refer to the network in the figure.
a) How many degrees does each vertex have?
b) Is the network traceable?


Solution

a) Number of degrees of each vertex:

T: 3
U: 2
V: 4
W: 4
X: 2
Y: 3
Z: 4

b) Yes, the network is traceable because only two verticies have odd degrees
(T and Y), and the rest of the verticies have even degrees.


Example 3

The unknown town of Networki was situated on three islands and the banks of Circuitry River. Networki had 10 bridges as shown in the map. The people wanted to find a way to traverse the town by only crossing each bridge once. Is this possible?




Solution

Make a network of the map:


Count the degrees of each vertex:

A: 4
B: 4
C: 4
D: 4
E: 4

Therefore, it is possible to traverse all the bridges without double crossing because each vertex has an even number of degrees.