// Numbas version: finer_feedback_settings
{"name": "Identify whether graphs contain Euler Paths and Circuits", "extensions": ["graphs"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Identify whether graphs contain Euler Paths and Circuits", "tags": [], "metadata": {"description": "<p>This question asks students to identify trees.</p>", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "statement": "<p>Consider the following graphs over the vertices $\\var{vertices}$.</p>\n<p>Which of them contain Euler paths?</p>", "advice": "<ol>\n<li>The degrees of the vertices in the first graph are $\\var{d1}$. The number of vertices with an odd degree is {nodd1}. {advice1}</li>\n<li>The degrees of the vertices in the first graph are $\\var{d2}$. The number of vertices with an odd degree is {nodd2}. {advice2}</li>\n</ol>", "rulesets": {}, "extensions": ["graphs"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"vertices": {"name": "vertices", "group": "Problem Parameters", "definition": "Set([\"a\",\"b\",\"c\",\"d\",\"e\",\"f\"])", "description": "", "templateType": "anything", "can_override": false}, "E1": {"name": "E1", "group": "Graph 1", "definition": "generateEdges(0..length(vertices)-1,0.5,1,false,false)", "description": "<p>Randomly generated graph. We will base our question on this graph.</p>", "templateType": "anything", "can_override": false}, "nvertices": {"name": "nvertices", "group": "Problem Parameters", "definition": "\" as it does not contain the expected number of edges\"", "description": "<p>This is to construct the solution provided in the advice.</p>", "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}, "deg1": {"name": "deg1", "group": "Graph 1", "definition": "map(sum(l),l,adjacencyMatrix(vertices,E1,true))", "description": "<p>Degree Sequence of the vertices in E1.</p>", "templateType": "anything", "can_override": false}, "isEulerPath1": {"name": "isEulerPath1", "group": "Graph 1", "definition": "nodd1<3 and Connect1", "description": "<p>Does $P_1$ contain Euler paths?</p>", "templateType": "anything", "can_override": false}, "P1": {"name": "P1", "group": "Graph 1", "definition": "[E1,EP1,EC1][isEuler1]", "description": "<p>Pick which graph to ask the students about, based on the value of isEuler1.</p>", "templateType": "anything", "can_override": false}, "EP1": {"name": "EP1", "group": "Graph 1", "definition": "makeEulerPath(shuffle(0..length(vertices)-1),deg1,E1,false)", "description": "<p>Construct a graph with Euler paths from E1.</p>", "templateType": "anything", "can_override": false}, "isEulerCircuit1": {"name": "isEulerCircuit1", "group": "Graph 1", "definition": "nodd1=0 and connect1", "description": "<p>Does $P_1$ contain Euler circuits?</p>", "templateType": "anything", "can_override": false}, "n1": {"name": "n1", "group": "Graph 1", "definition": "if(isEulerCircuit1,1,2)", "description": "<p>How many marks to award if a student identifies there are Euler paths. This depends on whether there are also circuit (ie, award 1/2 the marks) or not (award full marks).</p>", "templateType": "anything", "can_override": false}, "EC1": {"name": "EC1", "group": "Graph 1", "definition": "makeEulerPath(shuffle(0..length(vertices)-1),deg1,E1,true)", "description": "<p>Construct a graph with Euler circuits from E1.</p>", "templateType": "anything", "can_override": false}, "isEuler1": {"name": "isEuler1", "group": "Graph 1", "definition": "random(0..2)", "description": "<p>This variable enables us to decide whether we ask about E1 directly, or whether we use it to construct a graph with Euler paths and/or Euler circuits.</p>", "templateType": "anything", "can_override": false}, "d1": {"name": "d1", "group": "Graph 1", "definition": "map(sum(l),l,adjacencyMatrix(vertices,P1,true))", "description": "<p>degree sequence of P1.</p>", "templateType": "anything", "can_override": false}, "G1": {"name": "G1", "group": "Graph 1", "definition": "map([vertices[x[0]],vertices[x[1]]],x,P1)", "description": "<p>So far, all the graphs are labelled with vertices 0,1,2,... $G_1$ relabels the vertices in the graph to correspond to the vertices variable.</p>", "templateType": "anything", "can_override": false}, "E2": {"name": "E2", "group": "Graph 2", "definition": "generateEdges(0..length(vertices)-1,0.5,1,false,false)", "description": "", "templateType": "anything", "can_override": false}, "deg2": {"name": "deg2", "group": "Graph 2", "definition": "map(sum(l),l,adjacencyMatrix(vertices,E2,true))", "description": "", "templateType": "anything", "can_override": false}, "EP2": {"name": "EP2", "group": "Graph 2", "definition": "makeEulerPath(0..length(vertices)-1,deg2,E2,false)", "description": "", "templateType": "anything", "can_override": false}, "EC2": {"name": "EC2", "group": "Graph 2", "definition": "makeEulerPath(0..length(vertices)-1,deg2,E2,true)", "description": "", "templateType": "anything", "can_override": false}, "n2": {"name": "n2", "group": "Graph 2", "definition": "if(isEulerCircuit2,1,2)", "description": "", "templateType": "anything", "can_override": false}, "isEulerCircuit2": {"name": "isEulerCircuit2", "group": "Graph 2", "definition": "nodd2=0 and connect2", "description": "", "templateType": "anything", "can_override": false}, "isEulerPath2": {"name": "isEulerPath2", "group": "Graph 2", "definition": "nodd2<3 and connect2", "description": "", "templateType": "anything", "can_override": false}, "isEuler2": {"name": "isEuler2", "group": "Graph 2", "definition": "random(0..2)", "description": "", "templateType": "anything", "can_override": false}, "P2": {"name": "P2", "group": "Graph 2", "definition": "[E2,EP2,EC2][isEuler2]", "description": "", "templateType": "anything", "can_override": false}, "d2": {"name": "d2", "group": "Graph 2", "definition": "map(sum(l),l,adjacencyMatrix(vertices,P2,true))", "description": "", "templateType": "anything", "can_override": false}, "G2": {"name": "G2", "group": "Graph 2", "definition": "map([vertices[x[0]],vertices[x[1]]],x,P2)", "description": "", "templateType": "anything", "can_override": false}, "nodd1": {"name": "nodd1", "group": "Graph 1", "definition": "sum(map(if(mod(x,2)=0,0,1),x,d1))", "description": "<p>Number of odd-degree vertices in P1.</p>", "templateType": "anything", "can_override": false}, "nodd2": {"name": "nodd2", "group": "Graph 2", "definition": "sum(map(if(mod(x,2)=0,0,1),x,d2))", "description": "", "templateType": "anything", "can_override": false}, "advicepath1": {"name": "advicepath1", "group": "Graph 1", "definition": "if(isEulerPath1,\"Since $\"+{nodd1}+\"\\\\leq 2$, it contains Euler paths,\", \"Since $\"+{nodd1}+\"\\\\geq 2$, it doesn't contain Euler paths,\")", "description": "<p>Construct the feedback to students to explain why there are Euler paths or not.</p>", "templateType": "anything", "can_override": false}, "advicecircuit1": {"name": "advicecircuit1", "group": "Graph 1", "definition": "if(isEulerCircuit1,\" and since there are no odd-degree vertices, it also contains Euler circuits,\", \"Since $\"+{nodd1}+\"\\\\neq 0$, it doesn't contain Euler circuits,\")", "description": "<p>Construct the feedback to students to explain why there are Euler circuits or not.</p>", "templateType": "anything", "can_override": false}, "advicepath2": {"name": "advicepath2", "group": "Graph 2", "definition": "if(isEulerPath2,\"Since $\"+{nodd2}+\"\\\\leq 2$, it contains Euler paths,\", \"Since $\"+{nodd2}+\"\\\\geq 2$, it doesn't contain Euler paths,\")", "description": "", "templateType": "anything", "can_override": false}, "adviceCircuit2": {"name": "adviceCircuit2", "group": "Graph 2", "definition": "if(isEulerCircuit2,\" and since there are no odd-degree vertices, it also contains Euler circuits,\", \"Since $\"+{nodd2}+\"\\\\neq 0$, it doesn't contain Euler circuits,\")", "description": "", "templateType": "anything", "can_override": false}, "connect1": {"name": "connect1", "group": "Graph 1", "definition": "isConnected(0..length(vertices)-1,P1)", "description": "<p>Check if the graph $P_1$ is connected.</p>", "templateType": "anything", "can_override": false}, "advice1": {"name": "advice1", "group": "Graph 1", "definition": "if(connect1,advicepath1 + advicecircuit1,\"The graph is not connected, therefore it doesn't have Euler paths nor circuits.\")", "description": "", "templateType": "anything", "can_override": false}, "connect2": {"name": "connect2", "group": "Graph 2", "definition": "isConnected(0..length(vertices)-1,P2)", "description": "", "templateType": "anything", "can_override": false}, "advice2": {"name": "advice2", "group": "Graph 2", "definition": "if(connect2,advicepath2 + advicecircuit2,\"The graph is not connected, therefore it doesn't have Euler paths nor circuits.\")", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "connect1 and connect2", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Problem Parameters", "variables": ["vertices", "nvertices", "hasloop", "notconnected", "reasons"]}, {"name": "Graph 1", "variables": ["E1", "isEuler1", "deg1", "EP1", "EC1", "P1", "d1", "nodd1", "connect1", "isEulerPath1", "isEulerCircuit1", "G1", "n1", "advicepath1", "advicecircuit1", "advice1"]}, {"name": "Graph 2", "variables": ["E2", "deg2", "EP2", "EC2", "isEuler2", "P2", "d2", "nodd2", "connect2", "isEulerPath2", "isEulerCircuit2", "n2", "G2", "advicepath2", "adviceCircuit2", "advice2"]}], "functions": {"makeEulerPath": {"parameters": [["vertices", "list"], ["deg", "list"], ["G", "list"], ["circuit", "boolean"]], "type": "list", "language": "javascript", "definition": "/* Take a pair of odd-degree verties. If an edge exists between them, remove it, otherwise include it.*/\nlet n = circuit? 1:3\n\nlet G1 = []\nlet exclude = []\n\nlet oddDeg = []\n\nfunction sameEdge(x,e) {\n  return (x[0]===e[0] && x[1]===e[1]) || (x[0] === e[1] && x[1]===e[0])\n}\n\nfunction hasEdge(G,e) {\n  return G.some(x => sameEdge(x,e))\n}\n\nfor (let i=0;i<G.length;i++) {\n  if(deg[i]%2 == 1) { oddDeg.push(i) }\n}\n\nfor (let i=0;i<oddDeg.length-n;i++) {\n  e = [vertices[oddDeg[i]],vertices[oddDeg[i+1]]]\n  //console.log(G,e,hasEdge(G,e))\n  if(hasEdge(G,e)) { exclude.push(e) } else {G1.push(e)}\n  //console.log(exclude)\n}\n\nfor (var e of G) {\n  //console.log(e,exclude,hasEdge(exclude,e))\n  if(!hasEdge(exclude,e)) G1.push(e)\n}\n\nreturn G1"}, "isConnected": {"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 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\nlet T = spanningTree(vert,edges)\n\nreturn T.length>0"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>$\\var{G1}$</p>", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["Contains a Euler path", "Contains a Euler Circuit", "Contains both", "Contains neither."], "matrix": ["if(isEulerPath1,n1,0)", "if(isEulerCircuit1,1,0)", "if(isEulerCircuit1,2,0)", "if(isEulerPath1,0,2)"], "distractors": ["", "", "", ""]}, {"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>$\\var{G2}$</p>", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["Contains a Euler path", "Contains a Euler Circuit", "Contains both", "Contains neither."], "matrix": ["if(isEulerPath2,n2,0)", "if(isEulerCircuit2,1,0)", "if(isEulerCircuit2,2,0)", "if(isEulerPath2,0,2)"], "distractors": ["", "", "", ""]}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "type": "question", "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/"}]}