1 of 17

Introduction to Graph Theory

Vertices and Edges: “Networks”

Important in Computer Science, Electrical Eng., Social Sciences…

part of

Data Structures�Discrete Mathematics, Graphs and Algorithms,

part of: Combinatorics

Prof. Hassane Bouzahir

(Just google my name)

1

ENSA Agadir, 2014

2 of 17

1. Graphs

  • Graph

A graph G = (V, E, γ) consists of a finite set V of objects called vertices, a finite set E of objects called edges, and a function γ that assigns to each edge a subset {v, w}, where v and w are vertices (endpoints of e) (and may be the same).

​

  • End points

If γ(e) = {v, w}, then vertices v and w are called the end points of e.

2

ENSA Agadir, 2014

3 of 17

1. Graphs

  • Example 1 & 2

Let V = {1, 2, 3, 4} and E = {e1, e2, e3, e4, e5}. Let γ be defined by γ(e1) = γ(e5) = {1, 2}, γ(e2) = {4, 3}, γ(e3) = {1, 3}, γ(e4) = {2, 4} .

Then G = (V, E, γ) is a graph.

​

3

1

2

4

3

G

1

2

3

4

G

1

2

4

3

G

Isomorphic representations of the graph

ENSA Agadir, 2014

4 of 17

1. Graphs

  • Degree. The degree of a vertex is the number of edges having that vertex as an end point.

To be precise: the degree of a vertex is the number of endpoints on that vertex, i. e., if an edge is from a vertex to itself, we count it two times.

  • Loop. An edge is referred to as a loop if the edge is from a vertex to itself.

Note: a loop contributes 2 to the degree of a vertex, since that vertex serves as both end points of the loop.

  • Isolated. A vertex with degree 0 is called an isolated vertex.

4

ENSA Agadir, 2014

5 of 17

1. Graphs

  • Example 3�

5

A

B

E

C

D

p

q

r

s

t

u

a

b

d

e

c

2

1

3

5

6

4

A: 2 B: 4

C: 1 D: 3 E: 2

a: 4 b: 2

c: 3 d: 1 e: 0

All vertices with

degree 2

ENSA Agadir, 2014

6 of 17

1. Graphs

  • Path in a Graph

A path п in a graph G consists of a pair (Vп, Eп) of sequences: a vertex sequence Vп : v1, v2, …, vk and an edge sequence E п : e1, e2,…,ek-1 for which

  1. Each successive pair vi, vi+1 of vertices is adjacent in G, and edge ei has vi and vi+1 as end points for i=1, …, k-1;

​

  • No edge occurs more than once in the edge sequence.

6

ENSA Agadir, 2014

7 of 17

1. Graphs

  • Circuit (cycle)

A circuit is a path that begins and ends at the same vertex.

​

  • Simple

A path is called simple if no vertex appears more than once in the vertex sequence, except possibly if v1= vk. In this case, the path is called a simple circuit.

7

ENSA Agadir, 2014

8 of 17

1. Graphs

  • Connected, Disconnected & Components

A graph is called connected if there is a path from any vertex to any other vertex in the graph. Otherwise, the graph is disconnected. If the graph is disconnected, the various connected pieces are called the components of the graph.

8

A

B

E

C

D

p

q

r

s

t

u

Connected

- Disconnected

-Two components

2

1

3

5

6

4

ENSA Agadir, 2014

9 of 17

1. Graphs

Some important special families of graphs will be useful in our discussions.

  1. Un (discrete graph) denotes the graph with n vertices and no edges.

​

​

  • Ln (linear graph) denotes the graph with n vertices and with edges {vi,vi+1} for 1≤ i <n

​

9

U2

U5

L2

L5

ENSA Agadir, 2014

10 of 17

1. Graphs

  1. Kn (complete graph) denotes the graph with n vertices and with an edge {vi, vj } for all i and j.

​

​

​

​

  • Regular

If each vertex of a graph has the same degree as every other vertex, the graph is called regular, e.g., Kn (n=2, 3, 4, 5) above.

10

K3

K4

K5

K2=L2

ENSA Agadir, 2014

11 of 17

1. Graphs

  • Subgraph

Suppose that G = (V, E, γ) is a graph. Choose a subset E1 of the edges in E and a subset V1 of the vertices in V, so that V1 contains (at least) all the end points of edges in E1. Then H = (V1, E1, γ1) is also a graph where γ1 is γ restricted to edges in E1. Such a graph H is called a subgraph of G.

11

ENSA Agadir, 2014

12 of 17

1. Graphs

  • The subgraph Ge

Deleting one edge and no vertices

​

​

​

​

​

12

b

a

c

d

i

f

g

h

G

b

a

c

d

i

f

g

h

Ge

e = {a, b}

ENSA Agadir, 2014

13 of 17

1. Graphs

  • Example 8

13

b

a

c

d

i

f

g

h

c

d

i

f

g

h

b

c

d

i

f

g

h

b

a

c

d

i

f

g

h

G

ENSA Agadir, 2014

14 of 17

1. Graphs

  • Example 9 (Quotient graph GR)

Let G be the graph (without multiple edges) of the following figure, and let R be the equivalence relation on V defined by the partition.

{{a, m, i}, {b, f, j}, {c, g, k}, {d, h, l}}

14

f

m

g

h

i

j

k

l

b

a

c

d

[a]

[b]

[c]

[d]

GR

[m]

[j]

[k]

[h]

=

GR

ENSA Agadir, 2014

15 of 17

1. Graphs

  • Example 9

If S is also an equivalence relation on V defined by the partition.

{{i, j, k, l}, {a, m}, {f, b, c}, {d}, {g}, {h}}

15

f

m

g

h

i

j

k

l

b

a

c

d

[a]

[i]

[b]

[h]

[g]

[d]

GS

ENSA Agadir, 2014

16 of 17

1. Graphs

  • The Quotient graph Ge

If e is an edge between vertex v and w in a graph G = {V, E, γ}, then we consider the equivalence relation whose partition consists of {v, w} and {vi}, for each vi ≠ v, vi ≠ w. (merging v and w and leaving others alone)

16

f

m

g

h

[i]

k

l

b

a

c

d

Ge

f

m

g

h

i

j

k

l

b

a

c

d

G

e = {i, j}

ENSA Agadir, 2014

17 of 17

1. Graphs

  • Homework

Ex. 6, Ex. 16, Ex. 20, Ex. 22, Ex. 23, Ex. 29

17

ENSA Agadir, 2014