header

Program Information

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)\}$$.

Reference

 Adopting Metamorphic Relations to verify NonTestable Graph Theory Algorithms https://doi.org/10.1109/ICACCE.2015.138 

MR Information

MR1------

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:

MR2------

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:

MR3------

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:

MR4------

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:

MR5------

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:
Insert title here