Question

(1) Run Prim's algorithm and Kruskal's algorithm for the following graph:

G(V, E)
where V = {A, B, C, D, E}
E = { {A,B}, {B,C}, {C, A}. {B, D}, {B, E}, {D, E}}
use edge weights: w({A, B} = 1), w({B, C}) = 2, w({C, A}) = 3, w({B, D}) = 4, w({B, E}) = 5, w({D, E}) = 6.

(2) Can the maximum weight edge be in every minimum spanning tree of a graph?

Answer 1

V = {A, B, C, D, E}
E = { {A,B}, {B,C}, {C, A}. {B, D}, {B, E}, {D, E}}
Weights = w({A, B} = 1), w({B, C}) = 2, w({C, A}) = 3, w({B, D}) = 4, w({B, E}) = 5, w({D, E}) = 6

Therefore the graph will be:

#1. Kruskal's:

In this algorithm we first sort the edges in non-decreasing order of their weights:

w({A, B} = 1),
w({B, C}) = 2,
w({C, A}) = 3,
w({B, D}) = 4,
w({B, E}) = 5,
w({D, E}) = 6

Now we draw the MST by joining vertices with minimum edge weight, making sure that no cycles are formed.

Hence we start from the minimum edge and move on:

First, let us assume that all the vertices are empty trees we will now one by one establish the connections between them using Kruskal's Algorithm forming the minimum spanning tree of the above graph.
"I will also highlight this work on the graph"

Edge {A, B} has minimum weight, which is 1, so we put this edge in tree:

Now next edge is: {B, C}) = 2

Next edge is {C, A}) = 3:
so the tree will be:

but by joining this edge we have formed a cycle, hence we have to remove this edge:
So the resulting MST will be:

Now next edge is {B, D}) = 4:

Now next edge is {B, E}) = 5:

Now the last edge which is {D, E} = 6:

Here also we see that a cycle is formed and hence we have to remove this edge, So the tree will be:

Now we have no edge left and hence this is the rsulting Minimum Spanning Tree:

This is the resulting MST formed using Kruskal's Algorithm, with total weight = 1 + 2 + 4 + 5 = 12.

Traversing from the graph:
1:

2:

3:
4:

#2 Prim's :

In this algorithm of finding Minimum Spanning Tree,
We create an empty tree,
We then start from a source node or vertex of the graph and then create a tree including that vertex only.
Then we find all the edges connected to that vertex and then find the edge with the minimum weight, and we then connect that minimum weight edge to that vertex of the tree.
We have to make sure that after connecting the new edge there must not be any cycle formed in the tree, and if a cycle is formed we remove that edge.
And we keep doing this we get the resulting minimum spanning tree.

Let's start with the vertex 'A':

Now edges containing A are:
{A, B} = 1,
{C, A} = 3
Here we see that the edge with the minimum weight is {A, B} = 1,
So we get:

Now we have 2 vertices so we find all the edges containing them:
A: {A, B} = 1, {C, A} = 3
B: {A, B} = 1, {B, C} = 2, {B, D} = 4, {B, E} = 5

The edge {A, B} = 1 is already included hence we ignore it.

From the rest of the edges, the minimum weighted is {B, C} = 2, So we include this edge:

Now we have three vertices so now again finding all edges containing them:

A: {A, B} = 1, {C, A} = 3
B: {A, B} = 1, {B, C} = 2, {B, D} = 4, {B, E} = 5
C: {B, C} = 2, {C, A} = 3

Now the minimum weighted edge out of these edges excluding those which are already included in the resulting tree, is {C, A} = 3,

But here if we include this edge we get a cycle formed which we are not allowed to have, Hence we drop this edge and move to next minimum edge which is {B, D} = 4

Now we have 4 vertices and all edges containing them are:
A: {A, B} = 1, {C, A} = 3
B: {A, B} = 1, {B, C} = 2, {B, D} = 4, {B, E} = 5
C: {B, C} = 2, {C, A} = 3
D: {B, D} = 4, {D, E} = 6

Now the minimum weighted edge out of these edges excluding those which are already included in the resulting tree, is {C, A} = 3, but we know that it will form the cycle so we drop this one, and then the next minimum edge which is not already included in the tree is {B, E} = 5,

Now we have 5 vertices so we find all edges containing them:
A: {A, B} = 1, {C, A} = 3
B: {A, B} = 1, {B, C} = 2, {B, D} = 4, {B, E} = 5
C: {B, C} = 2, {C, A} = 3
D: {B, D} = 4, {D, E} = 6
E: {B, E} = 5, {D, E} = 6

Now the minimum weighted edge out of these edges excluding those which are already included in the resulting tree, is {C, A} = 3, but we know that it will form the cycle so we drop this one, and then the next minimum edge which is not already included in the tree is {D, E} = 6,

But if we include this edge we form a cycle and hence we stop here.
There is no more edge to include.

Hence the resulting MST is:

Traversing from the graph:
1:

2:

3:
4:

#3:
Can the maximum weight edge be in every minimum spanning tree of a graph?

NO MAXIMUM WEIGHTED IS NOT NECCERILY INCLUDED IN EVERY MINIMUM SPANNING TREE.
FOR EXAMPLE, IF ALL EDGES ARE OF SAME WEIGHT WHICH IS ALSO MAXIMUM WEIGHT, AND TO FOR A MINIMUM SPANNING TREE WE MUST INCLUDE ALL THE EDGES WITH MINIMUM WEIGHT FORMING NO CYCLES, THUS WE HAVE to INCLUDE THE MAXIMUM WEIGHTED EDGE THERE.

BUT AS I SAID IT IS NOT NECCERY IN EVERY CASE.
AS IN THE GRAPH ABOVE WE HAVE NOT INCLUDED THE MAXIMUM WEIGHTED EDGE.

FOR HELP PLEASE COMMENT.
THANK YOU.