## 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 (s_{i}, s_{j}) in 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.

_{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.

Terminology:

**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 e
**lementary**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).

Let us consider the graph G = (V, E,w) seen previously, and the weight function:

Adjacency:

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

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

## 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[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.

## Path

**u**to

**v**is a sequence <s

_{0}, s

_{1}, … , s

_{k}> such as u = s

_{0}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 ».

_{0}= s

_{k}. The circuit is called elementary if the path <s

_{0}, …, s

_{(k-1)}> is elementary. A graph without cycles is called acyclic.

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:

**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.