// Numbas version: exam_results_page_options {"name": "Find a spanning tree in an undirected graph", "extensions": ["graphs"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Find a spanning tree in an undirected graph", "tags": [], "metadata": {"description": "
This question asks students to find a spanning tree for simple undirected graphs.
", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "Find spanning trees for the following graphs over the vertices $\\var{vertices}$. Enter your solution as the list of edges, using square brackets - such as [[a,b],[c,d]]
.
This is to construct the solution provided in the advice.
", "templateType": "string", "can_override": false}, "hasloop": {"name": "hasloop", "group": "Problem Parameters", "definition": "\" as it contains a loop\"", "description": "", "templateType": "string", "can_override": false}, "notconnected": {"name": "notconnected", "group": "Problem Parameters", "definition": "\" as it is not connected\"", "description": "", "templateType": "string", "can_override": false}, "reasons": {"name": "reasons", "group": "Problem Parameters", "definition": "[hasloop,notconnected,\"\"]", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "length(T1)>0 and length(T2)>0", "maxRuns": "100"}, "ungrouped_variables": [], "variable_groups": [{"name": "Problem Parameters", "variables": ["vertices", "nvertices", "hasloop", "notconnected", "reasons"]}, {"name": "Graph 1", "variables": ["E1", "G1", "T1"]}, {"name": "Graph 2", "variables": ["E2", "G2", "T2"]}], "functions": {"isTree": {"parameters": [["vert", "list"], ["edges", "list"]], "type": "boolean", "language": "javascript", "definition": "function neighbours(v,G) {\n /* Return all the neighbours of the vector v in the graph G. */\n let nset = []\n for(let e of G) {\n let i = e.indexOf(v)\n if(i > -1) {nset.push(e[1-i])}\n }\n return nset\n}\n\nfunction sum(L) {\n /*Find the sum of the elements in a list.*/\n let s=0\n for (let x of L) { s+=x }\n return s\n}\n\nfunction isTree(vert,G) {\n let visited = []\n let next = [vert[0]]\n while(next.length>0) {\n let v = next.pop()\n let nset = neighbours(v,G)\n if (sum(nset.map(x=>visited.includes(x))) > 1) {return -1}\n visited.push(v)\n for(let n of nset) {if(!visited.includes(n)) next.push(n)}\n }\n if(visited.length === vert.length) return 1\n else return 0\n}\n\nreturn isTree(vert,edges)"}, "spanningTree": {"parameters": [["vert", "list"], ["edges", "list"]], "type": "list", "language": "javascript", "definition": "function neighbours(v,G) {\n /* Return all the neighbours of the vector v in the graph G. */\n let nset = []\n for(let e of G) {\n let i = e.indexOf(v)\n if(i > -1) {nset.push(e[1-i])}\n }\n return nset\n}\n\nfunction sum(L) {\n /*Find the sum of the elements in a list.*/\n let s=0\n for (let x of L) { s+=x }\n return s\n}\n\nfunction spanningTree(vert,G) {\n let visited = []\n let edges = []\n let next = [vert[0]]\n while(next.length>0) {\n let v = next.pop()\n let nset = neighbours(v,G)\n for(var x of nset) {\n if(!visited.includes(x) && !next.includes(x)) edges.push([v,x])\n }\n visited.push(v)\n for(let n of nset) {if(!visited.includes(n) && !next.includes(n)) next.push(n)}\n }\n if(visited.length === vert.length) return edges\n else return []\n}\n\nreturn spanningTree(vert,edges)"}, "randomTree": {"parameters": [["vert", "list"]], "type": "list", "language": "javascript", "definition": "n = vert.length\nedges = [[vert[0],vert[1]]]\nfor(var i=2;iEnter a spanning tree for the graph with edges {G1}:
", "answer": "{t1}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}, {"type": "jme", "useCustomName": true, "customName": "Second Graph", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "studentExpr (The student's answer, parsed):\n assert(trim(studentAnswer)<>\"\",\n warn(translate(\"part.marking.nothing entered\"));\n fail(translate(\"part.marking.nothing entered\"))\n );\n try(\n simplify(\n expand_juxtapositions(\n parse(stringLetters(studentAnswer)),\n [\n \"singleLetterVariables\": settings[\"singleLetterVariables\"],\n \"noUnknownFunctions\": not settings[\"allowUnknownFunctions\"],\n \"implicitFunctionComposition\": settings[\"implicitFunctionComposition\"]\n ]\n ),\n 'basic'\n )\n , message,\n warn(translate(\"part.jme.answer invalid\",[\"message\":message]));\n fail(translate(\"part.jme.answer invalid\",[\"message\":message]))\n )\n\ncheckTree:\n isTree(vertices,cleanAnswer)\n\ncheckSubgraph:\n assert(isSubgraph(cleanAnswer,G2),\n warn(\"Your graph is not a subgraph of the original graph!\")\n incorrect(\"Your grah is not a subgraph of the original graph!\");end())\n\nverifyAnswer:\n if(checkTree=-1,\n warn(\"Your graph is not a tree, as it contains loops.\");\n incorrect(\"Your graph is not a tree, as it contains loops.\");\n end()\n ,\n if(checkTree=0,\n warn(\"Your graph is not connected.\");\n incorrect(\"Your graph is not connected.\");end()\n ,\n correct(\"The graph you entered forms a spanning tree of the original graph.\")\n ))\n \n\nmark:\n apply(studentExpr);\n apply(checkSubgraph);\n apply(checkTree);\n apply(cleanAnswer);\n apply(verifyAnswer)\n\ncleanAnswer (The student's answer, to be reused by other parts):\n Set(map(sort(x),x,eval(studentExpr)))\n\ninterpreted_answer (The student's answer, to be reused by other parts):\n cleanAnswer", "extendBaseMarkingAlgorithm": false, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Enter a spanning tree for the graph with edges {G2}:
", "answer": "{t2}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": "0.001", "failureRate": 1, "vsetRangePoints": "5", "vsetRange": ["0", "1"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "maxlength": {"length": "0", "partialCredit": "0", "message": ""}, "minlength": {"length": "0", "partialCredit": "0", "message": ""}, "valuegenerators": []}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}]}], "contributors": [{"name": "Julien Ugon", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3575/"}]}