Contenus

Toggle## Graph theory

In graph theory, a graph **G** is defined by a couple (S, A) with **S** a finite set of vertices, and **TO** a finite set of pair of vertices (s_{i}, s_{j}) in S².

In a directed graph, the pairs (s_{i}, s_{j}) of **TO** are oriented, i.e. s_{i} is the initial vertex and s_{j} the terminal vertex. Graphically, this couple is a **bow **from the top s_{i} towards the top s_{j}.

In an undirected graph, the pairs (s_{i}, s_{j}) are not oriented. Thus, (s_{i}, s_{j}) is equivalent to writing (s_{j}, s_{i}). Graphically, this couple is a **fish bone** between vertices s_{i} and s_{j}.

Elements of terminology:

- THE'
**order**of a graph is the number of its vertices | S |. - A
**loop**is an arc or an edge (s_{i}, s_{i}). - An undirected graph is said
**simple**if it does not contain a loop and if it has at most one edge between any pair of vertices. Otherwise it is a multi-graph. - A directed graph is said
**elementary**if it does not contain a loop. - A directed graph is a
**p-graph**if it has at most*p*arcs between any pair of vertices. - A graph
**partiel**of a graph is the graph obtained by removing certain arcs (or edges). - a
**subgraph**of a graph is the graph obtained by removing certain vertices and all the arcs incident to the removed vertices. - A graph is said
**full**if it has an edge (s_{i}, s_{j}) for any pair of vertices (or two arcs (s_{i}, s_{j}) and (s_{j}, s_{i})). A complete simple graph with n vertices will have n (n-1) / 2 edges. - a
**attribute**can be associated with (s_{i}, s_{j}). The attribute can be a letter, a word or a weight (numeric value). A graph with weights is called**Network**.

Consider a graph G = (V, E, w) with a weight function:

Notions of adjacency:

- In an undirected graph, a vertex s
_{i}is said**adjacent**at a summit s_{j}if there is an edge between s_{i}and s_{j}. The set of vertices adjacent to a vertex s_{i}is defined by:

- In a directed graph, we distinguish the vertices
**successors**(terminals of an arc) and**predecessors**(initials of an arc):

Notions of degree of a vertex:

- In an undirected graph, the
**degree**of a vertex is the number of edges incident to this vertex. In the case of a simple graph we have:

- In a directed graph, the
**external half-degree**of a vertex is the number of arcs starting from this vertex. In a 1-graph we have:

- In a directed graph, the
**interior half degree**of a vertex is the number of arcs arriving from this vertex. In a 1-graph we have:

- The number of vertices of odd degree is even. The sum of all the degrees is twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of the even degree vertices is even, the sum of the degrees of the odd degree vertices must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of such vertices.

## Computer representation

There are two "academic" ways of representing a graph in a computer fashion: either by an adjacency matrix, or by adjacency lists.

We assume that the vertices of S are numbered from 1 to **not**. The adjacency matrix is a matrix **M** of size n * n such that M [i, j] = **value** if (i, j) in A, M [i, j] = **no value** otherwise. Within the framework of the presence of link between the vertex i and j, **value** = 1 and **no value** = 0. Within the framework of link valued between the vertex i and j, **value** = weighting and **no value** = infinite. In a non-oriented frame, the matrix will be symmetrical with the upper right triangle. This type of coding requires O (| S | ²) memory locations.

The representation by adjacency lists consists of an array **T** of **not** lists, one for each vertex of **S**. A linked list T [s_{i}] contains all the elements_{j} of **S** such that there is a link (s_{i}, s_{j}) in **TO**. That is, the list of successors of s_{i}. If the graph is valued, each link can contain information on the weighting. This type of encoding requires O (| S | + | A |) memory locations.

Each method has advantages and disadvantages depending on the operations that you want to perform on the graph.

## Pathways

**u**towards a summit

**v**is a sequence <s

_{0}, s

_{1},…, S

_{k}> vertices such that u = s

_{0}and v = s

_{k}, and (s

_{i}, s

_{(i + 1)}) is in

**TO**for

**i**from 0 to k-1. The length of the path is the number of arcs in the path, i.e.

**k**. If there is a path

**u**To

**v**, we will say that

**v**is accessible from

**u**. A path is elementary if the vertices it contains are all distinct. u is called Start, v is called End.

_{0}= s

_{k}and if the path has at least one arc. This circuit is elementary if the path <s

_{0},…, S

_{(k-1)}> (the circuit without the last vertex) is elementary. A loop is therefore a circuit of length 1. The graph is said to be acyclic if it has no circuit.

This can be calculated by transitive closure. The latter is the sum of **not** first powers of the adjacency matrix, n = | A |. The graph is strongly connected if the whole matrix has **value**. A strongly connected component is a strongly connected subgraph.

The same notions exist for undirected graphs under the name of chain and cycle. The graph is said to be connected and we speak of a connected component.