TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

3.16 AN INFORMAL PRESENTATION OF GRAPHS

We will start without any formal definition as the concept of a

graph is straightforward.

 COMPLETE SIMPLE GRAPHS

Look at the following list of diagrams:

K1

K2

K3

K4

K5

We say that Kn is a complete simple graph:

 As you can imagine, the graph Kn contains n vertices.

 We say that Kn is complete as all vertices are connected to each

other with edges.

 We say that Kn is simple as it contains

no loops no parallel edges

47
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

Question: How many edges does Kn have?

Look at K5 .

Every vertex is connected to the other 4 vertices:

5×4 = 20

But every edge is counted twice. Thus, the total number of edges is
5 4
= 10
2

In general, the complete simple graph Kn contains

n(n- 1)
edges
2
(look at the list of complete graphs above to confirm the result).

For example, K6 will have

65
= 15 edges
2

Let us make clear that the way we draw a graph is irrelevant! The

graphs

and

are exactly the same.

In this section we mainly deal with “subgraphs” of those graphs.

For example,

is a simple graph of 5 vertices and 7 edges.

It is a subgraph of K5 .

48
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 A COMPANY OF FIVE PEOPLE

Consider a company of five people: A, B, C, D, E.

If they all friends to each other, this “warm friendship” can be

represented by a complete graph K5 .

If there is no friendship between A-C, A-D and B-D, the

corresponding graph will be

If those 5 people do not know each other, this most “frigid

relationship” can be shown by the following graph:

Thus, a simple graph of 5 vertices can be anything between the

complete graph K5 and the last “empty” graph.

Finally, notice that here we are talking about simple graphs as

- you cannot be a friend with yourself (no loops),

- you cannot be a friend with somebody twice! (no parallel edges).

49
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 THE DEGREE OF A VERTEX

In the following graph

The person A has 2 friends: we say that the vertex A has degree 2.

Similarly, B has degree 3, C has degree 3, etc.

 DIRECTED GRAPHS

Perhaps the friendship among those 5 people is not a two-way

relationship! They are just Instagram friends where some of them

“follow” others. Two people do not necessarily follow each other.

Here we need a directed graph:

In this example,

A “follows” B but B “does not follow” A.

E and C “follow” each other!

There is no relation between A and C, etc.

Finally, the person A

follows 1 person: we say that the vertex A has out-degree 1,

has 1 follower: we say that the vertex A has in-degree 1.

Similarly, E (which seems to be the most “sociable” person), has

out-degree 4 and in-degree 2.

50
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 NON-SIMPLE GRAPHS

Perhaps those 5 vertices represent “cities” and the edges “roads”

between cities. Thus, we allow loops and/or parallel edges.

Non-simple graphs:

 WEIGHTED GRAPHS

Sometimes the edge alone is not enough to represent the

information we want. For example, we want to include the

distances between 5 cities:

5 8
7

15 9
7

10

Then we are talking about a weighted graph.

51
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

3.17 A FORMAL DEFINITION OF GRAPHS

A graph G [or a graph G(V,E)] consists of

a set of vertices V

a set of edges between vertices E

For example, the graph G with

V = {A, B, C, D, E}

E = {AB, AE, BC, BE, CD, CE, DE}

is the following.

We say that

The vertices A and B are adjacent (they are linked by edge AB).

The edges AB and BC are adjacent (they are linked by vertex B).

A and C are not adjacent. AB and EC are not adjacent.

For each vertex we define

degree of A = number of adjacent vertices

Thus

vertex A B C D E

degree 2 3 3 2 4

We say that the graph is simple if

It contains no loops (e.g. edge A to itself)

It contains no parallel edges (e.g, two edges from A to B)

52
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 ROUTES ON THE GRAPH

We can visit successive vertices by 3 kinds of routes:

Path: no vertex is revisited: e.g. ABC or AECD

Trail: no edge is revisited: e.g. AEBCED or BECBA

Walk: Walk as you wish, e.g. ABCBEC or ABAE

Simply speaking,

a path from X to Y looks like a trail from X to Y looks like

We also define:

cycle: derived from a path which closes to the initial vertex

e.g. ABEA or EBCDE (only the first vertex is revisited)

circuit: a trail which closes to the initial vertex, e.g. AEDCEBA

(a walk which closes to the initial vertex is nothing more than a

walk which closes to the initial vertex! e.g. ABABABA)

The number of edges on a path, trail or walk is called length.

For example,

AB is a path of length 1 (just an edge)

ABC is a path of length 2.

AEBCED is a trail of length 5.

ABABABA is a walk of length 6. [one less than the vertices]

53
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 ADJACENCY MATRIX

We can represent the graph G

as follows

A B C D E

A 0 1 0 0 1

B 1 0 1 0 1

C 0 1 0 1 1

D 0 0 1 0 1

E 1 1 1 1 0

1’s show a connection by an edge.

0’s show no connection

The matrix

0 1 0 0 1
 
1 0 1 0 1
M=0 1 0 1 1
 
0 0 1 0 1
1 1 1 1 0 

is called adjacency matrix.

Notice that

 The main diagonal contains 0’s (why?)

 The matrix is symmetric about the main diagonal (why?)

 The sum in each column (or row) is the degree of the vertex.

54
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 THE POWERS OF AN ADJACENCY MATRIX

For the adjacent matrix M of the graph

use your GDC to find M2

2 1 2 1 1
 
1 3 1 2 2
M =2
2
1 3 1 2
 
1 2 1 2 1
1 2 2 1 4 


This matrix shows the number of walks of length 2.

For example,

there are 2 walks from A to A: ABA and AEA

there is only 1 walk from A to B: AB

there are 3 walks from B to B: BAB, BEB and BCB,.

Amazing, isn’t it? Notice another amazing thing:

the main diagonal contains the degrees of the vertices (why?)

Similarly,
2 5 3 3 6
 
5 4 7 3 7
M =3
3
7 4 5 7
 
3 3 5 2 6
6 7 7 6 6 

shows the numbers of walks of length 3, etc.

Finally, look at the following sums:

M+ M2 shows the numbers of walks of length at most 2.

M+ M2  M3 shows the numbers of walks of length at most 3

55
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 CONNECTED AND DISCONNECTED GRAPHS

If we can connect any pair of vertices by a path the graph is

connected. Otherwise, it is disconnected.

connected disconnected

In our 1st graph, A and C are connected by several paths:

ABC, AEBC, AEDC, etc

In our 2nd graph there is no path between A and C.

NOTICE

On a graph of 5 vertices the maximum length of a path is 4 (why?)

In general, for n vertices, the maximum length of a path is n-1.

The adjacency matrix can give us information about connectivity:

Our graphs above contain 5 vertices. The sum

M+ M2  M3  M4

contains all possible paths (since thay have length at most 4).

if M+ M2  M3  M4 contains 0’s the graph is disconnected.

Otherwise (all elements ≠ 0), the graph is connected.

In general, for a graph of n vertices:

M+ M2  ⋯  Mn-1 shows connectivity.

If it contains 0’s, the graph is disconnected.

56
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 DIRECTED GRAPH

In a directed graph, the edges have a direction.

The edges AB and BA are different.

For example,

Now, instead of degrees, we have out-degrees and in-degrees.

For example, the in-degree of E is 2, the out degree of E is 4.

Paths, strails and walks have a direction. For example

DCEAB is a path of length 4

If there is a path between any pair of vertices X and Y, either from

X to Y or from Y to X the graph is connected.

If paths in both directions exist the graph is strongly connected.

The adjacency matrix is not necessarilly symmetric:

to
A B C D E out-degrees

A 0 1 0 0 0 1

B 0 0 0 0 0 0

from C 0 1 0 0 1 2

D 0 0 1 0 1 2

E 1 1 1 1 0 4

in degrees 1 3 2 1 2

Still, the powers M2, M3, … of the adjacancy matrix M, show

directed walks of length 2, 3 etc.

57
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 WEIGHTED GRAPH

We remind (from previous paragraph) that in a weighted graph

there is a value attached to each edge which is called weight.

5 8
7

15 9
7

10

The path ABCD has

length = 3 [as it contains 3 edges]

total weight = 27 [sum of weights 8+9+10=27]

We can represent the weighted graph by a weighted adjacency

table. (we do not say matrix!).

A B C D E
A 0 8 0 0 5
B 8 0 9 0 7
C 0 9 0 10 15
D 0 0 10 0 7
E 5 7 15 7 0

58
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

3.18 TREES AND SPANNING TREES

Consider the simple graphs on n vertices. Let

Kn = the complete simple graph (it contains all possible edges)

En = the “empty” graph (no edges at all)

For example, if n=5

K5 E5

Graphs with too many vertices (close to Kn) contain cycles.

Graphs with few edges (close to En) are disconnected.

A tree is something in between. Roughly speaking, trees are the

most “minimalist” connected graphs.

Some trees with 5 vertices (they all have 4 edges)

More formally, a tree with n vertices has 3 basic properties:

it is connected it has no cycles it has n-1 edges

In fact, if a graph has any two of the three properties, it is a tree.

Notice

 If we add an edge on a tree, it will contain a cycle.

 If we remove an edge from a tree, it will become disconnected.

59
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

For 1 vertex, there is only 1 trivial tree:

For 2 vertices, there is only 1 tree:

For 3 vertices, there are 3 trees:

For 4 vertices, there are 16 trees! (can you find them?)

 SPANNING TREE

Any connected graph G contains trees. We call them spanning trees

of G. For example, the graph G

has 4 spanning trees:

The complete graph K4

has 16 spanning trees. i.e. all possible trees on 4 vertices, which we

mentioned above (did you find them or not yet?)

60
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 MINIMUM SPANNING TREE (MST)

Consider the weighted graph

4 3

As we mentioned above, there are 4 spanning trees. But now we

are looking for the one of minimum total weight: it is called

minimum spanning tree (MST). This is

4 3

Its total weight is 9.

If we have edges of equal weight we may have more than one

minimum spanning trees.

Finding the minimum spanning tree is not always so

straightforward. We sill see two algorithms that find minimum

spanning trees: Kruskal and Prim algorithms

 KRUSKAL

The algorithm gives an ordered list of n-1 edges:

 Pick the edge of minimum weight. Put it on the list

 Pick the next edge of minimum weight

 Check if it generates a cycle: If not, it’s OK, put in on the list

 Go back to step 2 until n-1 edges are collected on the list.

Note: if there are 2 edges of minimum weight, pick one at random

61
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

EXAMPLE 1

Apply Kruskal’s algorithm on the following graph

5 8
7

15 9
7

10

Solution

We have 5 vertices, we need n-1=4 edges

Pick edge of min weight Check LIST

AE = 5 OK AE

EB = 7 OK EB

ED = 7 OK ED

AB = 8 rejected

BC = 9 OK BC

The minimum spanning tree is

5
7

7 9

It has total weight 28.

62
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 PRIM

The algorithm creates a “growing” tree until it visits all n vertices:

 Pick a vertex at random. Put it on the tree

 Join the tree created to the nearest vertex out of the tree

 Go back to step 2 until all n vertices are joined.

Note: if there are 2 nearest vertices, pick one at random.

EXAMPLE 2

Apply Prim’s algorithm on the following graph

5 8
7

15 9
7

10

Solution

We have 5 vertices; we have to join all of them

Let us start from C. The tree now contains only C

Add the nearest vertex

TREE
to the tree created
CB = 9 CB

BE = 7 CB, BE

EA = 5 CB, BE, EA

ED = 7 CB, BE, EA, ED

The minimum spanning tree is as in example 1.

Total weight = 9+7+5+7 = 28

63
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

We can also work on the adjacency table. Pick C to start.

Cross out row C and circle column C

A B C D E List of edges
A 0 8 0 0 5 start from C

B 8 0 9 0 7
C 0 9 0 10 15
D 0 0 10 0 7
E 5 7 15 7 0

Find the minimum entry in the circled columns: Circle 9.

Cross out the row of 9, that is B, and circle column B.

A B C D E List of edges
A 0 8 0 0 5 Start: C

B 8 0 9 0 7 CB
C 0 9 0 10 15
D 0 0 10 0 7
E 5 7 15 7 0

Find the minimum entry in the circled columns: Circle 7.

Cross out the row of 7, that is E, and circle column E

Continue in the same way until you circle all columns:

A B C D E List of edges
A 0 8 0 0 5 Start: C

B 8 0 9 0 7 CB
C 0 9 0 10 15 BE
D 0 0 10 0 7 EA
E 5 7 15 7 0 ED

The circled numbers show the selected edges and their weights.

Total weight = 9+7+5+7 = 28

64
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

3.19 EULERIAN GRAPHS

A graph is called semi-Eulerian if it possesses a trail that visits all

edges. In other words, it is semi-Eulerian if we can draw the graph

without raising the pencil! Such a trail is called Eulerian trail.

A graph is called Eulerian if it possesses a circuit that visits all

edges. That is, we can draw the graph without raising the pencil as

above, but we have to finish where we started. Such a circuit is

called Eulerian circuit.

semi-Eulerian Eulerian graph

(but not Eulerian)

The first graph is semi-Eulerian. A Eulerian trail is ABCDACEDB

Try to find other Eulerian trails, that is to draw the graph

without raising the pencil!

(Hint: you have to start from A and finish at B or vice versa)

The second graph is Eulerian. A Eulerian circuit is ABCDACEDBFA

Try to find other Eulerian circuits, that is to draw the graph as

above but finish where you started.

(Hint: you can start from any vertex you like.)

65
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

There is an easy way to check if the graph is Eulerian, semi-

Eulerian or neither.

The graph is Eulerian if and only if all vertices have even degrees

The graph is semi-Eulerian if and only if all vertices,

except two vertices X and Y, have even degrees.

The vertices X and Y have odd degrees (we call them odd vertices)

and the trail has to start from X and finish at Y or vice versa.

Look at the degrees of the graphs above:

2
2

4 4
4 4
4 4
3 3
2

In the first graph, only A and B have odd degrees (odd vertices).

That is why the trail has to start from A and finish at B (or vice

versa).

In the second graph all vertices have even degrees.

NOTICE.

These results apply also to non-simple graphs with parallel vertices.

For example, in the first graph above, if we draw a parallel edge

66
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 CHINESE POSTMAN PROBLEM

On a weighted graph:

Edges = roads
Vertices = crossroads

A postman wants to visit all edges and return back to the origin in
the most efficient way (minimum total weight).

If the graph is Eulerian, there is already solution: a Eulerian circuit

Solution: A Eulerian circuit

Minimum cost = total weight

If the graph is semi-Eulerian, we spot the two odd vertices X, Y

We find the shortest path from X to Y of total weight a

Solution: A Eulerian trail from X to Y + shortest path Y to X

Minimum cost = total weight + a

If the graph has 4 odd vertices X, Y, Z, W

We find the best pair of shortest paths:

X to Y and Z to W weights a, b
X to Z and Y to W weights c, d
X to W and Y to Z weights e, f

(Let us assume that the smallest sum is a+b)

Join X-Y and Z-W with fake edges of weights a and b

The graph becomes Eulerian

Solution: A Eulerian circuit but

when we meet X we follow the shortest path X to Y
when we meet Z we follow the shortest path Z to W
Minimum cost = total weight + (a + b)

Notice: the number of odd vertices is always even: 0, 2, 4, 6, …

In exams we can see only cases: 0 (Eulerian), 2 or 4 odd vertices

67
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

EXAMPLE 1

Solve the following Chinese postman problem.

Solution
All vertices have even degree, so the graph is Eulerian.
Thus, the best solution has
total weight = (sum of weights) = 45
If we start from A, a possible route is ABCDFEDBEA

EXAMPLE 2

Solve the following Chinese postman problem.

Solution

There are exactly two odd vertices: E (degree 3) and D (degree 3)

(so the graph is semi-Eulerian).
The shortest path from E to D is EBD of total weight 9.
Thus, the best solution has
total weight = (sum of weights) + 9 = 41 + 9 = 50
If we start from A, a possible route is ABCDEBDBEA

68
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

EXAMPLE 3

Solve the following Chinese postman problem.

Solution

There are exactly four odd vertices: B, E, C, D (all of degree 3)

We have two check three pairs of shortest paths

Pair Best total weight

B to E and C to D 7+5 = 12
B to C and E to D 3+10 = 13
B to D and E to C 8+10 = 18

The best pair is B to E (path BE) and C to D (path CFD)

Thus, the best solution has
total weight = (sum of weights) + 12 = 44 + 12 = 56
If we start from A, a possible route is ABCFDCFDEBEA

69
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

3.20 HAMILTONIAN GRAPHS

A graph is called Hamiltonian if it possesses a cycle that visits all

vertices. Such a cycle is called Hamiltonian cycle.

The following graphs are Hamiltonian

We can simply travel around vertices!

For the first one a Hamiltonian cycle is ABCEDA

For the second one a Hamiltonian cycle is ADECBFA

Of course, in both cases, we can find many Hamiltonian cycles

For example, on the first graph we can follow the route EDCAB

In general,

a Hamiltonian cycle will have length n (number of vertices)

The graph

is not Hamiltonian (why?).

We can visit though all vertices by a path: ECBAD

Such a path is called Hamiltonian path.

70
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

Finally, the following graph contains neitrher a Hamiltonian cycle,

nor a Hamiltonian path.

Indeed, we cannot visit all vertices by a path.

 THE COMPLETE GRAPH Kn

The complete graph K2

is not Hamiltonian. It has though a Hamiltonian path: AB

Any other complete graph Kn is apparently Hamiltonian.

For example, K3

is a cycle on itself! ABCA is a Hamiltonian cycle.

Of course, we can start from any vertex and move either clockwise

or anticlockwise. For example, CBAC is another Hamiltonian cycle.

It also contains many Hamiltonian paths (we do not return back!).

For example, ABC or ACB or CAB are Hamiltonian paths.

What about K4?, How many Hamiltonian cycles does it contain?

71
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

K 4:

If we start from A (and finish at A), for example

ABCDA

The vertices B, C, D can be arranged in any possible way. This can

be done in

3! = 1×2×3=6 ways§

For the complete graph K5 there are 4!=24 cycles starting from a

fixed point A.

For the complete graph K10 there are 9!=362880 cycles starting

from a fixed point A.

For the complete graph K70 there are 69! that is about 1.71×1098

cycles starting from a fixed point A. The number is huge. In fact,

69! is the greatest factorial that your GDC can calculate! Try 70!

On a weighted Kn graph, the task to find the most efficient (of

smallest total weight) is a nightmare!

The investigation of this problem is the task of the next paragraph!

§ If you don’t know, n! is called “n factorial” and is equal to n! = 1×2×3×…×n. There exists
in your GDC: Run-Mat – OPT – PROB – [F1]

72
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 TRAVELING SALESMAN PROBLEM (TSP)

On a weighted Kn graph:

Vertices = cities
Edges = distances between cities

A salesman wants to visit all vertices and return back to the origin
in the most efficient way (minimum total weight).

Let us work on the following weighted K5 graph

Since the graph is complete, the salesman can move in any way he

likes. Suppose he follows the route

ABCDEA with total weight 37km.

We know at least that 37km is an upper bound of the best solution

Perhaps a better choice is to use the

nearest neighbor algorithm: Start from A and move always

to the nearest unvisited city.
Remember to come back to A.

ABDECA with total weight 42km.

Not a wise choice! The best upper bound remains 37km.

73
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

 A LOWER BOUND USING THE DELETED VERTEX ALGORITHM

For reasons we are not going to explain (sorry for that), the

following algorithm gives us a lower bound for the best solution to

the problem. It is called deleted vertex algorithm,

 Select a vertex, say X.

 Let a, b be the weights of the shortest edges from X
 Delete X together with all its edges from X.
 On remaining subgraph, find a spanning tree of minimum
weight (apply perhaps PRIM). Let c be its total weight
 Then a+b+c is a lower bound of the best solution.

EXAMPLE 1 (for our graph above)

let us select A (they will tell us which to delete!).

The two smallest weights from A are 5 and 7.
The remaining subgraph is (BCDE)
The minimum spanning tree (ED, BD, BE) has weight 22.
Hence, a lower bound is 5+7+22 = 34

We know that the best solution is between 34 and 37 (inclusive).

Perhaps, another starting point will give a better result. Indeed,

let us select C
The two smallest weights from C are 10 and 11.
The remaining subgraph is (ABDE) has a minimum spanning
tree of weight 16
Hence, a lower bound is 10+11+16 = 37

We were lucky! The best solution is between 37 and 37. So it is 37.

This is not always the case. Our target in general is to find some

good lower and upper bounds.

74
TOPIC 3: GEOMETRY AND TRIGONOMETRY Christos Nikolaidis

FINAL NOTICE

What we have seen is the Classical TSP where

 The graph is complete.

 For each pair of vertices X and Y, the shortest path is the
edge XY. (Euclidian property)

[I didn’t say that at the beginning of the paragraph in order to

wheedle you!]

In practice, the graph may be not complete, and between two

vertices X and Y there may be a shortest path than the edge XY.

This is the Practical TSP.

We can easily transform the Practical TSP into the Classical TSP:

 If there is no path between B and C we add a fake edge BC.

The weight of this edge will be that of the shortest path B to C

 If there is a path from B to C which is shorter than the edge BC

we replace the weight of BC by this new better weight.

Of course, after we find the solution, the salesman has to follow the

real route BAC in both cases.

[I hope that this is just for information and not for exams!]

75