Stabilizing nodes from an anchor
In a finite, undirected, connected graph, an integer variable v(n) is associated with each node n. One node is distinguished as the anchor. An operation OP(n) is defined on nodes:
OP(n):
if node n is the anchor, then do nothing,
else set v(n) to the value 1 + min{v(m)}, where m ranges over all neighbors of n that are distinct from n.
An infinite sequence of operations <OP(n),OP(m), …> is executed, the node arguments n, m, … for the operations being chosen arbitrarily and not necessarily fairly. Show that eventually all v(n) stabilize. That is, that after some finite prefix of the infinite sequence of operations, no further operation changes v(n) for any node n.
My First Thought About this question was:
It is obvious that the anchor in this problem plays a key role, and that the anchor is also a node, say a, that has an integer value, v(a), associated with it. Since the graph is connected this means that from any node n, there exists a path to any other node m. We are also unable to determine the order of the sequence of operations.
but finally i got the solution:
Since this graph is connected, we know there is at least one node that shares an edge with the anchor, or at least one node is a direct neighbor to the anchor.
For example: Say the connected undirected graph has 3 nodes.
OP() will be called some finite amount of times. This will continue until all direct neighbors of the anchor are equal to v(a)+1. After this, OP() will be called another finite amount of times. Eventually, the value any given node n, becomes equal to v(a) + d, where d is the length of shortest path from n to a.
At this point, any operation on a node in the graph would result in an unchanged v(n). Thus, the graph is stabilized and this has taken place in a finite amount of steps.
For my example, I used a graph with only 3 nodes, but you can easily see how this effect would take place on a much larger graph. The key here is that the graph is connected, so all nodes have at least one path to the anchor.
Your Answer
More puzzles to try-
Polar Bear riddle
You are on holidays and wake up in the morning, stand up, and look South. You look to the left ...Read More »All Rebus Riddle
What does this rebus riddle mean?Read More »Fill the Picture Grid
A picture is attached with this question. You have to fill the grid in a manner that every row and ...Read More »Victim Murdered in Bathroom
A man is found murdered in his bathroom naked with blood scattered all around him. The bathroom was locked from ...Read More »Birth Day Riddle
John was born on March 5, 1970, in Delhi, India. Jacob was born 25 days before John. The year when ...Read More »Solve Puzzle
If the puzzle you solved before you solved the puzzle you solved after you solved the puzzle you solved before ...Read More »What do you have riddle
If you have five mango and two bananas in one hand and two mango and four bananas in the other ...Read More »Thief in Akbar Emperor
One day, all the courtiers from Akbar’s court were gathered in the assembly hall when one of them told the ...Read More »Solve the Investigation case
A man got killed in his office. The suspects are Edison, Maxis, Jason, Janna, and Sofia. A calendar near the ...Read More »Sum of Squares
Can you find out the smallest number that can be conveyed as the sum of three squares in three unique ...Read More »Measurement
When are there more millimetre than centimetre?Read More »What does the picture indicates?
Measuring time using Ropes
You have two ropes. Each of them burns for one hour. They burn unevenly in different parts though – it ...Read More »Cut 2 equal parts of cake
Given the cake with a irregular piece removed. How can you cut the cake in two equal parts with one ...Read More »Turn again
It turns around once, what is out will not get in. It turns around again, what is in will not ...Read More »Black or Brown Gloves
Mr. Brown has 8 black gloves and 8 brown gloves in his closet. He blindly picks up some gloves from ...Read More »Eye Puzzle
This rectangle of seemingly random colored dots contains a message. Do you know the answer?Read More »Ship name Riddle
Captain John Sparrow is the captain of this famous ship. The captain of this famous ship is Captain John Sparrow. ...Read More »Tell The Meaning
What does this rebus picture means ?Read More »Tennis Player
Why weren’t the tennis players allowed in the restaurant? Why weren’t the tennis players allowed in the restaurant? Why were ...Read More »