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

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:

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

_{0}= s

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

_{0}, …, s

_{(k-1)}> is elementary.

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.