Graph Theory 101

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 (si, sj) in S².

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

graph theory

In an undirected graph, the pairs (si, sj) are not oriented. Thus, (si, sj) is equivalent to writing (sj, si). Graphically, this couple is a fish bone between vertices si and sj.

graph

Elements of terminology:

  • THE'order of a graph is the number of its vertices | S |.
  • A loop is an arc or an edge (si, si).
  • 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 (si, sj) for any pair of vertices (or two arcs (si, sj) and (sj, si)). A complete simple graph with n vertices will have n (n-1) / 2 edges.
  • a attribute can be associated with (si, sj). 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:

graph

Notions of adjacency:

  • In an undirected graph, a vertex si is said adjacent at a summit sj if there is an edge between si and sj. The set of vertices adjacent to a vertex si is defined by:

adjacency graph

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

successor predecessor graph

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:

degree graph

  • 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:

outgoing degree graph

  • 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:

incoming degree graph

  • 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 [si] contains all the elementsj of S such that there is a link (si, sj) in TO. That is, the list of successors of si. 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.

graph

Pathways

In a directed graph, a path from a vertex u towards a summit v is a sequence <s0, s1,…, Sk> vertices such that u = s0 and v = sk, and (si, 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 s0 = sk and if the path has at least one arc. This circuit is elementary if the path <s0,…, 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.