Maths - Graph Theory

graph

A graph G=(N,U) consists of:

  • A finite set N={n1,n2,...} of nodes.
  • A subset U of the Cartesian product N×N, the elements of which are called arcs.

The diagram shows the nodes represented by circles, and arcs (ni,nj) are shown by an arrow drawn from the point representing ni to the point representing nj.

The subset of arcs is shown in the following table.

  to node
n1 n2 n3 n4 n5 n6
from node n1   true   true    
n2 true          
n3 true         true
n4     true   true  
n5   true   true    
n6     true      

A more efficient way to encode the graph is as follows:

Where the pairs of names are the names of the start and end nodes.

Types of Graph

There are many variations, a few examples are:

Relationship to other Mathematical Structures

cayley graph

We can use graphs to represent other mathematical structures. For example Groups can be represented by a 'Cayley graph'. This is a graph, with specific rules, where the arcs have a 'colour' property

We could extend this to represent other mathematical structures which have sets+structure.

However graphs, in there most general form, are not necessarily equivalent to an algebraic structure with operations that apply to the whole set (closed operations/functions) in fact graphs can represent partial functions (see also denotational semantics).

Although graphs are not initial algebras it may be possible to use a slightly different structure which is an initial algebra as described on this page.

Graphs are also related to category theory. Category theory diagrams are graphs where:

For a discussion about using and representing graphs in category theory see this page.

Initial and terminal end-points of an arc.

For an arc (ni,nj), the node ni is the initial end-point and the node nj is the terminal end-point.

Adjacent nodes

adjacent nodes Two nodes are adjacent if they are joined by an arc.

adjacent arcs.

adjacent arcs Two arcs are adjacent if they have at least one common end-point.

Successors of a node.

successors of node A node ni is called a successor of a node x if (ni,nj) U; the set of all successors of x, is denoted by +(ni). In the example, the successors of n1 are (n2,n4), the other successors are:
ni +(ni)
n1 (n2,n4)
n2 (n1)
n3 (n1,n6)
n4 (n3,n5)
n5 (n2,n4)
n6 (n3)

Predecessors of a node.

predecessors of node A node nj is called a predecessor of ni if (nj,ni) U, and the set of all predecessors of n is denoted by -(ni). For example the predecessors of n1 are (n2,n3), the other predecessors are:
ni -(ni)
n1 (n2,n3)
n2 (n1,n1)
n3 (n4,n6)
n4 (n1,n5)
n5 (n4)
n6 (n3)

Arcs incident to and from a node.

If an arc u has node ni, as its initial end-point, we say that the arc is incident from ni, whereas if an arc u has node ni as its terminal end-point we say that arc u is incident to ni. The number of arcs incident from a node ni is called the out-degree of ni and it is denoted by p+(ni); while the number of arcs incident to ni is called in-degree of x and is denoted by p-(ni).

From the example:
ni p+(ni) p-(ni)
n1 2 2
n2 1 2
n3 2 2
n4 2 2
n5 2 1
n6 1 1

Partial graphs.

If we remove from a graph G (N,U) a subset of its arcs, we are left with a graph of the form:

H = (N,V), where V U

which is called a partial graph of G.

Combining Whole Graphs

So far, we have treated the graph as the whole structure and the nodes and arcs as elements. Here we treat whole graphs as fixed and indivisible and instead apply operations and functions to whole graphs.

Functions Between Graphs

In some cases, perhaps when the graph represents preordered sets, we can define functions between the graphs.

A function between preordered sets is:

  • monotone if xy implies f(x)f(y).
  • antitone if xy implies f(y)f(x).
function between preordered sets

More about morpisms between graphs on page here.

Sum, Product and Exponent of Graphs

There are many operations that we can apply to graphs including:

  Nodes Arcs

 

Sum
disjoint union

 

The nodes are added in the same way as sum (disjoint union) of sets.
graph sum

Arcs are just moved with the corresponding nodes.

Product
Cartesian

We can take the
Cartesian product
of two domains
A and B.

graph product

cartesion graph
If:

  • a1a2 and
  • b1b2 then:
  • <a1,b1><a2,b2>

Product
tensor

tensor graph
If:

  • a1a2 and
  • b1b2 then:
  • <a1,b1><a2,b2>
Exponent
(function)
 

For f,g∈Hom(A,B)

fg if f(x)g(x) for all x∈A

exponent

So to summarise, in both the Cartesian and tensor cases the nodes are the Cartesian product, but the arcs are defined as follows:

Cartesian Product

<u,v> <u',v'> exists:
if u=u' and v adj v'
or v=v' and u adj u'

cartesian product A⊕B = A⊗IB + IA⊗B

Tensor Product

<u,v> <u',v'> exists:
if u adj u' and v adj v'

tensor product A⊗B

Properties

The tensor product is bilinear and associative.

Equivalence Between Graph Products and Kronecker Sum/Product

  Graphs Matrix
Cartesian Cartesian product Kronecker sum
Tensor tensor product Kronecker product

Cartesian and tensor products not only occur in graphs but also occur in other algebras. In matrix algebra they are known as the Kronecker sum and Kronecker product. This use of the term 'sum' for a product is a bit confusing although it makes some sense in this graphical context since: the nodes are the product nodes but the arcs are in some sense a sum of the component nodes.

For more information see pages about Kronecker sum and Kronecker product.

So an alternative way to calculate a Cartesian or tensor product of two graphs is, to convert the graphs into adjacency matrices(defined below), then take the Kronecker sum or product, then convert back to a graph.

Although the example of an adjacency matrix below has only elements of 0 or 1, if we allow multiple arcs between nodes then, any natural numbers would make sense in this context. It would be hard to interpret adjacency matrix, which had elements that were negative or real numbers, as a graph.

Subgraphs.

If we remove from a graph G = (X,U) a subset nodes, together with all the arcs incident to or from nodes, we are left with a graph of the form:

where:

which is called a subgraph of G. We may describe H, as the subgraph of G generated by Y.

Cliques

A clique is a subset of the nodes of a graph such that there is an edge between every two nodes in the subset.

Cograph

A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.

Matrix Representations

In addition to outputting to a diagram we can also output other information about the graph in matrix form:

Incidence Matrix

The incidence matrix represents the graph by a matrix of size |V| by |E| see this wiki page
where:

Graph Incidence Matrix
example
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0

Adjacency Matrix

The adjacency matrix is an n by n matrix A, where n is the number of vertices in the graph. If there is an arrow from a vertex x to a vertex y, then the element ax,y is 1 (or in general the number of xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph. see this wiki page

Graph Adjacency Matrix
example
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0

Laplacian Matrix

The laplacian matrix also known as "Kirchhoff matrix" or "Admittance matrix" where:

entry [i,j] =

Alternatively this is defined as D − A, where D is the diagonal degree matrix. It contains both adjacency information and degree information. There are other, similar matrices, that are also called "Laplacian matrices" of a graph. see this wiki page

Graph Laplacian Matrix
example
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 -1 1 0 0 0 0 0
-1 0 0 0 1 0 0 0 0
0 -1 0 0 0 1 0 0 0
0 0 0 0 0 -1 1 0 0
0 0 0 -1 0 0 0 1 0
0 0 0 0 -1 0 0 0 1

Distance Matrix

Distance matrices are related to adjacency matrices, with the differences that:

see this wiki page

Graph Distance Matrix
example
0 0 0 -1 -1 -1 -1 -1 -1
0 0 0 -1 -1 -1 -1 -1 -1
0 0 0 -1 -1 -1 -1 -1 -1
0 0 1 0 -1 -1 -1 -1 -1
1 0 0 -1 0 -1 -1 -1 -1
0 1 0 -1 -1 0 -1 -1 -1
0 2 0 -1 -1 -1 0 -1 -1
0 0 2 -1 -1 -1 -1 0 -1
2 0 0 -1 -1 -1 -1 -1 0

Other Information about Graph

We now have a graph and we can check out various things about it. We can get information about the whole graph as follows. (10) tells us the graph is acyclic, that is it has no loops (which we can check by looking at the diagram above). (11) tells us that the graph is not functional, that is not every node has a single outgoing arrow. This is what we would expect since an acyclic graph cannot be functional.

(10) -> isAcyclic?(hs3)
   (10)  true
                                                          Type: Boolean
(11) -> isFunctional?(hs3)
   (11)  false
                                                          Type: Boolean

Connected Graphs

If a graph is 'unconnected' then it is not possible to get to parts of the graph from other parts. unconnected graph
The graph on the right is connected, but only 'weakly connected' because we can only travel between some parts of the graph in one direction. connected graph
The graph on the right is 'strongly connected' because we can travel between any two nodes in either direction. connected graph
Some graphs are weakly connected but might have islands that are strongly connected. connected graph

Condensations.

Let P= (n1,n2,...,nJ) be a partition of the node-set of a graph G=(X,U). Then the condensation of G induced by P is the graph Gp= (P,Up) where:

Up={(Xr,Xs)∈P×P|Xr ≠ Xs /\ (there existsxi∈Xr,xj∈Xs | (xi ,xj )∈U)}

In pictorial terms, Gp is obtained from U by coalescing the nodes of each member of P, and then removing any loops.


metadata block
see also:
  • For a discussion about using and representing graphs in category theory see this page.
  • There is a program which can represent and do calculations on graph theory on this page.
  • For more information see pages about matrix equivalents see Kronecker sum and Kronecker product.
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.