"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = displayarray(1,5,6,0); weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"); //// edges that will form a cycle
for (i = 1; i <= n-1; i++){
for (j = i+1; j <= n; j++){
if(A[i][j] == 1){
weights[i][j] = A[i][j]*Math.ceil(Math.random()*9)+19;}
else if(A[i][j] == 0){
weights[i][j] = A[i][j]+999;}
}}
for(i = 0; i

"
SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

"
/////////////////
var stage_number = new Array(n-1);
for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") +"

"+ eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

";
stop = (stop-0)+1;}
else if(stop

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else { for(nc=step; nc<=noofedges; nc++){ i_rej = bin.shift(); q_edge[nc]=labels[i_rej[0]]+labels[i_rej[1]]; answ[nc]="NC"; which_conclusion[nc]="third";} feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } correct = answ[e]; Correct%QUESTION.NUMBER% = correct; //document.write(Correct%QUESTION.NUMBER%+"

");
////////
Nwidth1 = getFontSize()/16*(n * 60) ;
Nheight = getFontSize()/16*(n * 60) ;
m1=""
QuestionText1%QUESTION.NUMBER% = "This question asks whether or not the edge **"+q_edge[e]+"** was considered when Kinga applied Prim's algorithm. If it was considered, at which step was it added/rejected?

**"+starting+"** was Kinga's starting vertex.

";
QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

";
QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- Input A if you think the edge was accepted, followed by the step number e.g. if the edge was accepted at step 1 input
**A1**; - Input R if you think the edge was rejected, followed by the step number e.g. if the edge was rejected at step 5 input
**R5**; - Input
**NC**if you think the edge was not considered while running the algorithm.

Input your answer in upper case letters in the box below. Please follow the instructions for the answer format written under the input box.

"; //EquationText1%QUESTION.NUMBER% = ""; //just graph displayed Feedback1%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was accepted at STEP "+e+" your answer should be "; Feedback2%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was rejected at STEP "+e+" your answer should be "; Feedback3%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was not considered when finding the minimum spanning tree your answer should be "; conclusion = ""; if (which_conclusion[e]=="first"){conclusion = Feedback1%QUESTION.NUMBER%;} else if (which_conclusion[e]=="second"){conclusion = Feedback2%QUESTION.NUMBER%;} else {conclusion = Feedback3%QUESTION.NUMBER%;} Feedback%QUESTION.NUMBER%="

For a connected and undirected network, a **minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

In the given problem, **"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree: "+MST+".

"+conclusion+"

");
document.write(QuestionText1%QUESTION.NUMBER%+SVG_graph%QUESTION.NUMBER%+QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER%);
document.write("")
document.write(QuestionText3%QUESTION.NUMBER%);
document.write("")
}
if (document.forms[0].name=="FEEDBACK")
{}
else
{question%QUESTION.NUMBER%()}
]]>

"+""+"

") } ]]>

"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = 7; weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"); //// edges that will form a cycle
for (i = 1; i <= n-1; i++){
for (j = i+1; j <= n; j++){
if(A[i][j] == 1){
weights[i][j] = A[i][j]*Math.ceil(Math.random()*9)+19;}
else if(A[i][j] == 0){
weights[i][j] = A[i][j]+999;}
}}
for(i = 0; i

"
SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

"
/////////////////
var stage_number = new Array(n-1);
for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") +"

"+ eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

";
stop = (stop-0)+1;}
else if(stop

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else { for(nc=step; nc<=noofedges; nc++){ i_rej = bin.shift(); q_edge[nc]=labels[i_rej[0]]+labels[i_rej[1]]; answ[nc]="NC"; which_conclusion[nc]="third";} feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } correct = answ[e]; Correct%QUESTION.NUMBER% = correct; //document.write(Correct%QUESTION.NUMBER%+"

");
////////
Nwidth1 = getFontSize()/16*(n * 60) ;
Nheight = getFontSize()/16*(n * 60) ;
m1=""
QuestionText1%QUESTION.NUMBER% = "This question asks whether or not the edge **"+q_edge[e]+"** was considered when Kinga applied Prim's algorithm. If it was considered, at which step was it added/rejected?

**"+starting+"** was Kinga's starting vertex.

";
QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

";
QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- Input A if you think the edge was accepted, followed by the step number e.g. if the edge was accepted at step 1 input
**A1**; - Input R if you think the edge was rejected, followed by the step number e.g. if the edge was rejected at step 5 input
**R5**; - Input
**NC**if you think the edge was not considered while running the algorithm.

Input your answer in upper case letters in the box below. Please follow the instructions for the answer format written under the input box.

"; //EquationText1%QUESTION.NUMBER% = ""; //just graph displayed Feedback1%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was accepted at STEP "+e+" your answer should be "; Feedback2%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was rejected at STEP "+e+" your answer should be "; Feedback3%QUESTION.NUMBER%="

Since edge "+q_edge[e]+" was not considered when finding the minimum spanning tree your answer should be "; conclusion = ""; if (which_conclusion[e]=="first"){conclusion = Feedback1%QUESTION.NUMBER%;} else if (which_conclusion[e]=="second"){conclusion = Feedback2%QUESTION.NUMBER%;} else {conclusion = Feedback3%QUESTION.NUMBER%;} Feedback%QUESTION.NUMBER%="

For a connected and undirected network, a **minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

In the given problem, **"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree: "+MST+".

"+conclusion+"

");
document.write(QuestionText1%QUESTION.NUMBER%+SVG_graph%QUESTION.NUMBER%+QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER%);
document.write("")
document.write(QuestionText3%QUESTION.NUMBER%);
document.write("")
}
if (document.forms[0].name=="FEEDBACK")
{}
else
{question%QUESTION.NUMBER%()}
]]>

"+""+"

") } ]]>

"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = displayarray(1,5,6,0); weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"; QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

"; QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- The pair of letters representing vertices of the edge should be in alphabetical order e.g. write AB not BA;
- In the case when you can choose between edges of the same weight please choose the one that will be first when ordered alphabetically e.g. choose AC not AF, AC not CF;
- Example of the correct format for the answer:
**AC,CE,DE,BC**

Input your answer in the box below as an ordered sequence in upper case, with the first edge added by Prim's algorithm inputted first, then the second etc. Each edge should be separated by a comma.

";
//EquationText1%QUESTION.NUMBER% = ""; //just graph displayed
arrow_ratio_along_line = 0; // places arrow on line: if 0 then no arrow is drawn.
filled = 1; // = 1 filled arrow else open
weights_ratio_along_line = 0.3 // places weights on line: if 0 then no weight is drawn (possibly).
weights_font_colour = "black";
weights_font_scale = 1.3;
SVG_graph%QUESTION.NUMBER% = SVG_network(A,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

"
var stage_number = new Array(n-1);
for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") + "

"+eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

";
stop = (stop-0)+1;}
else if(stop

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else{ feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } //document.write(feedback); SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" Correct%QUESTION.NUMBER% = MST; //document.write(Correct%QUESTION.NUMBER%+"

"); Feedback%QUESTION.NUMBER%="

For a connected and undirected network, a **minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

In the given problem, **"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree:

"; //document.write(Feedback%QUESTION.NUMBER%+"

");
document.write(QuestionText1%QUESTION.NUMBER%+SVG_graph%QUESTION.NUMBER%+QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER%);
document.write("")
document.write(QuestionText3%QUESTION.NUMBER%);
document.write("")
}
if (document.forms[0].name=="FEEDBACK")
{}
else
{question%QUESTION.NUMBER%()}
]]>

"+""+"

") } ]]>

"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = 7; weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"; QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

"; QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- The pair of letters representing vertices of the edge should be in alphabetical order e.g. write AB not BA;
- In the case when you can choose between edges of the same weight please choose the one that will be first when ordered alphabetically e.g. choose AC not AF, AC not CF;
- Example of the correct format for the answer:
**AC,CE,DE,BC**

Input your answer in the box below as an ordered sequence in upper case, with the first edge added by Prim's algorithm inputted first, then the second etc. Each edge should be separated by a comma.

";
//EquationText1%QUESTION.NUMBER% = ""; //just graph displayed
arrow_ratio_along_line = 0; // places arrow on line: if 0 then no arrow is drawn.
filled = 1; // = 1 filled arrow else open
weights_ratio_along_line = 0.3 // places weights on line: if 0 then no weight is drawn (possibly).
weights_font_colour = "black";
weights_font_scale = 1.3;
SVG_graph%QUESTION.NUMBER% = SVG_network(A,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

"
var stage_number = new Array(n-1);
for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") + "

"+eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else{ feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } //document.write(feedback); SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" Correct%QUESTION.NUMBER% = MST; //document.write(Correct%QUESTION.NUMBER%+"

"); Feedback%QUESTION.NUMBER%="

**minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

**"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree:

"; //document.write(Feedback%QUESTION.NUMBER%+"

"+""+"

") } ]]>

"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = displayarray(1,5,6,0); weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"); //// edges that will form a cycle
for (i = 1; i <= n-1; i++){
for (j = i+1; j <= n; j++){
if(A[i][j] == 1){
weights[i][j] = A[i][j]*Math.ceil(Math.random()*9)+19;}
else if(A[i][j] == 0){
weights[i][j] = A[i][j]+999;}
}}
for(i = 0; i **"+starting+"** is your starting vertex.

";
QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

";
QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- The pair of letters representing vertices of the edge should be in alphabetical order e.g. write AB not BA;
- In the case when you can choose between edges of the same weight please choose the one that will be first when ordered alphabetically e.g. choose AC not AF, AC not CF.

Input two upper case letters in the box below.

"; //EquationText1%QUESTION.NUMBER% = ""; //just graph displayed arrow_ratio_along_line = 0; // places arrow on line: if 0 then no arrow is drawn. filled = 1; // = 1 filled arrow else open weights_ratio_along_line = 0.3 // places weights on line: if 0 then no weight is drawn (possibly). weights_font_colour = "black"; weights_font_scale = 1.3; SVG_graph%QUESTION.NUMBER% = SVG_network(A,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" var stage_number = new Array(n-1); for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") +"

"+ eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else{ feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } //document.write(feedback); SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" Correct%QUESTION.NUMBER% = correct; //document.write(Correct%QUESTION.NUMBER%+"

"); Feedback%QUESTION.NUMBER%="

**minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

**"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree: "+MST+".

Then, counting "+e+ordStringOf(e)+" edge gives you the correct answer

"+""+"

") } ]]>

"} else {document.forms[0].elements[item+3].value = "Your answer,

"+ANS+"

"+SHOW+" "} document.forms[0].elements[item+3].value = QuestionText1%QUESTION.NUMBER% + SVG_graph%QUESTION.NUMBER% + QuestionText2%QUESTION.NUMBER%+EquationText1%QUESTION.NUMBER% + document.forms[0].elements[item+3].value; } function question%QUESTION.NUMBER%() { n = 7; weights = getrandommatrix(n, n, 0, 0, 1); X = getrandommatrix(n,n,0,0,1); W = getrandommatrix(n,n,0,0,1); Z = getrandommatrix(n,n,0,0,1); T = getrandommatrix(n,n,0,0,1); S1 = getrandommatrix(n,n,0,0,1); S2 = getrandommatrix(n,n,0,0,1); S3 = getrandommatrix(n,n,0,0,1); S4 = getrandommatrix(n,n,0,0,1); S5 = getrandommatrix(n,n,0,0,1); S6 = getrandommatrix(n,n,0,0,1); c = displayarray(1,3,4,0); myCArray = displayarray( c, 1, n, 0); myCArray_sort=sorting(myCArray,1); do{ do{ do{ A = getrandommatrix(n, n, 0, 0, 1); for(i = 1; i <= n-1; i++){ for(j = i+1; j <= n; j++){ A[i][j] = Math.round(Math.random()); } } for(i = 0; i

"); //// edges that will form a cycle
for (i = 1; i <= n-1; i++){
for (j = i+1; j <= n; j++){
if(A[i][j] == 1){
weights[i][j] = A[i][j]*Math.ceil(Math.random()*9)+19;}
else if(A[i][j] == 0){
weights[i][j] = A[i][j]+999;}
}}
for(i = 0; i **"+starting+"** is your starting vertex.

";
QuestionText2%QUESTION.NUMBER% = "In case you cannot read the weights on the graph, please use the Network Matrix below.

";
QuestionText3%QUESTION.NUMBER% = "

__Important:__

- No spaces should be used in the input box;
- The pair of letters representing vertices of the edge should be in alphabetical order e.g. write AB not BA;
- In the case when you can choose between edges of the same weight please choose the one that will be first when ordered alphabetically e.g. choose AC not AF, AC not CF.

Input two upper case letters in the box below.

"; //EquationText1%QUESTION.NUMBER% = ""; //just graph displayed arrow_ratio_along_line = 0; // places arrow on line: if 0 then no arrow is drawn. filled = 1; // = 1 filled arrow else open weights_ratio_along_line = 0.3 // places weights on line: if 0 then no weight is drawn (possibly). weights_font_colour = "black"; weights_font_scale = 1.3; SVG_graph%QUESTION.NUMBER% = SVG_network(A,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" var stage_number = new Array(n-1); for (ib=0; ib

"+ i_st+ordStringOf(i_st) +" edge added i.e. " + eval("A"+(i_st)+" = edge"+i_st+"") +"

"+ eval("B"+(i_st)+" = SVG_network(S"+i_st+",weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale)") + "

" + "

"+"The next edge of least weight connected to the tree is "+labels[i_rej[0]]+labels[i_rej[1]]+" however it would form a cycle and therefore is rejected. " + "

";} else{ feedback += "

Since all the vertices are now connected the minimum spanning tree has already been formed. Hence, the algorithm stops here." + "

" i_feed=noofedges;} } //document.write(feedback); SVG_tree_graph%QUESTION.NUMBER% = SVG_network(T,weights,arrow_ratio_along_line,filled,weights_ratio_along_line,weights_font_colour,weights_font_scale) + "

" Correct%QUESTION.NUMBER% = correct; //document.write(Correct%QUESTION.NUMBER%+"

"); Feedback%QUESTION.NUMBER%="

**minimum spanning tree** is a connected subgraph of minimum total weight incorporating every vertex of the network.

**Prim's algorithm:** start with defining your starting vertex. Then, connect to it the 'nearest' vertex, that is, the one joined to the starting vertex by the edge with a minimum weight. Afterwards, in each iteration, you connect to the tree of connected vertices that vertex which is 'neareset' to the connected set until all vertices are connected.

**"+starting+"** was a starting vertex. When finding the minimum spanning tree you should have been connecting edges in the following order:

"+feedback+" Connecting edges in the indicated order should form a Minimum Spanning Tree: "+MST+".

Then, counting "+e+ordStringOf(e)+" edge gives you the correct answer

"+""+"

") } ]]>