// Numbas version: exam_results_page_options
{"name": "Identify a full matching in a graph (2)", "extensions": ["graphs"], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Identify a full matching in a graph (2)", "tags": [], "metadata": {"description": "<p>This questions gives a bipartite graph and asks students to identify a full matching of the graph, if it exists.</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>Consider the bipartite graph between the two sets $\\var{S1}$ and $\\var{S2}$ with edges $\\var{edges}$:</p>\n<p>{drawgraph(vnames,indedges,false)}</p>\n<p>Note: if the graph doesn't show well, click on the window and it should appear correctly.</p>", "advice": "<p>There is no full matching in this graph - we can show that using Hall's theorem. For example, if $S=\\var{S}$, $N(S)=\\var{NS}$.</p>", "rulesets": {}, "extensions": ["graphs"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"nvertices": {"name": "nvertices", "group": "Ungrouped variables", "definition": "random(6 .. 10#2)", "description": "", "templateType": "randrange", "can_override": false}, "vnames": {"name": "vnames", "group": "Ungrouped variables", "definition": "map(letterordinal(x),x,0..nvertices-1)", "description": "", "templateType": "anything", "can_override": false}, "S1": {"name": "S1", "group": "Ungrouped variables", "definition": "vnames[0..nvertices/2]\n", "description": "", "templateType": "anything", "can_override": false}, "S2": {"name": "S2", "group": "Ungrouped variables", "definition": "vnames[nvertices/2..nvertices]", "description": "", "templateType": "anything", "can_override": false}, "S": {"name": "S", "group": "Ungrouped variables", "definition": "Set(shuffle(S1)[0..random(3..nvertices/2)-1])", "description": "<p>a set that prevents a matching (has fewer neighbours than required by Hall's theorem).</p>", "templateType": "anything", "can_override": false}, "redges": {"name": "redges", "group": "Ungrouped variables", "definition": "set(map([random(notS),random(S2)],x,1..nvertices*2))", "description": "<p>Randomly generated set of edges</p>", "templateType": "anything", "can_override": false}, "edges": {"name": "edges", "group": "Ungrouped variables", "definition": "sort_by(0,union(redges,SNS))", "description": "", "templateType": "anything", "can_override": false}, "indedges": {"name": "indedges", "group": "Ungrouped variables", "definition": "map([indices(S1,x[0])[0],indices(S2,x[1])[0]+int(nvertices/2)],x,edges)", "description": "", "templateType": "anything", "can_override": false}, "NS": {"name": "NS", "group": "Ungrouped variables", "definition": "Set(shuffle(S2)[0..length(S)-1])", "description": "<p>Neighbours of the set S.</p>", "templateType": "anything", "can_override": false}, "SNS": {"name": "SNS", "group": "Ungrouped variables", "definition": "Set(product(S,NS))", "description": "<p>Edges between S and N(S).</p>", "templateType": "anything", "can_override": false}, "notS": {"name": "notS", "group": "Ungrouped variables", "definition": "filter(not (x in S),x,S1)", "description": "<p>S1\\S</p>", "templateType": "anything", "can_override": false}, "test": {"name": "test", "group": "Ungrouped variables", "definition": "drawgraph(vnames,indedges,false)", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["nvertices", "vnames", "S1", "S2", "S", "NS", "SNS", "redges", "notS", "edges", "indedges", "test"], "variable_groups": [], "functions": {"stringLetters": {"parameters": [["input", "string"]], "type": "string", "language": "javascript", "definition": "return input.replace(/([\\[,])(\\w)(?=[\\],])/g,'$1\\\"$2\\\"');"}, "isSubgraph": {"parameters": [["T", "list"], ["G", "list"]], "type": "boolean", "language": "javascript", "definition": "let T1 = T.map(x=>x.sort())\nlet G1 = G.map(x=>x.sort())\n\nfunction isEdge(e,G) {\n  return G.some(x => (x[0]===e[0] && x[1]===e[1]) || (x[1] === e[0] && x[0]===e[1]))\n}\n\nreturn T1.every(x=>isEdge(x,G1))"}, "neighbours": {"parameters": [["S", "list"], ["G", "list"]], "type": "set", "language": "jme", "definition": "union(Set(map(s[1],s,filter(x[0] in S,x,G))),Set(map(s[0],s,filter(x[1] in S,x,G))))"}, "ishalls": {"parameters": [["S", "list"], ["G", "list"]], "type": "boolean", "language": "jme", "definition": "length(neighbours(S,G)) >= length(S)"}, "show": {"parameters": [["S", "expression"]], "type": "boolean", "language": "javascript", "definition": "return true"}}, "preamble": {"js": "", "css": ".graph {\n  margin: auto;\n       width: 400px;\n      height: 400px;\n      border: 1px solid lightgray; \n}"}, "parts": [{"type": "gapfill", "useCustomName": true, "customName": "Matching", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "<p>Does this graph have a matching?</p>\n<p>[[0]]</p>\n<div data-bind=\"fadeVisible: part.gaps[0].display.studentAnswer()=='0'\">\n<p>Enter a matching (as a list of edges, like [[a,b],[c,d]]): [[1]]</p>\n</div>\n<div data-bind=\"fadeVisible: part.gaps[0].display.studentAnswer()=='1'\">\n<p>Enter a set $S$ so $|N(S)|&lt;|S|$ (as a list of vertices, such as [a,b,c]): [[2]]</p>\n</div>", "gaps": [{"type": "1_n_2", "useCustomName": true, "customName": "Choice", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["yes", "No"], "matrix": ["0", "1"], "distractors": ["", ""]}, {"type": "jme", "useCustomName": true, "customName": "Matching", "marks": "0", "scripts": {}, "customMarkingAlgorithm": "studentExpr (The student's answer, parsed):\n    assert(trim(studentAnswer)<>\"\",\n        warn(\"You did not enter a matching.\");\n        fail(\"No matching was 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\nnotMatching (check that the answer is a matching of the original set):\n    length(distinct(map(x[0],x,cleanAnswer))) < length(cleanAnswer) or \n    length(distinct(map(x[1],x,cleanAnswer))) < length(cleanAnswer)\n\ncheckSubgraph:\n    assert(isSubgraph(cleanAnswer,edges),\n        warn(\"Make sure that you only pick edges from the graph!\")\n        incorrect(\"Make sure that you only pick edges from the graph!\");end()\n        )\n\nverifyAnswer:\n    if(notMatching,\n       warn(\"You did not enter a matching, as some vertices are repeated.\");\n       incorrect(\"You did not enter a matching, as some vertices are repeated.\");\n       end()\n    ,\n    if(length(cleanAnswer) < nvertices/2,\n          warn(\"Your matching is not a full matching.\");\n          incorrect(\"Your matching is not a full matching.\");end()\n    ,\n    correct(\"You entered a full matching of the graph.\")\n     ))\n          \n\nmark:\n    apply(studentExpr);\n    apply(cleanAnswer);\n    apply(checkSubgraph);\n    apply(notMatching);\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": false, "showFeedbackIcon": false, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "[]", "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": "Hall's Theorem", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "studentExpr (The student's answer, parsed):\n    assert(trim(studentAnswer)<>\"\",\n        warn(\"You need to enter a set of vertices.\");\n        fail(\"You need to enter a set of vertices.\")\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\ncheckHalls (check that the answer satisfies Hall's criterion):\n    isHalls(cleanAnswer,edges)\n\nverifyAnswer:\n    if(checkHalls,\n       warn(\"Your solution does not satisfy Hall's criterion.\");\n       incorrect(\"Your solution does not satisfy Hall's criterion.\");\n       end()\n    ,\n    correct(\"Your answer is correct.\")\n     )    \n\nmark:\n    apply(studentExpr);\n    apply(cleanAnswer);\n    apply(checkHalls);\n    apply(verifyAnswer)\n\ncleanAnswer (The student's answer, to be reused by other parts):\n    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, "answer": "{S}", "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": []}], "sortAnswers": false}], "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/"}]}