Finding the Target Vertex in a Trees Using Minimum Queries

In graph theory, a tree is a connected, acyclic graph that consists of vertices and edges. A common problem in trees involves identifying a specific target vertex through a series of queries. Each query asks whether a chosen vertex is the target, and if not, which adjacent edge leads closer to the target. This problem presents a unique challenge: to minimize the number of queries required to identify the target vertex in the worst-case scenario.

Undirected Trees

In computer science, an undirected tree is a special type of tree in which, unlike a rooted tree, the direction of the edges is not specified.

In other words, in this type of tree, each edge can connect two vertices to each other reciprocally and there is no concept of a “root”.

Undirected trees have various applications in computer science, including:

• Computer networks: In modeling the topology of computer networks, undirected trees are used to represent connections between devices.
• Maps: In displaying maps, undirected trees are used to show routes between different locations.
• Molecules: In chemistry, undirected trees are used to represent the structure of molecules.

Table 1

Problem

We have a (undirected) tree with 10 vertices, one of which is considered the target vertex, but we do not know which one it is. In each question, we can choose a vertex and find out whether it is the target vertex or not, and if it is not, which edge is closer to the target. In the worst case, with how many minimum questions can we find the target vertex?

Solution

To solve this problem, we can first select the node with the highest number of degrees (Here is node 4). In other words, we divide the tree into two subtrees, each of which has (almost) the same number of nodes.

Suppose node 10 is the target node.

Figure 1

By selecting the node with the highest degree, if it was the target node, then we have reached the target node with a query, and if it was not the target node, then according to the scenario, it should tell me which edge is closest to it. (among the three edges orange, blue and black) then with his answer about which edge is closest, then some non-target nodes are discarded.

Figure 2

So with an optimal query that is to select the vertex with the highest degree, many nodes are discarded.

Therefore, according to figures 1 and 2, by selecting nodes 4, 9 and 10, we will reach the target node i.e. 10 with three questions.

How about the tree in the picture below? Do we have a number of vertices that have the highest degree, that is, degree 2?

Figure 3

In this case, we select a node for the first query that results in two subtrees (with equal number of nodes). Now suppose it tells you that the target node is closer to the edge of node 6 (the blue edge), so some nodes are discarded.

Figure 4

At this time I ask if knot number 8 is the target knot, and he says no, and I ask what year it is close to, he says black mane, so again a number of knots are discarded and finally with a Another question of the target node, i.e. node 7 or 6, is selected as the target node, and this time we have reached the target node with at least three questions.

Now I ask if node number 8 is the target node, and he says no, and I ask which edge it is closest to, he says the black edge, so again a number of nodes are discarded.

Figure 5

And finally with a question Another target node, i.e. node 7 or 6, is selected as the target node, and this time we have reached the target node with at least three questions.

How many questions can we reach the target node in the tree in the figure below?

Figure 6

In this tree, one query can reach the target node. First I ask if node #1 is the target node, and he says no, and I ask which edge is closest, and he answers the black edge, so node 5 will be the target node.

Figure 7

Therefore, the best case for such problems is star-shaped trees.

Read More

What is a Trie or Prefix tree

Creating a Python Autocomplete App with Tkinter and Trie Tree

Finding Pairs with a Sum in Python

My YouTube Channel

More shell script videos and linux tutorials on my YouTube Channel.