Home

Stabilizing nodes from an anchor

1,635.2K Views

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.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment
Cancel

    • 1 Answer(s)

    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.
    Screen Shot 2014-10-09 at 12.39.42 PM

    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.

    Screen Shot 2014-10-09 at 12.57.43 PM

    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.

     

    Cancel
    ronit Guru Answered on 5th August 2015.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle