Block cut tree

One of the most important concepts in graph theory is the block cut tree of a graph. The block cut tree of a graph is determined by splitting up the components of a graph into two parts: the cut vertices whose removal disconnects the graph, and the blocks which are biconnected components that don't contain any cut vertices in their own graphs. The block cut tree determines the betweenness relations of the graph, and in particular it completely determines the total betweenness relations which are defined by the set of all points in paths between two points. To consider the block cut tree we will start with the example below.



One thing that is worth realizing about the block cut tree is that cut vertices are singular elements and all blocks have two or more elements in them. This suggests a way of representing the block cut tree as a set system, so I decided to represent it in this way. In order to get the block cut tree like this the function bcset can be used.

(= (bcset graph)
    #{#{0} #{1} #{2} #{3} #{7} #{8}
      #{0 4} #{7 3} #{6 2} #{1 5} #{7 8} 
      #{9 10 8} #{0 1 3 2}})

This produces a height two forest-comparability ordered set system in which cut vertices belong in the blocks associated with them. The block cut tree is merely the inclusion comparability of this set system, which as displayed below is a tree.



One characteristic of the block cut tree, is that every element is either a cut vertex or it is contained in some block. This relates the elements of the graph to the elements of the block cut tree. One interesting aspect of this set system representation is that the block or the cut of the point within the tree can be determined by getting the smallest set containing it. In other words, it can be computed by getting the intersection of the set of all sets that contained the point as a member. This is what the subdimembers function does with respect to the set system.

(= (subdimembers tree 2)
   #{2})
(= (subdimembers tree 10) 
   #{9 10 8})

This relates the members of the graph to the members of the block cut tree. The next thing to be computed is the path between two points in the block cut tree as determined by the sets corresponding to those points. This determines a path between any two points in the block cut tree of the graph. All points between two points can be determined by the union of the elements in this path set system.

(= (bcpath graph 0 9) 
   #{#{0} #{3} #{7} #{8} #{3 7} #{7 8} #{9 10 8} #{0 1 3 2}})
(= (bcinterval graph 0 9) 
   #{0 1 2 3 7 8 9 10})

This demonstrates how the problem of determining all points that are between any two points in the graph regardless of length can be determined by the block cut tree. As a tree is defined as a type of graph that has a unique path between any two points, all the paths between any two points have the same length, so the metric betweenness and the total betweeenness coincide. So well the total betweenness and the metric betweenness don't always coincide, they do coincide in the block cut tree which determines the total betweenness.