Assume that a graph G = (V, E) is represented using an array of length ∣V∣, where position n contains the adjacency list for the node with node index n (n ∈ {0,…,∣V∣-1}), and the adjacency lists contain node indices.
We need to check if a given graph is reflexive, symmetric, and transitive. Checking for reflexivity and symmetry is easy:
reflexive(G):
for n ∈ {0,…,number of nodes in G - 1} do
if n does not occur in its own adjacency list then
return false
return true
symmetric(G):
M ← adjacency matrix for G
for m ∈ {0,…,number of nodes in G - 1} do
for n ∈ {0,…,number of nodes in G - 1} do
if M[m,n] ≠ M[n,m] then
return false
return true
(The code for symmetric can be optimised.)
A reflexive graph G = (V, E) is transitive iff all shortest paths between any two nodes contain at most one edge. Proof:
Only if: Assume that, for all u, v, w ∈ V, (u, v) ∈ E and (v, w) ∈ E implies (u, w) ∈ E. Take any path v₁,…,vn. If this path has length at least 2, then it can be shortened by replacing v₁ → v₂ → v₃ by v₁ → v₃. Hence all shortest paths have length 1 or less.
If: Assume that all shortest paths contain at most one edge, and assume that (u, v) ∈ E and (v, w) ∈ E. We know that there exists a path from u to w, so there must be a path from u to w of length at most one. If the length is one, then we have (u, w) ∈ E. If the length is zero, then u = w, and hence (u, w) ∈ E follows from reflexivity.
Hence we can check transitivity as follows:
// Precondition: G must be reflexive.
transitive(G):
for every node v in G do
p ← an array containing the lengths of the shortest paths from
v to every node in G (using -1 to mark the absence of a
path)
if any element in p is ≥ 2 then
return false
return true
Finally the pieces above can be combined as follows:
equivalence-relation(G):
return (reflexive(G) and symmetric(G) and transitive(G))
Assuming a uniform cost model.
Assume that the input is G = (V, E). The different functions have the following time complexities:
reflexive: The for loop is iterated at most ∣V∣ times. The total time needed to scan the adjacency lists is O(∣E∣) time units. We get the time complexity O(∣V∣ + ∣E∣).
symmetric: Creating an adjacency matrix takes O(∣V∣²) time units (first allocating and initialising a ∣V∣×∣V∣ matrix, and then updating one matrix entry for every edge in the graph). The nested loops take O(∣V∣²) time units, for a total of O(∣V∣²).
transitive: The following is done at most ∣V∣ times:
Hence the total time is O(∣V∣(∣V∣ + ∣E∣)).
We see that the time complexity is dominated by transitive. The total time required is O(∣V∣(∣V∣ + ∣E∣)).
Basic idea: Find a minimum spanning tree, return the weight of (one of) its most expensive edge(s).
This can be implemented by modifying Kruskal's algorithm so that the weight of the last edge added to the minimum spanning tree is returned.
Assuming a uniform cost model.
This algorithm has the same time complexity as Kruskal's algorithm: O(∣E∣log∣V∣), if we assume that we can compare two weights in constant time.
The algorithm produces a result.
The graph is connected, so it has an MST. Furthermore the graph contains at least two nodes, so any MST contains at least one edge.
The returned value is the spacing of some partition.
Denote the computed MST by T, and (one of) its most expensive edge(s) by e. If we remove e from T, then we get two trees T₁ and T₂. Denote the nodes contained in these trees by V₁ and V₂, respectively. V₁ and V₂ partition the graph, and no edge connecting these sets is strictly cheaper than e (because T is an MST), so the weight of e is the spacing of (V₁, V₂).
The returned value is the largest possible spacing.
Assume that there is some other partition (V₁′, V₂′) which has a strictly larger spacing. This means that e is strictly cheaper than any of the (at least one) cheapest edges between V₁′ and V₂′. Let us denote one of these edges by e′, and the nodes that it connects by v₁′ and v₂′ (with v₁′ ∈ V₁′ and v₂′ ∈ V₂′).
We know that there is a simple path p in T which connects v₁′ and v₂′, because T is a spanning tree. Furthermore v₁′ ∈ V₁′ and v₂′ ∈ V₂′, so we know that at least one of the edges in p must go between V₁′ and V₂′. This edge is not more expensive than e, which in turn is strictly cheaper than e′. However, e′ was assumed to be a cheapest edge between V₁′ and V₂′, so we have found a contradiction.
You may want to try to generalise the algorithm to partitions with more than two components.
This exercise is related to cluster analysis, see for instance the book Algorithm Design by Kleinberg and Tardos. Some examples found online.
No solution given.