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

weightgraph

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
  • 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[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. u is denoted « start » and v « end ».
A circuit/cycle 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 without cycles is called acyclic.
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.
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.
eulerian2
eulerian3

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.
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.
Publicités