`Name:`

Minimal Spanning Tree `Domain:`

Algorithm `Functionality:`

Using Kruskal's Algorithm to find minimal spanning tree. `Input:`

The below diagram figure 1.(a) shows that an undirected non-negative weighted graph with vertices set $V=\{a,b,c,d,e,f,g,h,i\}$ and edge set E as $$t=\{(a,b),(b,c),(b,h),(a,h),(b,c),(c,i),(i,h),(h,g),(i,g),(c,f),(g,f),(c,d),(d,f),(d,e),(e,f)\}$$.
Consider the figure 1.(a) as a base model graph $\rm G=\{V,E\}$, whereas $|V|=9$ and $|E|=14$.Minimal spanning tree for the same is shown in figure 1.(b) as a sub graph $\rm G=\{V',E'\}$,whereas $|V|=9$ and $|E|=8$. `Output:`

Figure 2.(b) displays the obtained Kruskal's minimal spanning tree as $$t'=\{(a,b),(a,h),(c,i), (h,g),(c,f),(g,f),(c,d),(d,e)\}$$.
Adopting Metamorphic Relations to verify NonTestable Graph Theory Algorithms https://doi.org/10.1109/ICACCE.2015.138

`Description:`

`Property:`

A Minimal spanning tree should be connected and has to cover all the vertices of source graph without cycles.We compared the $|V|\in G$ and $|V'|\in G$ results true for equality relation because $|V|=|V'|=9$. `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

For a graph G with N number of vertices, should contain N-1 edges with positive weights in their minimal tree implementation.Because $\rm G'(|E'|)=[G(|V|)/G'(|V'|)-1]$. `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

Always the weight(length) of minimal spanning tree should be equal or less than the weight of all edges of a source graph.Compared with edges as $\rm G'(|E'|)\leq G(|E|)$ is also returning true as result based on the weight values mentioned above. `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

Adding an edge to the spanning tree should create a cycle and removing an edge from spanning tree leaves the spanning tree as disconnected.If we added any edge to this tree is creating a cycle and removing any edge making the graph disconnect is proving MR4. `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

`Source input:`

Spanning tree is a sub graph to its source graph.As all edges of spanning tree are appeared with adjacent connections like $t \subset t$ is supporting MR5. `Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`