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
Basics about graph theory can be found in the following lecture: Graph theory
Basics
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 (si, sj) in S².
Terminology:
- Order of a graph is equal to |S|.
- A loop is an arc or edge (si, si).
- 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.
Adjacency:
- In an undirected graph, a vertex si is adjacent to a vertex sj if there is an edge between si and sj. The set of adjacent vertices for si is defined by:
- In a digraph, we differentiate successors (end vertex) et predecessors (start vertex) :
Degree:
- 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:
Computer Representation
There are two way to implement a graph in computer sciences: by adjacent matrix or by adjacent list.
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[si] have all the sj of S such as (si, sj) exists in A. This encoding take O(|S|+|A|) memory.
Path
This is done by transitive closure. We compute the n first adjacent matrix powers, n=|A|. The graph is connected if all the matrix have value.
Problem: eulerian graph
Problem: hamiltonian graph
This is no necessary and sufficient condition for this problem but only some sufficient conditions as follows: