Question

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n vertices u - v <= k for every edge (u,v), where k is some constant. All nodes have a unique label.

Answer 1

If the given condition for each edge (u,v) is | u-v | <= k (This condition will not holds true if we have k = 6 and N = 5, then let say we have one vertex as N = 5, then we need at least a vertex of -1, which is not possible) since the graph is undirected.

Our idea is simple, we will connect every i = N, N-1, N-2,..... to j = N - k, N-k +1, N-k+2,.... correspondingly to each other. This iteration is possible when we have an even number of vertices. So, we will traverse till we have our condition true and it will become false only in case of the odd value of N. So for the odd value of N, we will connect the leftover ith value to any edge. Then we will join each ith edge with (i+1)th edge to make the graph connected.

N = no. of vertices

Edges = set of unique pairs of vertices that need to be connected.

connected = boolean array with values false, it indicates whether the ith vertex is connected to any edge or not.

end = N

start = N - k

if start is zero then start = 1 // We don't have any vertex with value <=0

end of if

for end till 1 and end > start do :

if end - start <= k then :

make_pair(end, start) and put this into Edges set

connected[end] = connected[start] = true

start = start + 1

else break loop

end of for loop

// Now till here, our all vertices are not connected. Just extract any edge and start connecting every unconnected vertex to its end.

// For example, the extracted edge is 1--9, and leftovers are [ 4, 7, 2 ], then we will connect as 1--5--4---7--2.

edge = Edge[1]

last_vertex = edge.first

for i = 1 till N do:

if connected[i] is false then:

connected[i] = true

  make_pair(last_vertex , i) and put this into Edges set

last_vertex = i // remember, we are creating a chain of edge

end of if

end of for

for each edge in Edge do:

make_pair(second vertex of current edge, first vertex of next edge) and put this into Edge set

end of for