# Introduction to graph theory

## Introduction to graph theory

A graph is an object composed of vertices (or nodes) and edges (or arcs, in some cases) that connect the vertices. We can see a graph like a geographic map: the vertices are then cities and the edges are the roads that lead from one city to another.

There are two types of graphs:

•   Directed graph: relationships are oriented and we speak of an arc. An arc is represented by a couple of ordered vertices( Or nodes).
•   Undirected graph: relationships are not oriented and we therefore speak of edges. An edge is represented by a pair of unordered vertices.

#### Vocabulary

•   A loop is an arc that connects a vertex to itself. In an undirected graph, loops are prohibited and each edge is therefore made up of two distinct vertices.
•   Degree of a vertex: In an undirected graph, the degree of a vertex is the number of edges which are incident to it.
•   Indegree of a vertex : In a directed graph, the Indegree of a vertex is the number of arcs leaving it,
•   Outdegree of a vertex : In a directed graph, the Outdegree of a vertex is the number of incoming arcs
•   The degree of a vertex in a directed graph is the sum of Indegree and Outdegree.
•   Path: In a directed graph G = (S, A), a path of length k from a vertex u to a vertex v is a sequence (u0, u1, ..., uk) of vertices such that u = u0, v = uk and (ui-1, ui) belongs to A for all i. A path is elementary if its vertices are all distinct.
•   Walk: In a directed graph G = (S, A), a Walk (u0, u1, ...., uk) forms a circuit if u0 = uk and if the path contains at least one arc. This circuit is elementary if the vertices u1, ..., uk are distinct. A loop is a circuit of length 1.
•   Cycle: In the undirected case, a path v0v1, v1v2, ..., vk − 1vk is a cycle if v0 = vk and if an edge does not appear twice with a different orientation. For example v0v1, v1v0 is not a cycle in the non-oriented case. This cycle is elementary if the vertices u1, ..., uk are distinct. A graph without a cycle is said to be acyclic.
•   Connected graph: An undirected graph is connected if each pair of vertices is connected by a path. The connected components of a graph are the vertex equivalence classes induced by the relation "is accessible from".
•   Strongly connected graph: A Directed graph is strongly connected if for any pair of vertices x, y there exists a path connecting x to y.
Notes ! The definition implies that if x and y are two vertices of a strongly connected graph, then there is a path from x to y and a path from y to x.