Cost in a Graph

Cost in a Graph

The cost in a graph represents the total length of the network measured in real transport distances where aij is the presence (1) or absence (0) of a link between i and j and lij is the length of the link. This measure can also be calculated based on two other dimensions of the network: the Minimum Spanning Tree (MST) and the Greedy Triangulation (GT). The MST represents the shortest and/or lowest cost subtree of the network; it can be obtained by applying, among other shortest path algorithms, the Kruskal algorithm, which allows finding the lowest cost route connecting all nodes in the network. The GT refers to the maximally connected planar graph keeping the same number of nodes as in the original network but adding all possible links without breaking its planarity. Such operations consider both the topology and the geography of the network while comparing the latter with its optimal configurations. More efficient networks have relative costs near 1, while less efficient networks are closer to 0.

The Kruskal algorithm extracts the optimal cost route (B) from the original network (A). It is defined by one single line joining all nodes at minimum cost (Minimum Spanning Tree). The Greedy Triangulation (GT) adds missing links between all nodes so as to make it complete (maximal) without breaking its planarity (C). Values of 10 at each newly created link were attributed artificially due to the absence of distance units, but would, in reality, be less evenly distributed. In its current form, the network (A) is more efficient in terms of weight (CostRel = 0.642) than in terms of links (CostRel = 0.389) with reference to the optimal situations B and C.