What The Heck Is Graph Theory

Introduction to Bazonkas (easy)

The Graph Zoo

1. The null graph -no vertices, no edges.
2. Multigraphs permit more than one edge between a given pair of vertices. So a graph might Contain vertices {A,B,C} and have edges {(A,B),(A,B),(B,C)}. We don't meet multigraphs in the Lerch Grossman Algorithm. However it illustrates a point about sets. Since in this diagram there are two edges between A and B the pair (A,B) occurs twice. However, the nature of sets is that something is either a member or it isn't. The way that we have written it we have (A,B) being a member twice. We can expect a visit from the Math Police. The get out is to call it a "collection" of edges rather than a "set".
3. Directed graphs are connected by directed edges. In the Lerch Grossman paper directed edges are called arcs. A directed edge has a sense of direction to it. We draw them with little arrows on. We write the set of edges as an ordered pair. In a regular graph the edge (A,B) is the same as the edge. For mathematicians directed graphs are usually viewed as a special case -they are simple graphs with (if you like) arrows added. For the programmer directed graphs are easier to deal with and you expend effort ensuring that your program knows that an edge (A,B) is the same as one (B,A). Directed graphs are often called 'digraphs' for those wishing to seam familiar.
4. Connected graphs are graphs in which there is a chain (a sequence of edges (A,B)(B,C)(C,D))... ) joining every pair of vertices. LG use the term 'path' on a directed graph for the same concept but using directed edges. (Watch for other terms from other authors e.g. edge sequences). The issue of connectedness is a little more complicated with digraphs but we don't need it here.
5. Cyclic vs acyclic graphs. If there are loops in a graph its called cyclic if not its acyclic. Formally a loop is a chain with the same first and last vertex.
6. Trees a connected acyclic graph is called a tree. If you pick a vertex (at random) in a tree and call it the "root" then you have a "rooted tree". L and G go on to define branches and twigs (yawn). They mean what you'd think, more or less. Rooted trees have two important properties. Even though we are in theory talking about an non-directed graph, every edge now has a special direction which is the direction of the root. In other words you can if you want think of rooted trees as directed graphs. As programmers we say "yes please" to this. The second point, which turns out to be important in the LG algorithm is this. Every vertex, except the root has exactly one edge on the root side. It may have any number (including zero) on the 'leaf' side. So if we have a rooted tree we may be able to represent it as a data structure in which each record has exactly one pointer pointing in the root direction. This turns out to be the case in the LG algorithm -and is a good thing. You read it here first folks!
7. The list goes on. With only the above properties we can ask a large number of intriguing questions of a graph. For example, going back to Euler in 1763, we can ask whether it is possible to find a circuit that will use all the edges exactly once (an euler circuit). Often, however, we need to add to the basic graph concept. Vertices represent values or edges represent distances. Numbers and sometimes colours are added. The menagerie of graph types and properties is extensive.

Some Diagrams

Multigraphs

Directed Graph

Graph that is not connected

Rooted Tree

Transitive closure

Partial Graphs and Subgraphs

1. Suppose that graph B contains some of the vertices of graph a but all of the edges from A that connect those vertices. Here B is called a subgraph. If A consisted of vertices which represented the towns of Canada and edges that represented connecting roads then an example of a subgraph would cover e.g. the cities and roads of Manitoba -some of the towns but all of the roads connecting them.
2. On the other hand if we keep all of the vertices (often only nominally) but only some of the edges, then the result is called a partial graph. Extending our previous example, a partial graph might represent all the towns of Canada but only roads which are four lanes or more.

Closures of a Graph and Maximum Closure of a Weighted Graph

1. A directed graph is shown in red.
2. The four vertices in the yellow bubbles are a closure.
3. They are the maximum closure and have the value 2+3-1-1=3. Convince yourself that this is so. i.e. that there is no other closure with a greater value
4. Working out the maximum closure of even a simple graph is not trivial

The Pit Optimisation Context

Last Thoughts About graph theory

1. As we see above it is important to have a system for describing graphs and their properties.
2. As mathematicians are wont to do, they prove things about graphs. So for example there is a simple way to determine whether a graph has an Euler circuit, and this was proven by Euler.
3. Lastly (and this is where we get interested) they work on algorithms to solve problems that involve graphs.

Graphs and Computer Programming

1. Dynamic vs Static Storage. Are you going to use static arrays, dynamic data structures (linked or doubly linked records) or a more modern type of container, such as those provided by C++'s standard template library.
2. How the edges are represented. Options include true pointers, iterators (pointers on drugs), integers that represent the index of vertex in an array or array like structure, names (substrings) that can then be used to lookup the storage position of the indicated vertex, and using 2d arrays as adjacency matrices.
3. Maintaining the structure.For example, if we are not dealing with a directed graph we if A is adjacent to B than B is adjacent to A.
4. Additional data: Depending on the method additional information may be stored abour individual vertices or edges. The might be flagged e.g as belonging to a particular sub set, they may have temporary or permanent values applied to them etc..

Graph Algorithms

Complexity

Representing Graphs in The computer

1. Size: is it important how much memory is required? In particular some matrix methods tend to require space that is proportional to the square of the number vertices. This is no problem for say 100 vertices but for a million it becomes impractical.
2. The ability to visit each vertex (or edge) once. Algorithms tend to have steps that say things like "find a vertex with property P -if one exists". If the vertex data is embedded in a linear structure such as a list or an array this is easy.
3. Examining for structural features makes different demands on an implementation. For example determining whether a graph is connected or cyclic, or counting the vertices on a branch each have their own requirements.
4. Creating and destroying the structures. Particularly in the case of the more complex data structures, you must give some thought

1. Adjacency matrices. If there are n vertices in a graph an adjacency matrix is an n x n matrix containing 1's where vertices are connected by edges (i.e. are adjacent), and 0 otherwise. So the first graph above (the yellow and black one) would be written as:

   
         A B C D
      A  0 1 1 0
      B  1 0 1 1
      C  1 1 0 1
      D  0 1 1 0
       

   A two dimensional array (e.g. of booleans) would clearly work. Notice that the space required increases with the square of the number of vertices. This may not be a problem is the problem sizes are moderate or if a large percentage of the vertices are connected by and edge
2. Adjacency lists. Here for each vertex a list is made of each adjacent vertex. The yellow graph could be written:

       A:BC
       B:ACD
       C:ABD
       D:BC
   

   This is not quite so simple as we have a list or array of items which have variable length. However it is a good fit with the storage classes available through C++'s standard template library for example.
3. Data Structures. The most general way to represent graphs is probably through data structures. Records that represent vertices and have a variable number (linked list?) of pointers to other such records.
   
   This diagram is supposed to indicate a doubly linked structure. As vertex A is linked by an edge to B, so there is a pointer in A pointing at B and a pointer in B pointing at A. The red line is supposed to represent a pointer locating the structure from the programs point of view. If the graph is not known to be connected you need to arrange multiple such pointers -perhaps a dummy vertex- pointing at least once at each component. It is worth considering that disposing of the memory in a structure such as this is not trivial.
4. Problem specific methods. IN the LG implementation that I present here our vertices represent blocks of rock which are arranged in a three dimensionally so that the arrangement suggest storing all the data in three dimensional arrays. One of the data structures is a tree. Because it is a tree and because it is possible to work always in a rootwards direction you can get away with a three dimensional array of "pointers" to each blocks rootward neighbour. In fact true pointers are less convenient than remembering the index of the adjacent block in the array.
5. Rule based representations. On occassion it is possible not to have to represent the edges of the graph at all because they have a regularity that can be described by rules. Suppose

Recursion and Transitive closure

  Function Boolean IsAnAncestorOf(A,B)
    {
     if(IsAParentOf(A,B))return true;
     
     for each C such that IsAParent(A,C)  if IsAnAncestor(C,B) return true;

     return false;
    }