91影视

The minimum spanning tree is evaluated by using algorithm that are Kruskal鈥檚 algorithm or prim鈥檚 algorithm where the shortest distance from the source and the destination is evaluated and check from which path it is minimum and called the minimum cost spanning tree.

a).

Whenever the border weight is increased by one, the minimal spanning tree does not change. The smallest spanning tree is determined using Kruskal's technique (for finding Minimum Spanning Tree). Let's get started with the Kruskal method for graph.If a minimum spanning tree of G, and that have also computed shortest path for any kind of nodes it accepts particular node s 系 V

The simplest demonstration is that each spanning tree has " n-1 " edges since the graph " G " has " n " vertices. The following are the steps to determining the least spanning tree:

Let's start with vertex " A " on the graph.

The vertex " A " has two edges with weights of 1 between A and B vertices and 5 between A and D vertices. From A to B vertices, whose weight limit is 1 as indicated below, and after that, start with vertex " B ."

The vertex " B " has two edges, another B from to Something like A vertices and the other from B to C vertices, both having a weight of one.

The weight 1 vertices from B to A are already drawn. Then, from B through C vertices, the minimal weight 1 is assessed, as indicated below:

Then comes the vertex " C." The vertex "C " has two edges, one from C to B vertices and the other from C to D vertices, both having a weight of one.

Weight 1 has already been drawn from C to B vertices. Then, from C through D vertices, the minimal weight 1 is assessed, as indicated below:

The following vertex is " D ." The vertex " D" has two edges, one from D to C vertices and the other from D to A vertices, both having a weight of one.

Weight 1 has already been pulled from D to C . As a result, in vertex " D," there is no minimum weight.

Finally, theminimum spanning tree is shown below:

The cost of the minimum spanning tree is the sum of all the weighted edges. That is,

$$\begin{gathered} Cost=Sumofallweightededgesinminimumspanningtree \\ =1+1+1, \\ =3 \end{gathered}$$

Therefore, to use the Kruskal's method, the cost of path A to B is "1" then expense of path B to C is " 1 ," and the cost of path C to D is "1" in the graph "G ."

This revised graph "G " is comparable with above - the graph structure "G " except that each edge weight is increased by one. As a result, the cost of path D to A is "6" the cost of path A to B is "2" the cost of path B to C is "2" and the cost of path C to D is "2."

Steps to determine the minimum spanning tree using the Kruskal鈥檚 algorithm, From the graph,

Let鈥檚 start with the vertex 鈥� A 鈥�. The vertex 鈥� A鈥� contains two edges with weight of 2 from A to B vertices and 6 from A to D vertices. Here, the minimum weight is 2 from A to B vertices and is shown below:

Next, starts with vertex 鈥� C 鈥�.

鈥� The vertex 鈥� C 鈥� contains two edges with weight of 2 from C to B vertices and 2 from C to D vertices.

鈥� The weight 2 from B to A vertices are already drawn. Then, the minimum weight 2 from B to C vertices is considered.

Next, starts with vertex 鈥� C 鈥�.

鈥� The vertex 鈥淐 鈥� contains two edges with weight of 2 from C to B vertices and 2 from C to D vertices.

鈥� The weight 2 from C to B vertices are already drawn. Then, the minimum weight 2 from C to D vertices is considered and is shown below:

Next, starts with vertex 鈥� D 鈥�.

鈥� The vertex 鈥� D鈥� contains two edges with weight of 2 vertices and 6 from D to A vertices.

鈥� The weight 2 from D to C vertices is already drawn. So, there is no minimum weight in vertex 鈥� D 鈥�. Then , the minimum spanning tree is shown below:

Finally, the minimum spanning tree is shown below:

The cost of the minimum spanning tree AD is the sum of all the weighted edges. That is,

$$\begin{gathered} Cost=Sumofallweightededgesinminimumspanningtree \\ =2+2+2 \\ =6 \end{gathered}$$

Thus, the cost of path A to B is "2" cost of path B to C is "2" and cost of path C to D is "2" in graph 鈥� G 鈥� gives the minimum spanning tree using the Kruskal鈥檚 algorithm. Therefore, by incrementing each edge weight by same amount, the minimum spanning tree does not change. Here, proof of Kruskal鈥檚 algorithm is correct. So, it does not change.

YES, Whenever the border weight is raised by one, the shortest pathways may vary.

鈥� Since the size of the path rises as the number of edges on the path increases, the shortest path may vary. In the updated graph, pathways with a small number of edges may be the shortest, but they are unaffected by the original graph.

The cost of path A to B is "1," cost of path B to C is "1," cost of path C to D is 1" and cost of road D to A is "5" as illustrated in the graph " G " below:

Apply Dijkstra's method to the following graph:

1: Begin the initialization process with node " A " and locate the nodes that are next to it. Set the value of the node " A " to " 0," and the rest of the nodes to "infinity." The nodes are next to the " A," node. Then, for each and every neighbour node of node "A" add the cost of "A" node. The node "B = 1" represents the lowest cost value. The following is a depiction of the shortest path tree when node "B = 1".

2. Select the nodes that are next to the minimal node " B." The nodes "C " and "A" are next to the "B" node. Then, for each and every neighbour node of node " B ," add the cost of " " node.

$$\begin{gathered} "1+1=2"forthe"A"node. \\ "1+1=2"forthe"C"node. \end{gathered}$$.

Node " A " is already drawn here. As an example, consider node "C = 2" as a minimum cost value.

Below is a depiction of the shortest path tree for node "C = 2"

3:Find the nodes that are next to the minimal node "C." The nodes "D" and "B" are next to the "C" node. Then, for each and every neighbour node of node "C," add the cost of "C" node.

$"2+1=3"forthe"D"node.$

$"2+1=3"forthe"B"node.$

The lowest cost from the nodes:

Node " B " is already drawn here. Assume that node " D=3 " has the lowest cost value.

The following is a depiction of the shortest path tree when node " D=3 ":

3: Identify the adjacent nodes for minimum node 鈥� 鈥�.

The adjacent nodes of 鈥淒鈥� node are 鈥� C 鈥� and 鈥� A 鈥�. Then, add the cost of 鈥� D 鈥� node to each and every neighbour node of node 鈥� D 鈥�.

鈥� For 鈥� C 鈥� node, 鈥� $3+1=4$鈥�.

鈥� For 鈥� A 鈥� node, 鈥� $3+5=8$鈥�.

Identify the minimum cost from the nodes:

鈥� Here, node 鈥� C 鈥� and node 鈥� A 鈥� are already drawn. So, there is no minimum value in the tree.

The representation of the shortest path tree is shown below:

Therefore, the final shortest-path tree for the given graph is as follows:

As a result, route is the shortest path from point A to point D, with a cost of "6 ". And when the edge weight is raised by the same amount, the shortest pathways may vary.