Monday, June 29, 2015


In an undirected graph, how can I efficiently keep track of how many connected parts it has. I'd like to list the nodes such that all nodes of a connected part are together. In other words, if the graph has more than one connected part, I can divide the list between two consecutive nodes, such that no connected part of the graph has nodes in both lists. Consider a list of the nodes, and connect the entries of the list by edges from the graph. Some edges connect consecutive nodes, and some edges hop over nodes in the list. If, as edges from the graph are added to the list, the list is reordered such that the number of hops is minimized, then after all edges have been added, connected parts of the graph will be together in the list. Suppose nodes of a graph are listed in some order, and the graph has two connected parts. Consider a sublist of just the nodes from one connected part in the same order as the entire list. Count the hops in the sublist. Similarly count the hops in the sublist of the nodes in the other connected part. If the sublists are dividable in the entire list, one entirely before the other, then the number of hops in the entire list is just the sum of the hops in the sublists. If the sublists are not dividable, then the number of hops is greater than the sum. Therefore, if the number of hops in the list is minimum, connected parts of the graph are dividable between two consecutive nodes in the list. Suppose I add edges to a list one at a time. I claim I can reorder the list so that the number of hops stays minimal. Suppose a list, L, with some edges has minimal hops, and I have an edge to add. Transpose the ends of the edge with consecutive nodes to shorten the new edge, so long as the number of hops is reduced. I claim the result has the minimum number of hops. Suppose the contrary, that there is a list with fewer hops. Consider that list with the new edge removed. That list has fewer hops than L. This contradiction proves my claim.

No comments: