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

Gis directed graph : <=>existsV,E:G= <V,E> /\EsubsetVxV.

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>}

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

can be depicted as`E`= {<__a__,__a__>, <__a__,__b__>}

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) :=letV=G_{0},E=G_{1}:suchMinVxV-> {true,false}:( forallxinV,yinV:M(x,y) =true<=> <x,y> inE).

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

For the corresponding adjacency matrix, we thus have

RoS= {<a,c>:ainN_{n}/\cinN_{n}/\ (existsb: <a,b> inR/\ <b,c> inS)}.

Written as a Java method, the composition of two adjacency matrices

foralliinN_{n},jinN_{n}:adjacency(< N_{n},RoS>)_{i, j}=true<=>existskinN_{n}:A_{i, k}=true/\B_{k, j}=truewhereA= adjacency(<N_{n},R>),B= adjacency(<N_{n},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.

Gis undirected graph : <=>existsV,E:G= <V,E>,EsubsetVxV,Eis symmetric onV.

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

can be depicted as follows:`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>}

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

can be depicted as__E__= {<__a__,__a__>, <__a__,__b__>, <__b__,__a__>}

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.

The

indeg _{G}(x) := |{yinV: <y,x> inE}|whereV=G_{0},E=G_{1}.

The

outdeg _{G}(x) := |{yinV: <x,y> inE}|whereV=G_{0},E=G_{1}.

deg _{G}(x) := indeg_{G}(x) + outdeg_{G}(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.

GandG' are isomorphic : <=>Gis directed graph /\G' is directed graph /\existsf:f:V->^{iso(E, E')}V'whereV=G_{0},E=G_{1},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.

The

pis path inG: <=>( existsninN_{>0}:p:N_{n}->V/\foralliinN_{n-1}: <p_{i},p_{i+1}> inE)whereV=G_{0},E=G_{1}.

A path

length( p) :=suchninN:p:N_{n+1}->V.

A path is

pis path fromxtoy: <=>p_{0}=x/\p_{n}=ywheren= length(p).

A path is

pis simple : <=>foralliinN_{n},jinN_{n}: <p_{i},p_{i+1}> = <p_{j},p_{j+1}> =>i=jwheren= length(p).

A path is a

pis elementary : <=>foralliinN_{n},jinN_{n}:p_{i}=p_{j}=>i=jwheren= length(p).

pis cycle : <=>existsx:pis path fromxtox.

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

yis reachable fromxinG: <=>existsp:pis path inG/\pis path fromxtoy.

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.

The

reflexive _{S}(R) :=suchR' subsetSxS:RsubsetR' /\R' is reflexive onS/\forallR": (RsubsetR" /\R" is reflexive onS) =>R' subsetR".

transitive _{S}(R) :=suchR' subsetSxS:RsubsetR' /\R' is transitive onS/\forallR": (RsubsetR" /\R" is transitive onS) =>R' subsetR".

We then can derive the following result.

Then, for any directed graph <

R_{G}:= {<x,y> inG_{0}xG_{0}:yis reachable fromxinG}.

forallV,E: <V,E> is directed graph =>R_{<V, E>}= reflexive_{V}(transitive)._{V}(E)

which can be depicted as:

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

Since <0, 1> in

In addition, every node is reachable from itself:

transitive _{N5}(E) ={<0, 1>, <0, 2>, <0, 3>, <0, 4>, <1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>}.

reflexive _{N5}(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.

forallS,R:RsubsetSxS=>reflexive _{S}(R) =Runion (SxS).

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

R^{0}_{S}:= {<x,x>:xinS}R^{i+1}_{S}:=R^{i}_{S}oR.

`R`_{S}^{0} is the identity relation and
`R`_{S}^{1} is `R`. Consequently, e.g.

R_{S}^{3}=RoRoR.

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

forallS,R:RsubsetSxS=>transitive _{S}(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

that starts with

[ R,Runion (RoR),Runion (RoR) union (RoRoR), ...]

forallS,R:RsubsetSxS=>transitive _{S}(R) =union_1 <=i<=nR^{i}_{S}wheren= |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|R^{0}= {<x,x>:xinV}for(i=0;i<n;i++)R^{i+1}=R^{i}union (R^{i}oE)returnR^{n}

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.

Tis tree : <=>Tis directed graph /\existsrinV: indeg(r) = 0 /\forallxinV-{r}:indeg( x) = 1 /\xis reachable fromrinTwhereV=T_{0}.

root( T) := (suchrinV: indeg(r) = 0)whereV=T_{0}.

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

- The following diagrams depict trees with root
`r`: - The following directed graphs are
*not*trees: - The term -
`b`+2`a`is represented by the following tree: - A file system with directories
`/`

,`/bin`

,`/etc`

,`/usr`

,`/usr/bin`

,`/usr/bin/X11`

,`/usr/etc`

We state without proof the following important property of trees.

forallT:Tis tree =>~( existsp:pis path inT/\ length(p) > 0 /\pis cycle).

The following notions describe relations among tree nodes.

yis child ofxinT: <=>< x,y> inEwhereE=T_{1}.

A node

parent _{T}(y) :=suchxinV: <x,y> inEwhereV=T_{0},E=T_{1}.

A node

xis leaf inT: <=>xinV/\ ~existsy:yis child ofxinTwhereV=T_{0}.

xis ancestor ofyinT: <=>existsp:pis path inT/\pis path fromxtoy.

yis descendant ofxinT: <=>xis ancestor ofyinT.

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.

node

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

forallT:Tis tree =>forallxinV:existsp:pis path inT/\pis path fromrtox/\forallp': (p' is path inT/\p' is path fromrtox) =>p' =pwhereV=T_{0},r= root(T).

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

The

level _{T}(x) := length(p)wherep=suchp:pis path inT/\pis path from root(T) tox.

height( T) := max {level_{T}(x):xinV}whereV=T_{0}.

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.

forallT: (Tis tree /\forallxinV: outdeg(x) <= 2) => |V| < 2^{h+1}whereV=T_{0},h= height(T).

- Assume the height is
`h`= 0. Then |`V`| = 1 < 2 = 2^{h+1}. - 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+(2^{h}-1)+(2^{h}-1) = 2^{h+1}-1 < 2^{h+1}.

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

Author: Wolfgang Schreiner

Last Modification: October 4, 1999