Go backward to 7.2 Order Relations Go up to 7 More on Relations

7.3 Graphs

G is directed graph : <=>

exists V, E:

G = <V, E> /\

E subset V x V.

An element <x, y> in E expresses the fact that node x is connected to node y where x is called the  initial node of the corresponding edge and y is called its  terminal node. Both nodes are then  adjazent.

Please note that in above definition of a graph there may be at most one edge between any pair of nodes. A graph with potentially more than one edge between two nodes is called a  multigraph (Multigraph) which may be used to describes e.g. multiple roads between two cities. Furthermore, the edges in a graph may be labelled with real values; such a graph is called a  weighted graph (gewichteter Graph) and may describe lengths of roads or capacities of water pipes. However, we will not consider the formalization of such graphs in this document.

• The graph <N_5, E> with

  E = {<0, 1>, <0, 2>, <1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 0>, <4, 1>}

  can be depicted as

  

  or as

  

  i.e., the visual representation of a graph is not unique; vice versa, different visual objects may describe the same graph.

  A representation of this graph by a boolean matrix (every edge is denoted by a matrix entry true) is the following:

  	0	1	2	3	4
  0	false	true	true	false	false
  1	false	true	true	false	false
  2	false	true	false	false	false
  3	false	false	false	true	false
  4	true	true	false	false	false

• The graph <{a, b, c}, E> with

  E = {<a, a>, <a, b>}

  can be depicted as

  

  and is represented by the following matrix:

  	a	b	c
  a	true	true	false
  b	false	false	false
  c	false	false	false

The matrix representation of a graph used in above example can be formalized as follows.

adjacency(G) :=

let V = G0, E = G1:

such M in V x V -> {true, false}:

(forall x in V, y in V: M(x, y) = true <=> <x, y> in E).

The adjacency matrix is the typical implementation of a graph in a computer; most graph algorithms operate with this representation.

R o S = {<a, c>: a in Nn /\  c in Nn /\  (exists b: <a, b> in R /\  <b, c> in S)}.

forall i in Nn, j in Nn:

adjacency(<Nn, R o S>)i, j = true <=>

exists k in Nn: Ai, k = true /\  Bk, j = true

where A = adjacency(<Nn, R>), B = adjacency(<Nn, S>).

void compose(int n, boolean[][] A, boolean[][] B, boolean[][] C)
{
  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
      C[i][j] = false;
      for (int k=0; k<n; k++)
        C[i][j] = C[i][j] || (A[i][k] && B[k][j]);
    }
  return C;
}

In some graphs, the direction of the edges does not matter.

G is undirected graph : <=>

exists V, E:

G = <V, E>,

E subset V x V,

E is symmetric on V.

According to this definition, an undirected graph is a special directed graph; therefore all the following definitions and results for directed graphs apply to undirected graphs as well. Because of symmetry, the only information carried by an undirected graph is whether two nodes x and y are connected or not; in the visual representation it suffices to draw a single undirected edge between two connected nodes.

• The graph <N_5, E> with

  E = {<0, 1>, <1, 0>, <0, 2>, <2, 0>, <1, 1>, <1, 2>,

  <2, 1>, <3, 3>, <0, 4>, <4, 0>, <1, 4>, <4, 1>}

  can be depicted as follows:

  

  We just need to fill the elements of the upper right triangle of the matrix representation; the other elements are determined by symmetricity:

  	0	1	2	3	4
  0	false	true	true	false	true
  1		true	true	false	true
  2			false	false	false
  3				true	false
  4					false

• The graph <{a, b, c}, E> with

  E = {<a, a>, <a, b>, <b, a>}

  can be depicted as

  

  and has the following matrix representation:

  	a	b	c
  a	true	true	false
  b		false	false
  c			false

An important notion is the number of edges that enter or leave a node.

indegG(x) := |{y in V: <y, x> in E}|

where V=G0, E=G1.

outdegG(x) := |{y in V: <x, y> in E}|

where V=G0, E=G1.

degG(x) := indegG(x) + outdegG(x).

• In the graph

  

  the indegree of node 1 is 4 and its outdegree is 2.
• In the graph

  

  the indegree and the outdegree of node c are both 0.

Applied to undirected graphs, above definition makes the indegree of a node equal its outdegree and the total degree be even; since in undirected graphs the only interesting information is the total degree, this number is then usually divided by two in correspondence with the visual representation.

Even if two graphs are different, they may have the same structure.

G and G' are isomorphic : <=>

G is directed graph /\  G' is directed graph /\

exists f: f: V ->iso(E, E') V'

where V = G0, E = G1, V' = G'0, E' = G'1.

• The graphs

  

  are isomorphic with isomorphism

  f = {<0, b>, <1, c>, <2, d>, <3, a>}.

• The graphs

  

  are isomorphic with isomorphism

  f = {<0, 1>, <1, 2>, <2, 3>, <3, 0>}.

• The graphs

  

  are not isomorphic.

The edges of a node yield paths that can be used to wander among nodes.

p is path in G : <=>

(exists n in N>0: p: Nn -> V /\

forall i in Nn-1: <pi, pi+1> in E)

where V=G0, E=G1.

length(p) := such n in N: p: Nn+1 -> V.

p is path from x to y : <=>

p0 = x /\  pn = y

where n = length(p).

p is simple : <=>

forall i in Nn, j in Nn: <pi, pi+1> = <pj, pj+1> => i = j

where n = length(p).

p is elementary : <=>

forall i in Nn, j in Nn: pi = pj => i = j

where n = length(p).

p is cycle : <=> exists x: p is path from x to x.

Reachability  We will now investigate how to determine whether two nodes are directly or indirectly connected in a graph.

y is reachable from x in G : <=>

exists p: p is path in G /\  p is path from x to y.

The predicate "is reachable" is, for fixed graph G=<V, E>, a binary relation on V, as well as the edge relation E is. Actually we can derive from E the reachability relation by a general construction that we are going to elaborate.

reflexiveS(R) :=

such R' subset S x S:

R subset R' /\  R' is reflexive on S /\

forall R": (R subset R" /\  R" is reflexive on S) => R' subset R".

transitiveS(R) :=

such R' subset S x S:

R subset R' /\  R' is transitive on S /\

forall R": (R subset R" /\  R" is transitive on S) => R' subset R".

We then can derive the following result.

RG := {<x, y> in G0 x G0: y is reachable from x in G}.

forall V, E: <V, E> is directed graph =>

R<V, E> = reflexiveV(transitiveV(E)).

E = {<0, 1>, <1, 2>, <1, 3>, <2, 3>, <3, 4>}

transitiveN5(E) =

{<0, 1>, <0, 2>, <0, 3>, <0, 4>, <1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>}.

reflexiveN5(E) = {<0, 0>, <1, 1>, <2, 2>, <3, 3>, <4, 4>}.

Above definitions of closures are too inefficient for a practical algorithm that decides the reachability of a node; a direct construction of the reflexive closure is provided by the following result which is easy to establish.

forall S, R: R subset S x S =>

reflexiveS(R) = R union (S x S).

An efficient computation of the transitive closure is based on the following operation that composes a relation R an arbitrary number of times.

R0S := {<x, x>: x in S}

Ri+1S := RiS o R.

R_S⁰ is the identity relation and R_S¹ is R. Consequently, e.g.

RS3 = R o R o R.

The transitive closure is then characterized by the following result which we state without proof.

forall S, R: R subset S x S =>

transitiveS(R) = union {R</sup>iS: i in N>0}

In other words, the transitive closure of R is the union of all members of the sequence

[R, R union (R o R), R union (R o R) union (R o R o R), ...]

forall S, R: R subset S x S =>

transitiveS(R) = union_1 <= i <= n RiS

where n = |S|.

Since the reflexive and transitive closure of the edge relation describes the reachability relation, we thus have a constructive method of computing the reachability relation of a graph <V, E>; we start with the identity relation and add n times the transitive consequences of R:

reachability(V, E):

n = |V|

R0 = {<x, x>: x in V}

for (i=0; i < n; i++)

Ri+1 = Ri union (Ri o E)

return Rn

For an actual implementation, we usually turn to the representation of the graph as a n * n matrix M. Since in this representation the composition of two relations resembles matrix multiplication the computation of reachability is basically a sequence of matrix multiplications (see this example.

Trees  Trees are a special kind of graphs that are of particular relevance in computer science: they provide a way to represent hierarchical structures such as a family genealogy, an organizational chart, or a file system.

T is tree : <=>

T is directed graph /\

exists r in V: indeg(r) = 0 /\

forall x in V-{r}:

indeg(x) = 1 /\

x is reachable from r in T

where V = T0.

root(T) := (such r in V: indeg(r) = 0) where V = T0.

Trees are depicted with the root node at the top and all arcs directed downwards (such that arrowheads need not be given)⁵.

• The following diagrams depict trees with root r:

  

• The following directed graphs are not trees:

  

• The term -b+2a is represented by the following tree:

  

• A file system with directories

  /, /bin, /etc, /usr, /usr/bin, /usr/bin/X11, /usr/etc

  is represented by the following tree:

  

We state without proof the following important property of trees.

forall T: T is tree =>

~(exists p: p is path in T /\  length(p) > 0 /\  p is cycle).

The following notions describe relations among tree nodes.

y is child of x in T: <=>

<x, y> in E where E = T1.

parentT(y) := such x in V: <x, y> in E

where V = T0, E = T1.

x is leaf in T : <=> x in V /\  ~exists y: y is child of x in T

where V = T0.

x is ancestor of y in T : <=>

exists p: p is path in T /\  p is path from x to y.

y is descendant of x in T : <=> x is ancestor of y in T.

Please note that in a tree every node (apart from the root) has a parent and that this parent is unique. Every node is a descendant of the root; the only descendant of a leaf node is the node itself.

In a tree, all paths from the root are unique.

forall T: T is tree =>

forall x in V:

exists p: p is path in T /\  p is path from r to x /\

forall p': (p' is path in T /\  p' is path from r to x) => p' = p

where V = T0, r = root(T).

Because of this result, the following notions are uniquely defined.

levelT(x) := length(p)

where p = such p: p is path in T /\  p is path from root(T) to x.

height(T) := max {levelT(x): x in V} where V = T0.

The definition implies that the root node has level 0 and the level of a node is one plus the level of its parent.

We conclude this section by a result which relates the degrees of nodes to the heights of trees.

forall T: (T is tree /\  forall x in V: outdeg(x) <= 2) => |V| < 2h+1

where V = T0, h = height(T).

1. Assume the height is h = 0. Then |V| = 1 < 2 = 2^h+1.
2. Assume the height is h > 0. Consequently the root of T has a child that is the root of a tree of height h-1 and possibly a second child that is the root of a tree of height less than or equal h-1. By the induction hypothesis, we thus have

   |V| <= 1+(2h-1)+(2h-1) = 2h+1-1 < 2h+1.

It is easy to generalize above result to trees whose outdegrees are bounded by an arbutrary limit k (how?).