Problem about graph theory:

• Tree
• Spanning tree or in PDF
• Coloring, Clique and independent set or in PDF
• Pathfinding
• see formal language
• see stochastic problem

A graph G is defined by a couple (S,A) such as S is a defined set of vertices, and A is a defined set of vertices’ couple (s_i, s_j) in S².

In a directed graph, each couple (s_i,s_j) in A are directed, which means that s_i is the start vertex and s_j the end vertex. A directed couple is called an arc.

In a undirected graph, each couple (s_i,s_j) are not directed e.a. (s_i,s_j) and (s_j,s_i) is the same couple. An undirected couple is called an edge.

• Order of a graph is equal to |S|.
• A loop is an arc or edge (s_i, s_i).
• An undirected graph is called simple if there is no loop and at most one edge for a couple.  Otherwise it is a multi-graph.
• A digraph is called elementary if there is no loop.
• A digraph is called p-graph if there is at most p arcs for any couple.
• A part of a graph is done when some arcs/edges are removed.
• A subgraph have a subset of vertices and a subset of couple (depending of the original set of vertices and set of couple).
• A complete graph have all the arcs/edges between every pair of vertices. The number of edges is equal to the sum from 1 to n = n(n-1)/2.

• In an undirected graph, a vertex s_i is adjacent to a vertex s_j if there is an edge between s_i and s_j. The set of adjacent vertices for s_i is defined by:
  • 
• In a digraph, we differentiate successors (end vertex) et predecessors (start vertex) :
  • 

• In an undirected graph, the degree of a vertex is defined by:
  • 
• In a digraph, the external degree of a vertex is defined by:
  • 
• In a digraph, the internal degree of a vertex is defined by:
  • 

Vertices are named from 1 to n. An adjacent matric M with size n*n is a matrix such as M[i,j] = value if (i,j) is in A, M[i,j] = no value otherwise. When arcs/edges have no value, then value = 1 et no value = 0. When arcs/edges have a value, value = valueet no value = infinity. For an undirected graph, the matrix have a diagonal symmetry. This encoding take O(|S|²) memory.

The adjacent list is a table T of n sets, one for each vertex of S. The chained list T[s_i] have all the s_j of S such as (s_i, s_j) exists in A. This encoding take O(|S|+|A|) memory.

A path from u to v is a sequence <s₀, s₁, … , s_k> such as u = s₀ et v = s_k, and (s_i, s_(i+1)) exists in A for i from 0 to k-1. The length of a path is the number of step from u to v, e.a. k. If there is a path from u to v, then v is reachable from u. An elementary path do not have loop.

A circuit have the start equals to the end s₀ = s_k. The circuit is called elementary if the path <s₀, …, s_(k-1)> is elementary.

A graph is connected if it exists a path between any couple of vertices.

An eulerian path (or circuit) go through all arcs/edges one and only one time.

Necessary condition: the graph is connected. For any vertex, its degree is even.

Necessary and sufficient condition: the graph is connected. For any vertex, without two of them, its degree is even.

An hamiltonian path or circuit go through all vertices one and only one time.

Dirac 1952. A graph with n vertices (n>2) where each vertex have at least a degree equals to n/2 is hamiltonian.