Graph theory

Problem about graph theory:


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

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

graph1

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

graph2

Terminology:

  • Order of a graph is equal to |S|.
  • 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:
    • graph3
  • In a digraph, we differentiate successors (end vertex) et predecessors (start vertex) :
    • graph4

 

Degree:

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

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.

graph8

Path

A path from u to v is a sequence <s0, s1, … , sk> such as u = s0 et v = sk, and (si, 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 s0 = sk. The circuit is called elementary if the path <s0, …, s(k-1)> is elementary.
A graph is connected if it exists a path between any couple of vertices.

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

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.

Problem: hamiltonian graph

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

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.

 

Publicités