Questions on graph theory
", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "duration": 0, "percentPass": 0, "showQuestionGroupNames": false, "showstudentname": true, "question_groups": [{"name": "Group", "pickingStrategy": "all-ordered", "pickQuestions": 1, "questionNames": ["", ""], "questions": [{"name": "Number of vertices, edges, vertex degree for a graph", "extensions": [], "custom_part_types": [], "resources": [["question-resources/network1.png", "/srv/numbas/media/question-resources/network1.png"], ["question-resources/network2_DIAdEDD.jpg", "/srv/numbas/media/question-resources/network2_DIAdEDD.jpg"], ["question-resources/network2.png", "/srv/numbas/media/question-resources/network2.png"], ["question-resources/network2a.png", "/srv/numbas/media/question-resources/network2a.png"], ["question-resources/network3.png", "/srv/numbas/media/question-resources/network3.png"], ["question-resources/network4.png", "/srv/numbas/media/question-resources/network4.png"], ["question-resources/network5.png", "/srv/numbas/media/question-resources/network5.png"], ["question-resources/network6.png", "/srv/numbas/media/question-resources/network6.png"], ["question-resources/network7.png", "/srv/numbas/media/question-resources/network7.png"], ["question-resources/network8.png", "/srv/numbas/media/question-resources/network8.png"]], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Merryn Horrocks", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/4052/"}, {"name": "Stephen Maher", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9339/"}], "tags": [], "metadata": {"description": "This question displays one of 10 graphs. It asks the student to either
\n(a) count the vertices, or
\n(b) count the edges, or
\n(c) state how many vertices a spanning tree would contain, or
\n(d) state how many edges a spanning tree would contain, or
\n(e) state the degree of a selected (randomly chosen) vertex.
", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "statement": "{image('resources/question-resources/'+imagelist[imagechoice])}
\n", "advice": "{advice}
", "rulesets": {}, "variables": {"imagelist": {"name": "imagelist", "group": "Ungrouped variables", "definition": "[\n \"network1.png\",\"network2_DIAdEDD.jpg\",\"network2.png\",\n \"network2a.png\",\"network3.png\", \"network4.png\",\n \"network5.png\", \"network6.png\", \"network7.png\", \"network8.png\"\n ]", "description": "", "templateType": "anything"}, "parameter": {"name": "parameter", "group": "Ungrouped variables", "definition": "[\"How many vertices does this network have?\",\n \"How many edges does this network have?\",\n \"How many vertices would be in a spanning tree for this network?\",\n \"How many edges would be in a spanning tree for this network?\"\n \"What is the degree of vertex \" + vertexlist[vertexchoice] + \"?\",\n]", "description": "", "templateType": "anything"}, "vertexlist": {"name": "vertexlist", "group": "Ungrouped variables", "definition": "[\"A\",\"B\",\"C\",\"D\",\"E\"]", "description": "", "templateType": "anything"}, "imagechoice": {"name": "imagechoice", "group": "Ungrouped variables", "definition": "random(0..9)", "description": "", "templateType": "anything"}, "vertexchoice": {"name": "vertexchoice", "group": "Ungrouped variables", "definition": "random(0..2)", "description": "", "templateType": "anything"}, "parameterchoice": {"name": "parameterchoice", "group": "Ungrouped variables", "definition": "random(0..4)", "description": "", "templateType": "anything"}, "answerlist": {"name": "answerlist", "group": "Ungrouped variables", "definition": "[\n[5,7,5,4,2,4,3,2,3],\n[7,13,7,6,2,4,4,5,4],\n[5,9,5,4,4,5,5,2,2],\n[7,12,7,6,2,4,4,5,3],\n[6,10,6,5,4,3,3,5,2],\n[6,9,6,5,2,3,4,2,3],\n[5,8,5,4,3,3,3,3,4],\n[6,8,6,5,3,4,2,2,2],\n[7,13,7,6,3,3,3,6,3],\n[9,11,9,8,2,3,1,3,2]\n]", "description": "Answers to each question for each image.
", "templateType": "anything"}, "answer": {"name": "answer", "group": "Ungrouped variables", "definition": "answerlist[imagechoice][if(parameterchoice<4,parameterchoice,parameterchoice+vertexchoice)]", "description": "", "templateType": "anything"}, "advicelist": {"name": "advicelist", "group": "Ungrouped variables", "definition": "[\n \"There are {answer} vertices. You just count them.\",\n \"There are {answer} edges. You just count them.\",\n \"Since there are {answer} vertices in the network, there must be {answer} vertices in the spanning tree.\",\n \"The spanning tree has one less edge than vertices. Since there are {answer+1} vertices in the network, there will be {answer+1} vertices in the spanning tree, so there will be {answer} edges in the spanning tree.\",\n \"The vertex degree is the number of edge ends attached to the vertex. Vertex {vertexlist[vertexchoice]} has {answer} edge ends attached, so its degree is {answer}.\"\n ]", "description": "", "templateType": "anything"}, "advice": {"name": "advice", "group": "Ungrouped variables", "definition": "advicelist[parameterchoice]", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["imagelist", "parameter", "vertexlist", "imagechoice", "vertexchoice", "parameterchoice", "answerlist", "answer", "advicelist", "advice"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "{parameter[parameterchoice]}
", "minValue": "{answer}", "maxValue": "{answer}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}, {"name": "Identify the minimum spanning tree", "extensions": [], "custom_part_types": [], "resources": [["question-resources/network10.png", "/srv/numbas/media/question-resources/network10.png"], ["question-resources/network9.png", "/srv/numbas/media/question-resources/network9.png"], ["question-resources/network10_minsp.png", "/srv/numbas/media/question-resources/network10_minsp.png"], ["question-resources/network10_spt1.png", "/srv/numbas/media/question-resources/network10_spt1.png"], ["question-resources/network10_subnet.png", "/srv/numbas/media/question-resources/network10_subnet.png"], ["question-resources/network9_minsp.png", "/srv/numbas/media/question-resources/network9_minsp.png"], ["question-resources/network9_sp1.png", "/srv/numbas/media/question-resources/network9_sp1.png"], ["question-resources/network9_sp2.png", "/srv/numbas/media/question-resources/network9_sp2.png"], ["question-resources/network9_tree.png", "/srv/numbas/media/question-resources/network9_tree.png"], ["question-resources/network10_tr2_El8fNuV.png", "/srv/numbas/media/question-resources/network10_tr2_El8fNuV.png"]], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Merryn Horrocks", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/4052/"}, {"name": "Stephen Maher", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9339/"}], "tags": [], "metadata": {"description": "Students are randomly shown one of two networks. They are shown four sub-networks, and asked to identify which one is a minimum spanning tree for the network. Thus, there are 2 versions of this question.
", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "statement": "{image('resources/question-resources/'+imagelist[imagechoice])}
", "advice": "You can either use Prim's algorithm or Kruskal's algorithm to find the minimum spanning tree for yourself.
\nOr you can look through the options and discard those that are not spanning trees, then add up the weights in the remaining options, and choose the one with the least weight.
", "rulesets": {}, "variables": {"imagelist": {"name": "imagelist", "group": "Ungrouped variables", "definition": "[\"network9.png\",\"network10.png\"]", "description": "", "templateType": "anything"}, "imagechoice": {"name": "imagechoice", "group": "Ungrouped variables", "definition": "random(0,1)", "description": "", "templateType": "anything"}, "optionlist": {"name": "optionlist", "group": "Ungrouped variables", "definition": "[\n [\"network9_minsp.png\",\"network9_sp1.png\",\"network9_sp2.png\",\"network9_tree.png\"],\n [\"network10_minsp.png\",\"network10_subnet.png\",\"network10_tr2_El8fNuV.png\",\"network10_spt1.png\"]\n]", "description": "", "templateType": "anything"}, "optiona": {"name": "optiona", "group": "Ungrouped variables", "definition": "optionlist[imagechoice][0]", "description": "", "templateType": "anything"}, "optionb": {"name": "optionb", "group": "Ungrouped variables", "definition": "optionlist[imagechoice][1]", "description": "", "templateType": "anything"}, "optionc": {"name": "optionc", "group": "Ungrouped variables", "definition": "optionlist[imagechoice][2]", "description": "", "templateType": "anything"}, "optiond": {"name": "optiond", "group": "Ungrouped variables", "definition": "optionlist[imagechoice][3]", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["imagelist", "imagechoice", "optionlist", "optiona", "optionb", "optionc", "optiond"], "variable_groups": [], "functions": {}, "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": "Which of the following is a minimum spanning tree for this network?
", "minMarks": 0, "maxMarks": 0, "shuffleChoices": true, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["{image('resources/question-resources/'+optiona)}", "{image('resources/question-resources/'+optionb)}", "{image('resources/question-resources/'+optionc)}", "{image('resources/question-resources/'+optiond)}"], "matrix": ["1", 0, 0, 0], "distractors": ["", "", "", ""]}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}]}], "allowPrinting": true, "navigation": {"allowregen": true, "reverse": true, "browse": true, "allowsteps": true, "showfrontpage": true, "showresultspage": "oncompletion", "navigatemode": "sequence", "onleave": {"action": "none", "message": ""}, "preventleave": true, "startpassword": ""}, "timing": {"allowPause": true, "timeout": {"action": "none", "message": ""}, "timedwarning": {"action": "none", "message": ""}}, "feedback": {"showactualmark": true, "showtotalmark": true, "showanswerstate": true, "allowrevealanswer": true, "advicethreshold": 0, "intro": "", "reviewshowscore": true, "reviewshowfeedback": true, "reviewshowexpectedanswer": true, "reviewshowadvice": true, "feedbackmessages": []}, "contributors": [{"name": "Stephen Maher", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/9339/"}], "extensions": [], "custom_part_types": [], "resources": [["question-resources/network1.png", "/srv/numbas/media/question-resources/network1.png"], ["question-resources/network2_DIAdEDD.jpg", "/srv/numbas/media/question-resources/network2_DIAdEDD.jpg"], ["question-resources/network2.png", "/srv/numbas/media/question-resources/network2.png"], ["question-resources/network2a.png", "/srv/numbas/media/question-resources/network2a.png"], ["question-resources/network3.png", "/srv/numbas/media/question-resources/network3.png"], ["question-resources/network4.png", "/srv/numbas/media/question-resources/network4.png"], ["question-resources/network5.png", "/srv/numbas/media/question-resources/network5.png"], ["question-resources/network6.png", "/srv/numbas/media/question-resources/network6.png"], ["question-resources/network7.png", "/srv/numbas/media/question-resources/network7.png"], ["question-resources/network8.png", "/srv/numbas/media/question-resources/network8.png"], ["question-resources/network10.png", "/srv/numbas/media/question-resources/network10.png"], ["question-resources/network9.png", "/srv/numbas/media/question-resources/network9.png"], ["question-resources/network10_minsp.png", "/srv/numbas/media/question-resources/network10_minsp.png"], ["question-resources/network10_spt1.png", "/srv/numbas/media/question-resources/network10_spt1.png"], ["question-resources/network10_subnet.png", "/srv/numbas/media/question-resources/network10_subnet.png"], ["question-resources/network9_minsp.png", "/srv/numbas/media/question-resources/network9_minsp.png"], ["question-resources/network9_sp1.png", "/srv/numbas/media/question-resources/network9_sp1.png"], ["question-resources/network9_sp2.png", "/srv/numbas/media/question-resources/network9_sp2.png"], ["question-resources/network9_tree.png", "/srv/numbas/media/question-resources/network9_tree.png"], ["question-resources/network10_tr2_El8fNuV.png", "/srv/numbas/media/question-resources/network10_tr2_El8fNuV.png"]]}