Chapter 1 : Basic definitions page 1

Chapter 1 : Basic definitions

Chapter 1 outline :

1. Presentation
2. Intuitive definition of a graph
3. Mathematical definition of a graph
4. Order, orientation, and multiplicity
4.1. Order
4.2. Orientation
4.3. Multiplicity
5. Relations between the elements of a graph
5.1. Relations between vertices
5.2. Relations between arcs and vertices
5.3. Qualifiers of graphs
6. Matrices associated with a graph
6.1. Vertex-arc incidence matrix
6.2. Adjacency or vertex-vertex incidence matrix
6.3. Vertex-edge incidence matrix
6.4. Condensed form of sparse matrices
7. Other graph representations
7.1. Representation by linked lists
7.2. Tabular representations
8. Vocabulary related to connectivity
8.1. Chain, path, and length
8.2. Connectivity
8.3. Circuit and cycle
8.4. Cocycle and cocircuit

1. Presentation
Graphs model many concrete situations where interacting objects are involved.
 Road, rail or air interconnections between different urban areas,
 Links between the components of an electronic circuit,
 The plan of a city and its one-way streets,...
Graphs make it easier to manipulate objects and their relationships with a natural graphical
representation. All the mathematical techniques and tools developed in Graph Theory make it
easy to demonstrate properties, to deduce resolution methods, algorithms, ...

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 2

 What is the shortest path (in distance or time) to get from one city to another ?
 How can we minimize the total length of connections in a circuit ?
 Can we make one-way street without making impossible a circulation in the city ?

2. Intuitive definition of a graph

A graph describes a set (non-empty and finite) of objects and their relationships, i.e. the links
between the objects.
• The objects are called nodes, or vertices of the graph.
• A link between two objects is called an arc (or edge).

Example 1 :
In the following example, we have :
- A set of vertices : {1,2,3,4}
- A set of arcs : {(1,2) , (1,3), (3,2) , (3,4) , (4,3)}

Fig.1. Graph example 1

Example 2 :
In the following example, we have :
- A set of vertices : {1,2,3,4,5,6}
- A set of edges : {⌈1,2⌉, ⌈1,5⌉, ⌈2,5⌉, ⌈2,3⌉, ⌈3,4⌉, ⌈4,5⌉, ⌈4,6⌉}

Fig.2. Graph example 2

3. Mathematical definition of a graph
Mathematically, a graph 𝐺 is represented by a pair of two sets 𝐺 = (𝑋, 𝑈) where :

 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } is the set of nodes (or vertices)

 and 𝑈 = {𝑢1 , 𝑢2 , … , 𝑢𝑚 } is the set of cartesian product elements :
𝑋 × 𝑋 = {(𝑥, 𝑦)/𝑥 ∈ 𝑋, 𝑦 ∈ 𝑋}.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 3

4. Order, orientation, and multiplicity

4.1. Order
The number of vertices present in a graph 𝐺 = (𝑋, 𝑈) is the order of the graph.
The order of 𝐺 is therefore the cardinality of 𝑋 and denoted by |𝑋|.

Example :
The graph in figure Fig.1. is of order 4.
The graph in figure Fig.2. is of order 6.

4.2. Orientation
4.2.1. Oriented graph :
A graph 𝐺 is directed if its links can only be traversed in one direction. The orientation of the
links is indicated by arrows on the links. A directed link is called an arc and is denoted by 𝑢
(see Fig.1.).
The arc 𝑢 is presented as follows :

Fig.3. Arc 𝑢 = (𝑥𝑖 , 𝑥𝑗 )

The vertex 𝑥𝑖 is its starting point and 𝑥𝑗 is its endpoint.
An arc (𝑥𝑖 , 𝑥𝑖 ) is called a loop.

Fig.4. Loop
4.2.2. Undirected graph :
It is made up not of couples, but of unordered pairs of vertices.

When studying some properties, it happens that the orientation of the links plays no role. We
are simply interested in the existence of link(s) between two vertices (without specifying the
order). A link without orientation is called an edge (see Fig.2.).

𝑈 is not made up of couples, but of unordered pairs of vertices.

Remark :
In the undirected case, instead of writing 𝐺 = (𝑋, 𝑈) and 𝑢 = (𝑥𝑖 , 𝑥𝑗 ), it is often preferred to
use the notation 𝐺 = (𝑋, 𝐸) et 𝑒 = ⌈𝑥𝑖 , 𝑥𝑗 ⌉.

4.3. Multiplicity
The multiplicity of the arc 𝑢 is called the number 𝑚𝑖𝑗 defined by :

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 4

𝑚𝑖𝑗 = |{𝑢 ∈ 𝑈/𝑢 = (𝑥𝑖 , 𝑥𝑗 )}|.

Two arcs 𝑢1 and 𝑢2 are called parallel if they have the same endpoints (initial and final).
A set of 𝑝 parallel arcs is called a multiple arc, 𝑝 is the multiplicity (𝑝 = 𝑚𝑖𝑗 ).
The multiplicity of the graph 𝐺 is called the number 𝑚(𝐺) defined by :
𝑚(𝐺) = 𝑚𝑎𝑥𝑢∈𝑈/𝑢∈(𝑥𝑖 ,𝑥𝑗) {𝑚𝑖𝑗 }
A p-graph, where 𝑝 = 𝑚(𝐺), is a graph in which there are never more than 𝑝 arcs of the
form (𝑖, 𝑗) between any two vertices.

Example :

Fig.5. 3-graph of order 3 Fig.6. 1-graph of order 3

Remarks :
- A multigraph 𝐺 = (𝑋, 𝐸) is a graph in which there can be multiple edges between two
vertices.
- A graph 𝐺 = (𝑋, 𝐸) is simple :
i. if it is not a multigraph ;
ii. there are no loops.

Example :

Fig.7. A multigraph of order 5 Fig.8. A simple graph of order 5

5. Relations between the elemenets of a graph

5.1. Relations between vertices
5.1.1. Adjacency :
Two vertices are adjacent (or neighbors) if they are joined by an arc (or an edge).
5.1.2. Successor and predecessor nodes :
- The successors set of a node 𝑥𝑖 is denoted by :
Г+
𝐺 (𝑥𝑖 ) = {𝑥𝑗 ∈ 𝑋 / 𝑢 = (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈}

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 5

- The predecessors set of a node 𝑥𝑖 is denoted by :

Г−
𝐺 (𝑥𝑖 ) = {𝑥𝑗 ∈ 𝑋 / 𝑢 = (𝑥𝑗 , 𝑥𝑖 ) ∈ 𝑈}.

- The neighbors set of 𝑥𝑖 in the graph 𝐺 is denoted by :

ГG (𝑥𝑖 ) = Г+ −
𝐺 (𝑥𝑖 ) ∪ Г𝐺 (𝑥𝑖 ).

Example :

𝑥2 Г+
𝐺 (𝑥1 ) = {𝑥1 , 𝑥5 } Г−
𝐺 (𝑥1 ) = {𝑥1 , 𝑥2 , 𝑥3 }
𝑥1 + −
Г𝐺 (𝑥2 ) = {𝑥1 } Г𝐺 (𝑥2 ) = {𝑥5 }
Г+
𝐺 (𝑥3 ) = {𝑥1 , 𝑥4 } Г−
𝐺 (𝑥3 ) = ∅
Г+
𝐺 (𝑥4 ) = {𝑥5 }
−
Г𝐺 (𝑥4 ) = {𝑥3 , 𝑥5 }
+
𝑥3 𝑥4 𝑥5 Г𝐺 (𝑥5 ) = {𝑥2 , 𝑥4 } Г−
𝐺 (𝑥5 ) = {𝑥1 , 𝑥4 }

Fig.9. 1-graph of order 5

Remark :
If 𝐺 is a 1-graph, then 𝐺 can be defined by the set of its vertices 𝑋 and by the correspondence
Г = Г+ . Г is called a multivalued mapping associated with 𝐺.

5.1.3. Multivalued mapping of a graph

Example :

Fig.10. multivalued mapping

Let :
𝐺 = < 𝑋, 𝑈 >
𝑋 = {1,2,3}
𝑈 = {𝑢1 , 𝑢2 , 𝑢3 } = {(1,2), (1,3), (2,3)}
Vertex 1 : Г1 is the successors set of vertex 1
Vertex 𝑖 : Г𝑖 is the successors set of vertex 𝑖
Г𝑖 is the multivalued mapping that corresponds to 𝑋 a part of 𝑋
Г𝑖 ∶ 𝑋 → 𝑃(𝑋)
Г1 = {2,3}
Г2 = {3}
Г3 = ∅
We can also define the graph by its multivalued mapping :

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 6

𝐺 =< 𝑋, Г >=< 𝑋, 𝑈 >

𝑋 = {1,2,3}
Г = {Г1 , Г2 , Г3 } such that :
Г1 = {2,3}
Г2 = {3}
Г3 = ∅
Remarks :
- If Г𝐺 (𝑥𝑖 ) = ∅ then 𝑥𝑖 is an isolated vertex.
- If 𝐴 ⊂ 𝑋, 𝑥 ∈ 𝑋 and 𝑥 ∉ 𝐴, we define Г𝐺 (𝐴) = ⋃𝑎∈𝐴 Г𝐺 (𝑎). If 𝑥 ∈ Г𝐺 (𝐴) then we
say that 𝑥 is an adjacent vertex to the set 𝐴.

Example :
In the example of figure Fig.9., if we define the set 𝐴 as follows :

𝐴 = {𝑥1 , 𝑥2 } ⊂ 𝑋, Г𝐺 (𝐴) = Г𝐺 (𝑥1 ) ∪ Г𝐺 (𝑥2 ) = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 } ∪ {𝑥1 , 𝑥5 } = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 }

then 𝑥3 is adjacent to 𝐴 because 𝑥3 ∈ 𝑋, 𝑥3 ∉ 𝐴 and 𝑥3 ∈ Г𝐺 (𝐴).

5.1.4. Degree and half-degree :

We call the exterior half-degree of a vertex 𝑥, and we denote by 𝑑+ (𝑥) the number :

𝑑 + (𝑥) = |{𝑢 ∈ 𝑈/𝑥 𝑖𝑠 𝑡ℎ𝑒 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 𝑒𝑛𝑑𝑝𝑜𝑖𝑛𝑡 𝑜𝑓 𝑢}|

Similarly, the interior half-degree of 𝑥, denoted 𝑑 − (𝑥), is the number :

𝑑 − (𝑥) = |{𝑢 ∈ 𝑈/𝑥 𝑖𝑠 𝑡ℎ𝑒 𝑓𝑖𝑛𝑎𝑙 𝑒𝑛𝑑𝑝𝑜𝑖𝑛𝑡 𝑜𝑓 𝑢}|

The degree of a vertex 𝑥, denoted 𝑑(𝑥), is the number :

𝑑(𝑥) = 𝑑+ (𝑥) + 𝑑 − (𝑥)
and it is the number of arcs that have an endpoint at 𝑥.

Remark :
A loop is counted twice.
Special cases :
- A vertex 𝑥 ∈ 𝑋 such that 𝑑(𝑥) = 0 is called an isolated vertex.
- A vertex 𝑥 ∈ 𝑋 such that 𝑑(𝑥) = 1 is called a pendant vertex.
- We denote by 𝛿(𝐺) = 𝑚𝑖𝑛𝑥∈𝑋 {𝑑(𝑥)}, the minimum degree of 𝐺 ;
and by ∆(𝐺) = 𝑚𝑎𝑥𝑥∈𝑋 {𝑑(𝑥)}, the maximum degree of 𝐺.

Remark :
When 𝛿(𝐺) = ∆(𝐺) = 𝑘 (i.e. ∀𝑥 ∈ 𝑋, 𝑑(𝑥) = 𝑘), the graph 𝐺 is called k-regular.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 7

5.2. Relations between arcs and vertices

5.2.1. Adjacency :
Two arcs (or two edges) are adjacent if they have at least one common endpoint.

5.2.2. Vertex and incident arc :

A vertex 𝑥 is called incident outside the arc 𝑢 if 𝑥 is the initial endpoint of 𝑢.
An arc 𝑢 is called incident outside the vertex 𝑥 if 𝑥 is the initial endpoint of 𝑢.

A vertex 𝑥 is called incident inside the arc 𝑢 if 𝑥 is the final endpoint of 𝑢.

An arc 𝑢 is called incident inside the vertex 𝑥 if 𝑥 is the final endpoint of 𝑢.

A pendant arc is incident at a pendant vertex.

An arc 𝑢 is called incident to 𝐴 ⊂ 𝑋 outward if the initial endpoint of 𝑢 ∈ 𝐴 but not its final
endpoint, and we denote it as 𝑢 ∈ 𝜔𝐺+ (𝐴).
An arc 𝑢 is called incident to 𝐴 ⊂ 𝑋 inward if the final endpoint of 𝑢 ∈ 𝐴 but not its initial
endpoint, and we denote it as 𝑢 ∈ 𝜔𝐺− (𝐴).

The incident arcs set to A is denoted as : 𝜔𝐺 (𝐴 ) = 𝜔𝐺+ (𝐴) ∪ 𝜔𝐺− (𝐴)

5.3 Qualifiers of graphs

5.3.1. Symmetric graph :
A graph 𝐺 = (𝑋, 𝑈) is called symetric if and only if :
∀𝑥𝑖 , 𝑥𝑗 ∈ 𝑋, (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 ⇒ ( 𝑥𝑗 , 𝑥𝑖 ) ∈ 𝑈
Example :

Fig.11. Symetric graph

5.3.2. Antisymmetric graph :

A graph 𝐺 = (𝑋, 𝑈) is called antisymmetric if and only if :
∀ 𝑥𝑖 , 𝑥𝑗 ∈ 𝑋, (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 ⇒ (𝑥𝑗 , 𝑥𝑖 ) ∉ 𝑈

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 8

Example :

Fig.12. Antisymmetric graph

5.3.3. Transitive graph :

A graph 𝐺 = (𝑋, 𝑈) is called transitive if and only if :
∀ 𝑥𝑖 , 𝑥𝑗 , 𝑥𝑘 ∈ 𝑋, (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 𝑎𝑛𝑑 (𝑥𝑗 , 𝑥𝑘 ) ∈ 𝑈 ⇒ (𝑥𝑖 , 𝑥𝑘 ) ∈ 𝑈

Example :

Fig.13. Transitive graph

5.3.4. Complete graph :

A graph 𝐺 = (𝑋, 𝑈) is called complete if 𝑚 𝑖𝑗 ≥ 1 for every arc 𝑢 = (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈.
A complete graph is a graph in which all the vertices are adjacent.
if 𝐺 is a 1-graph, it is complete if we have : ∀ 𝑥𝑖 , 𝑥𝑗 ∈ 𝑋, (𝑥𝑖 , 𝑥𝑗 ) ∉ 𝑈 ⇒ (𝑥𝑗 , 𝑥𝑖 ) ∈ 𝑈.

Remark :
A complete and simple graph on 𝑛 vertices is denoted 𝐾𝑛 and is called an n-clique.
Example :

Fig.14.Complete graph Fig.15.Incomplete graph

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 9

5.3.5. Complementary graph :

To a simple graph 𝐺 = (𝑋, 𝑈), a complementary graph 𝐺̅ = (𝑋, 𝑈
̅) can be defined as follows :
̅ ⇔ 𝑢 ∉ 𝑈.
𝑢∈𝑈
That is to say : an edge (an arc) belongs to the complementary graph (𝐺̅ ) if it does not belong
to the initial graph 𝐺.

Example :

𝑥1 𝑥2 𝑥1 𝑥2
(𝐺) its complementary graph (𝐺̅ ) is :

𝑥3 𝑥4 𝑥3 𝑥4

Fig.16. Complementary graph

Consequence : 𝐺 ∪ 𝐺̅ is a complete simple graph, therefore a 𝐾𝑛 .
5.3.6. Bipartite graph :
A graph 𝐺 = (𝑋, 𝑈) is called bipartite if the set of its vertices 𝑋 can be partitioned into two
classes 𝑋1 and 𝑋2 such that : (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 ⇒ 𝑥𝑖 ∈ 𝑋1 𝑎𝑛𝑑 𝑥𝑗 ∈ 𝑋2.

𝑥1 𝑥3

𝑥2 𝑥4

X1 X2

Fig.17. Bipartite graph

5.3.7. Multipartite graph :
A graph 𝐺 = (𝑋, 𝑈) is multipartite if the set of its vertices 𝑋 can be partitioned into 𝑝 classes
(𝑝 ≥ 3) {𝑋1 , 𝑋2 , … , 𝑋𝑝 }, such that : 𝑖𝑓 (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 𝑎𝑛𝑑 𝑥𝑖 ∈ 𝑋𝑘 ⇒ 𝑥𝑗 ∈ 𝑋𝑘+1 .

𝑥1 𝑥3
𝑥5

𝑥2 𝑥4

X1 X2 X3
Fig.18. Multipartite graph

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
 Chapter 1 : Basic definitions page 10

5.3.8. Empty graph :

A graph that does not contain any arcs or edges is called an empty graph.
Example :
𝑎 𝑏

Fig.19. Empty Graph

5.3.9. Subgraph, partial graph, and partial subgraph :
To characterize the structure of a graph in a less local way, it is possible to search for notable
parts of the graph, by restricting either the set of vertices (subgraph), or the set of edges
(partial graph).

A subgraph of 𝐺 consists of considering only a part of the vertices of 𝑿 and the links induced
by 𝑼.
The subgraph generated by a set 𝐴 ⊂ 𝑋 is the graph 𝐺𝐴 = (𝐴, 𝑊) whose vertices are the
points of 𝐴 and whose arcs 𝑊 are those of 𝐺 that have both endpoints in 𝐴.
For example, if 𝐺 represents the daily air connections between the main cities of the world, a
possible subgraph is to limit it to the daily connections between the main European cities.

A partial graph of 𝐺 consists of considering only a part of the edges of 𝑼.

The partial graph generated by a subset 𝑉 ⊂ 𝑈 is the graph 𝐺’ = (𝑋, 𝑉). In other words, we
remove the arcs from 𝑈 − 𝑉 in 𝐺.
Taking the same example, a possible partial graph is to consider only the daily connections of
less than 3 hours between the main cities of the world.

A partial subgraph of 𝐺 is a partial graph of a subgraph of 𝐺.

Let 𝐺 = (𝑋, 𝑈) be a graph and 𝐴 ⊂ 𝑋 and 𝑉 ⊂ 𝑈. The graph 𝐺𝐴,𝑉 = (𝐴, 𝑉𝐴 ) such that 𝑉𝐴 is
the set of arcs of 𝐺 having their 2 endpoints in 𝐴.
Example :

Fig.20. A graph G Fig.21. A sub-graph of G Fig.22. A partial graph of G Fig.23. A partial sub-graph
of G

6. Matrices associated with a graph

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 11

6.1. Vertex-arc incidence matrix

A graph = (𝑋, 𝑈) without loops can be represented by an 𝑛 × 𝑚 matrix (where

𝑛 = |𝑋| 𝑎𝑛𝑑 𝑚 = |𝑈|), called an incidence matrix, which can only contain the values
0, 1, −1. Each row of the matrix is associated with a vertex and each column with an arc.
Thus, a box indicates the relationship that exists between a vertex and an arc :

 0 means that the vertex and the arc are not adjacent,
 1 means that the vertex is the initial endpoint of the arc,
 -1 means that the vertex is the terminal endpoint of the arc.

Example :
Consider the graph below :

Fig.24. A graph 𝐺 = (𝑋, 𝑈)

This graph can be represented by the following matrix :

a b c d e f g h
1 1 1 0 0 0 0 0 0
2 -1 0 -1 1 0 0 0 0
3 0 -1 1 0 -1 0 -1 0
4 0 0 0 -1 1 1 0 -1
5 0 0 0 0 0 -1 1 1
6.2. Adjacency or vertex-vertex incidence matrix
Definition 1 :
A graph 𝐺 = (𝑋, 𝑈) can be represented by an 𝑛 × 𝑛 matrix (𝑛 = |𝑋|), called an adjacency
matrix, which can only contain the values 0, 1. Each row and each column of the matrix
represents a vertex. Thus, a box indicates the relationship that exists between two vertices :

 0 means that the two vertices are not connected by an arc,

 1 means that the two vertices are connected by an oriented arc.

Example :

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 12

The previous graph (Fig.24.) will be represented by the following matrix.

1 2 3 4 5
1 0 1 1 0 0
2 0 0 0 1 0
3 0 1 0 0 0
4 0 0 1 0 1
5 0 0 1 1 0

Definition 2 :
The vertex-vertex adjacency or incidence matrix (also called the associated matrix) of a graph
𝐺 = (𝑋, 𝑈) is a square matrix where each row corresponds to a vertex of 𝐺 and each column
also corresponds to a vertex of 𝐺. The elements of the associated matrix indicate the number
of oriented arcs in the same direction connecting two vertices. The general term of the matrix
is :
𝑎𝑖𝑗 = 𝑚𝐺+ (𝑥𝑖 , 𝑥𝑗 ).

𝑚𝐺+ (𝑥𝑖 , 𝑥𝑗 ) : the multiplicity of a pair (𝑥𝑖 , 𝑥𝑗 ), is the number of arcs (in the graph 𝐺 ) having 𝑥𝑖
as the initial endpoint and 𝑥𝑗 as the final endpoint.

Remark :
Unlike the vertex-arc incidence matrix, loops can be represented using this matrix.

Example :
Consider the graph below :

Fig.25. A graph 𝐺 = (𝑋, 𝑈)

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 13

This graph can be represented by the following matrix :

a b c d e f g h
a 0 0 0 0 0 0 0 0
b 0 0 0 0 0 0 0 1
c 0 0 1 0 0 0 0 0
d 0 0 0 0 1 0 0 1
e 0 0 0 0 0 1 0 1
f 0 0 0 0 2 0 0 0
g 0 0 1 0 0 0 0 0
h 0 0 0 0 0 0 0 0
6.3. Vertex-edge incidence matrix
A graph 𝐺 = (𝑋, 𝐸) can be represented by an 𝑛 × 𝑚 matrix
(𝑤ℎ𝑒𝑟𝑒 𝑛 = |𝑋| 𝑎𝑛𝑑 𝑚 = |𝐸|), known as an incidence matrix, which can only contain the
values 0 𝑎𝑛𝑑 1. Each row of the matrix is associated with a vertex and each column with an
edge. Thus, a box indicates the relationship that exists between a vertex and an edge.

 0 means that the vertex and the edge are not adjacent,
 1 means that the edge is incident to the vertex.

6.4. Condensed form of sparse matrices

It is immediately noticeable that the two previous incidence matrices are sparse matrices :
many terms are zero. It is therefore possible to write each of the matrices in condensed form,
that’s to say, to "identify" the non-zero terms by their position in the matrix or by the SIF
matrix ["Initial Vertex Final Vertex"] if the arcs are numbered.

Example :
The arcs of figure Fig.24., being numbered from 𝑎 to ℎ. We can write the SIF matrix as
follows:

𝐴𝑟𝑐 𝑉𝐼𝑁𝐼𝑇 𝑉𝐹𝐼𝑁

𝑎 1 2
𝑏 1 3
𝑐 3 2
𝑑 2 4
𝑒 4 3
𝑓 4 5
𝑔 5 3
ℎ ( 5 4 )

The condensed form of the vertex-vertex incidence matrix of the graph in Fig.25. is as
follows:

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 14

𝑥𝑖 𝑥𝑗 𝑚𝐺+ (𝑥𝑖 , 𝑥𝑗 )
𝑏 ℎ 1
𝑐 𝑐 1
𝑑 𝑒 1
𝑑 ℎ 1
𝑒 𝑓 1
𝑒 ℎ 1
𝑓 𝑒 2
(𝑔 𝑐 1)
7. Other graph representations
7.1. Representation by linked lists
A graph can be represented by lists. We propose here one possibility, but many others can be
suitable. First, we define a list of nodes and to each node, we associate a list of successor
nodes and a list of predecessor nodes.

Example :
The graph in Figure Fig.24. will be represented as follows :

Predecessors Nodes Successors

7.2. Tabular representations

7.2.1. Table representation of arcs
For this, we use two tables 𝐼𝑁 𝑎𝑛𝑑 𝑇𝑁 where :
𝐼𝑁[𝑖] = 𝐼(𝑢𝑖 ) ; initial endpoint of the arc 𝑢𝑖 , 𝑖 = 1 … 𝑚.
𝑇𝑁[𝑖] = 𝑇(𝑢𝑖 ) ; terminal endpoint of the arc 𝑢𝑖 , 𝑖 = 1 … 𝑚.
Example :
Let’s represent the graph given by the figure Fig.24. using an arc table :
a b c d e f g h
IN 1 1 3 2 4 4 5 5

a b c d e f g h
TN 2 3 2 4 3 5 3 4

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 15

7.2.2. Representation by successor table

For this, we use two tables 𝑆𝑃 and 𝑆𝐿 where :

𝑆𝑃[𝑖] : (for all 𝑥𝑖 ∈ 𝑋) points to the first successor of vertex 𝑥𝑖 in the list 𝑆𝐿.

𝑆𝐿 : contains for each vertex the set of its successors.

Example :
The successor table representation of the graph shown in figure Fig.25.is given by :
a b c d e f g h
SP 0 1 2 3 5 7 9 0

1 2 3 4 5 6 7 8 9
SL h c e h f h e e c
Remark :
The absence of a successor for a vertex is encoded by a zero in 𝑺𝑷.

8. Vocabulary related to connectivity

8.1. Chain, path and length

In a graph, it is natural to want to move from vertex to vertex along the edges. Such a walk is
called a chain (undirected graph) or a path (directed graph).

A certain number of questions may then arise :

 For two vertices of the graph, is there a path to go from one to the other ?
 What is the set of vertices that can be reached from a given vertex ?
 How to find the shortest path from one vertex to another ?

A path from 𝑥 to 𝑦 is a chain in which the arcs are oriented and such that :
 𝑥 is the initial endpoint of the first arc,
 𝑦 is the terminal endpoint of the last arc,
 all subsequent neighbors of a vertex in a (oriented) path are its descendants,
 all previous neighbors of a vertex in a (oriented) path are its ancestors,
 the terminal endpoint of an arc is the initial endpoint of the arc that follows it in the
sequence.

The length of the path or chain corresponds to the number of arcs or edges traversed.
A simple path is a path that does not contain the same arc multiple times.
A simple chain is a chain that does not contain the same edge multiple times.
An elementary path is a path that does not pass through a node more than once.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 16

An elementary chain is a chain that does not pass through a node more than once.
Example :
Consider the graph below :

 𝑐ℎ1 = ((𝐴; 𝐶), (𝐶; 𝐸)) is a path from 𝐴 to 𝐸 of length 2.

 𝑐ℎ2 = ((𝐴; 𝐶), (𝐶; 𝐹), (𝐹; 𝐴), (𝐴; 𝐶), (𝐶; 𝐸)) is a path from 𝐴 to 𝐸 of length 5.
 𝑐ℎ3 = ((𝐴; 𝐶), (𝐶; 𝐹), (𝐹; 𝐷), (𝐷; 𝐶), (𝐶; 𝐸)) is a path from 𝐴 to 𝐸 of length 5.
 𝑐ℎ4 = ((𝐴; 𝐵), (𝐵; 𝐷), (𝐷; 𝐸)) is a chain from 𝐴 to 𝐸 of length 3.
 𝑐ℎ5 = ((𝐴; 𝐵), (𝐵; 𝐷), (𝐷; 𝐶), (𝐶; 𝐴), (𝐴; 𝐵), (𝐵; 𝐷), (𝐷; 𝐸)) is a chain from 𝐴 to 𝐸 of
length 7.
 𝑐ℎ6 = ((𝐴; 𝐵), (𝐵; 𝐷), (𝐷; 𝐶), (𝐶; 𝐹), (𝐹; 𝐷), (𝐷; 𝐸)) is a chain from 𝐴 to 𝐸 of length
6.

8.2. Connectivity
8.2.1. Connectivity in an undirected graph
We define on the vertices set of a graph 𝐺 = (𝑋, 𝑈) the binary relation 𝑅, called the
connectivity relation, defined by :

𝑥 = 𝑦 (𝑖𝑠𝑜𝑙𝑎𝑡𝑒𝑑 𝑣𝑒𝑟𝑡𝑒𝑥)
𝑥 𝑅 𝑦 (𝑥 𝑎𝑛𝑑 𝑦 ℎ𝑎𝑣𝑒 𝑎 𝑐𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑣𝑖𝑡𝑦 𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠ℎ𝑖𝑝) ⇔ { 𝑜𝑟
∃ 𝑎 𝑐ℎ𝑎𝑖𝑛 𝑙𝑖𝑛𝑘𝑖𝑛𝑔 𝑥 𝑡𝑜 𝑦

A graph 𝐺 = (𝑋, 𝑈) is connected if ∀ 𝑥, 𝑦 ∈ 𝑋, there exists a chain between 𝑥 and 𝑦.

The binary relation 𝑅 is an equivalence relation (noted ≡) because :
𝑥≡𝑥 (𝑟𝑒𝑓𝑙𝑒𝑥𝑖𝑣𝑖𝑡𝑦)
{ 𝑥≡𝑦 ⇒𝑦≡𝑥 (𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑦)
𝑥 ≡ 𝑦 𝑒𝑡 𝑦 ≡ 𝑧 ⇒ 𝑥 ≡ 𝑧 (𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦)
A connected component is the subset of vertices such that between any two vertices, there
exists a connectivity relation. Moreover, any node outside the component has no connectivity
relationship with any elements of the component.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 17

A graph is called connected if it has only one connected component. Each connected
component is a connected graph.

A non-connected graph appears as the juxtaposition of a set graphs : its connected

components. We denote by 𝑝(𝐺) the connectivity number of the graph 𝐺 which is simply the
number of connected components.
Examples :

Fig.26. A connected undirected graph

Fig.27. Non-connected undirected graph G with 𝑝(𝐺) = 2

8.2.2. Connectivity in a directed graph

We define on the vertices set of a graph 𝐺 the binary relation 𝑅’, called the strong
connectivity relation, defined by :
𝑥 = 𝑦 (𝑖𝑠𝑜𝑙𝑎𝑡𝑒𝑑 𝑣𝑒𝑟𝑡𝑒𝑥)
𝑥 𝑅’ 𝑦 (𝑥 𝑒𝑡 𝑦 ℎ𝑎𝑣𝑒 𝑎 𝑠𝑡𝑟𝑜𝑛𝑔 𝑐𝑜𝑛𝑛𝑒𝑐𝑡𝑖𝑣𝑖𝑡𝑦 𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠ℎ𝑖𝑝) ⇔ { 𝑜𝑟
∃ 𝑎 𝑝𝑎𝑡ℎ 𝑙𝑖𝑛𝑘𝑖𝑛𝑔 𝑥 𝑡𝑜 𝑦

A directed graph 𝐺 = (𝑋, 𝑈) is strongly connected if ∀ 𝑥, 𝑦 ∈ 𝑋, there exists a path

connecting 𝑥 to 𝑦 ; in other words, there is a path from vertex 𝑥 to vertex 𝑦 and from vertex 𝑦
to vertex 𝑥. Therefore, there must necessarily be at least one circuit in a strongly connected
graph.

A directed graph is weakly connected if there is a chain between any pair of vertices in the
graph when the orientation of the arcs is not considered.

Remark :
A directed graph is connected if the associated undirected graph is connected.
A strongly connected component is the subset of vertices such that between any two vertices,
there exists a strong connectivity relation. Moreover, any node outside the component has no
strong connectivity relationship with any elements of the component.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 18

A graph is called strongly connected if it has only one strongly connected component. Each
strongly connected component is a strongly connected graph.
Examples :

Fig.28. Two connected oriented graphs

Fig.29. Non-connected oriented graph 𝐺 with 𝑝(𝐺) = 3

Fig.30. Strongly connected oriented graph

Fig.31. Non-strongly connected oriented graph 𝐺 with 𝑝(𝐺) = 4

8.3. Circuit and cycle

A circuit containing a node 𝑥 is a path from 𝑥 to 𝑥. A circuit is a circular sequence of arcs and
thus, unlike a path, a circuit has neither a beginning nor an end.
Similarly, a cycle containing a node 𝑥 is a chain from 𝑥 to 𝑥. A cycle is also a circular
sequence of edges.
A circuit (or a cycle) is elementary if the associated path (or chain) is elementary.

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi
Chapter 1 : Basic definitions page 19

Example :

(𝑢2 , 𝑢4 , 𝑢3 ) 𝑖𝑠 𝑎 𝑐𝑖𝑟𝑐𝑢𝑖𝑡 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 3

(𝑢1 , 𝑢5 , 𝑢9 , 𝑢7 , 𝑢2 ) 𝑖𝑠 𝑎 𝑐𝑦𝑐𝑙𝑒 𝑜𝑓 𝑙𝑒𝑛𝑔𝑡ℎ 5
Fig.32. A circuit and a cycle examples

8.4. Cocycle and cocircuit

8.4.1. Cocycle
Given a subset vertices 𝐴 of a graph 𝐺 = (𝑋, 𝑈), where 𝐴  𝑋, we define :
 𝑤 + (𝐴) = {𝑢 = (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈/𝑥𝑖 ∈ 𝐴 𝑎𝑛𝑑 𝑥𝑗 ∉ 𝐴} : the set of arcs having their initial
endpoint in 𝐴, and their final endpoint in (𝑋 − 𝐴) (called the set of arcs incident
externally to 𝐴).
 𝑤 − (𝐴) = {𝑢 = (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈/𝑥𝑖 ∉ 𝐴 𝑎𝑛𝑑 𝑥𝑗 ∈ 𝐴} : the set of arcs having their final
endpoint in 𝐴, and their initial endpoint in (𝑋 − 𝐴) (called the set of arcs incident
internally to 𝐴).
 𝑤(𝐴) = 𝑤 + (𝐴) ∪ 𝑤 − (𝐴) : set of arcs incident to 𝐴.
Any arcs set of the form 𝑤(𝐴) is called a cocycle of 𝐴.

8.4.2. Cocircuit
A cocircuit is a cocycle whose all arcs are oriented in the same direction, that’s to say a set of
arcs of the form 𝑤 + (𝐴) (outward from 𝐴) or 𝑤 − (𝐴) (inward to 𝐴).
Example :

{3} ∪ {4,9} 𝑖𝑠 𝑎 𝑐𝑜𝑐𝑦𝑐𝑙𝑒 𝑤𝑖𝑡ℎ 𝐴 = {𝑒, 𝑑, ℎ}

{9} 𝑖𝑠 𝑎 𝑐𝑜𝑐𝑖𝑟𝑐𝑢𝑖𝑡 𝑤𝑖𝑡ℎ 𝐴′ = {𝑒, 𝑑, ℎ, 𝑓}

Fig.33. Cocyle and cocircuit examples

Matière : Graph theory 2nd Year Bachelor of Computer Science – 3rd Semester Responsable de la matière : Amiar Lotfi