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.
• We can associate WEIGHTS on edges. These weights represent cast, profit, length, capacity, action, etc. of a given connection. The weight is a mapping from the set of edges to a set of numbers or alphabet w : E → R or Σ. The graph with weight function of numbers is called a NETWORK and denoted by G = (V, E,w).

• 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:
  • 
• The number of vertices of odd degree is even. The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.

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. u is denoted « start » and v « end ».

A circuit/cycle 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 without cycles is called acyclic.

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.

Assume G is Eulerian ⇐⇒ there exists a circuit that includes every edge of G. Every time a circuit enters a node v on an edge, it leaves on a different edge. Since the circuit never repeats an edge, the number of edges incident with v is even ⇒ deg(v ) 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.

Ore 1960. A graph with n vertices (n ≥ 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater.

Posa 1962. A graph with n vertices (n ≥ 3) is Hamiltonian if, for any k, 0<k<(n-1)/2 the number of vertices which degree is inferior or equal to k is inferior or equal to k. The number of vertices which degree is inferior or equal to (n-1)/2 is inferior or equal to (n-1)/2.