Graph Theory 101 - Complex systems and AI

Contents

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

In a directed graph, a path from a vertex u towards a summit v is a sequence <s₀, s₁,…, S_k> vertices such that u = s₀ 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.

A path forms a circuit if s₀ = s_k and if the path has at least one arc. This circuit is elementary if the path <s₀,…, 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.

A directed graph is said to be strongly connected if each vertex is accessible from any other: for any pair of distinct vertices there is a path between them.

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.