File "SL-paper2.html"
Path: /IB QUESTIONBANKS/4 Fourth Edition - PAPER/HTML/Further Mathematics/Topic 6/SL-paper2html
File size: 65.3 KB
MIME-type: text/html
Charset: utf-8
<!DOCTYPE html>
<html>
<meta http-equiv="content-type" content="text/html;charset=utf-8">
<head>
<meta charset="utf-8">
<title>IB Questionbank</title>
<link rel="stylesheet" media="all" href="css/application-212ef6a30de2a281f3295db168f85ac1c6eb97815f52f785535f1adfaee1ef4f.css">
<link rel="stylesheet" media="print" href="css/print-6da094505524acaa25ea39a4dd5d6130a436fc43336c0bb89199951b860e98e9.css">
<script src="js/application-13d27c3a5846e837c0ce48b604dc257852658574909702fa21f9891f7bb643ed.js"></script>
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML-full"></script>
<!--[if lt IE 9]>
<script src='https://cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv.min.js'></script>
<![endif]-->
<meta name="csrf-param" content="authenticity_token">
<meta name="csrf-token" content="iHF+M3VlRFlNEehLVICYgYgqiF8jIFlzjGNjIwqOK9cFH3ZNdavBJrv/YQpz8vcspoICfQcFHW8kSsHnJsBwfg==">
<link href="favicon.ico" rel="shortcut icon">
</head>
<body class="teacher questions-show">
<div class="navbar navbar-fixed-top">
<div class="navbar-inner">
<div class="container">
<div class="brand">
<div class="inner"><a href="http://ibo.org/">ibo.org</a></div>
</div>
<ul class="nav">
<li>
<a href="../../index.html">Home</a>
</li>
<li class="active dropdown">
<a class="dropdown-toggle" data-toggle="dropdown" href="#">
Questionbanks
<b class="caret"></b>
</a><ul class="dropdown-menu">
<li>
<a href="../../geography.html" target="_blank">DP Geography</a>
</li>
<li>
<a href="../../physics.html" target="_blank">DP Physics</a>
</li>
<li>
<a href="../../chemistry.html" target="_blank">DP Chemistry</a>
</li>
<li>
<a href="../../biology.html" target="_blank">DP Biology</a>
</li>
<li>
<a href="../../furtherMath.html" target="_blank">DP Further Mathematics HL</a>
</li>
<li>
<a href="../../mathHL.html" target="_blank">DP Mathematics HL</a>
</li>
<li>
<a href="../../mathSL.html" target="_blank">DP Mathematics SL</a>
</li>
<li>
<a href="../../mathStudies.html" target="_blank">DP Mathematical Studies</a>
</li>
</ul></li>
<!-- - if current_user.is_language_services? && !current_user.is_publishing? -->
<!-- %li= link_to "Language services", tolk_path -->
</ul>
<ul class="nav pull-right">
<li>
<a href="https://06082010.xyz">IB Documents (2) Team</a>
</li></ul>
</div>
</div>
</div>
<div class="page-content container">
<div class="row">
<div class="span24">
</div>
</div>
<div class="page-header">
<div class="row">
<div class="span16">
<p class="back-to-list">
</p>
</div>
<div class="span8" style="margin: 0 0 -19px 0;">
<img style="width: 100%;" class="qb_logo" src="images/logo.jpg" alt="Ib qb 46 logo">
</div>
</div>
</div><h2>SL Paper 2</h2><div class="specification">
<p>The sequence \(\{ {u_n}\} \) satisfies the second-degree recurrence relation</p>
<p>\[{u_{n + 2}} = {u_{n + 1}} + 6{u_n},{\text{ }}n \in {\mathbb{Z}^ + }.\]</p>
</div>
<div class="specification">
<p>Another sequence \(\{ {v_n}\} \) is such that</p>
<p>\[{v_n} = {u_{2n}},{\text{ }}n \in {\mathbb{Z}^ + }.\]</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down the auxiliary equation.</p>
<div class="marks">[1]</div>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Given that \({u_1} = 12,{\text{ }}{u_2} = 6\), show that</p>
<p>\[{u_n} = 2 \times {3^n} - 3 \times {( - 2)^n}.\]</p>
<div class="marks">[5]</div>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Determine the value of \(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n} + {u_{n - 1}}}}{{{u_n} - {u_{n - 1}}}}\).</p>
<div class="marks">[4]</div>
<div class="question_part_label">a.iii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Determine the second-degree recurrence relation satisfied by \(\{ {v_n}\} \).</p>
<div class="marks">[4]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p>In 1985 , the deer population in a national park was \(330\). A year later it had increased to \(420\). To model these data the year 1985 was designated as year zero. The increase in deer population from year \(n - 1\) to year \(n\) is three times the increase from year \(n - 2\) to year \(n - 1\). The deer population in year \(n\)<em> </em>is denoted by \({x_n}\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show that for \(n \geqslant 2,{\text{ }}{x_n} = 4{x_{n - 1}} - 3{x_{n - 2}}\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Solve the recurrence relation.</p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show using proof by strong induction that the solution is correct.</p>
<div class="marks">[9]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph </span><span style="font-family: times new roman,times; font-size: medium;">shown below. State the weight of the tree.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><br><img src="images/kruskal_1.png" alt></span></p>
<div class="marks">[5]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">For the travelling salesman problem defined by this graph, find</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) an upper bound;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) a lower bound.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given that the integers \(m\) and \(n\) are such that \(3|({m^2} + {n^2})\) , prove that \(3|m\) </span><span style="font-family: times new roman,times; font-size: medium;">and \(3|n\) .</span></p>
<div class="marks">[7]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Hence</strong> show that \(\sqrt 2 \) is irrational.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">B.b.</div>
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(a) Consider the recurrence relation \(a{u_{n + 1}} + b{u_n} + c{u_{n - 1}} = 0\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">Show that \({u_n} = A{\lambda ^n} + B{\mu ^n}\) satisfies this relation where \(A\), \(B\) are arbitrary constants and \(\lambda \), \(\mu \) are the roots of the equation \(a{x^2} + bx + c = 0\).</span></p>
<p style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 21px; line-height: normal; font-family: Helvetica; margin: 0px; text-align: center;"><span style="font-family: 'times new roman', times; font-size: medium;">(b) <br><img src="images/Schermafbeelding_2014-09-19_om_14.22.07.png" alt></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">A particle \(P\) executes a random walk on the line above such that when it is at point \(n\left( {1 \leqslant n \leqslant 9,{\text{ }}n \in {\mathbb{Z}^ + }} \right)\) it has a probability \(0.4\) of moving to \(n + 1\) and a probability \(0.6\) of moving to \(n - 1\). The walk terminates as soon as \(P\) reaches either \(0\) or \(10\). Let \({p_n}\) denote the probability that the walk terminates at \(0\) starting from \(n\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) Show that \(2{p_{n + 1}} - 5{p_n} + 3{p_{n - 1}} = 0\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) By solving this recurrence relation subject to the boundary conditions \({p_0} = 1\), \({p_{10}} = 0\) show that \({p_n} = \frac{{{{1.5}^{10}} - {{1.5}^n}}}{{{{1.5}^{10}} - 1}}\).</span></p>
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">The vertices and weights of the graph \(G\) are given in the following table.</span></p>
<p style="font: normal normal normal 21px/normal 'Times New Roman'; text-align: center; margin: 0px;"><br><span style="font-family: 'times new roman', times; font-size: medium;"><img src="images/Schermafbeelding_2014-09-19_om_14.03.12.png" alt></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree for \(G\), indicating clearly the order in which the edges are included.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Draw the minimum spanning tree for \(G\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(b) Consider the travelling salesman problem for \(G\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) An upper bound for the problem can be found by doubling the weight of the minimum spanning tree. Use this method to find an upper bound.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Starting at \({\text{A}}\), use the nearest neighbour algorithm to find another upper bound.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(iii) By first removing \({\text{A}}\), use the deleted vertex algorithm to find a lower bound for the problem.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(c) The travelling salesman problem is now modified so that starting at \({\text{A}}\), the vertices \({\text{B}}\) and \({\text{C}}\) have to be visited first in that order, then \({\text{D}}\), \({\text{E}}\), \({\text{F}}\) in any order before returning to \({\text{A}}\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) Solve this modified problem.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Comment whether or not your answer has any effect on the upper bound to the problem considered in (b).</span></p>
</div>
<br><hr><br><div class="specification">
<p class="p1"><span class="s1">The sequence \(\{ {u_n}:n \in {\mathbb{Z}^ + }\} \) </span>satisfies the recurrence relation \(2{u_{n + 2}} - 3{u_{n + 1}} + {u_n} = 0\), where \({u_1} = 1,{\text{ }}{u_2} = 2\).</p>
</div>
<div class="specification">
<p class="p1">The sequence \(\{ {w_n}:n \in \mathbb{N}\} \) satisfies the recurrence relation \({w_{n + 2}} - 2{w_{n + 1}} + 4{w_n} = 0\), where \({w_0} = 0,{\text{ }}{w_1} = 2\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>Find an expression for \({u_n}\) in terms of \(n\).</p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>Show that the sequence converges, stating the limiting value.</p>
<div class="marks">[9]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1"><span class="s1">The sequence </span>\(\{ {v_n}:n \in {\mathbb{Z}^ + }\} \) satisfies the recurrence relation \(2{v_{n + 2}} - 3{v_{n + 1}} + {v_n} = 1\), where \({v_1} = 1,{\text{ }}{v_2} = 2\)<span class="s2">.</span></p>
<p class="p1">Without solving the recurrence relation prove that the sequence diverges.</p>
<div class="marks">[3]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>Find an expression for \({w_n}\) in terms of \(n\).</p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>Show that \({w_{3n}} = 0\) for all \(n \in \mathbb{N}\).</p>
<div class="marks">[7]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A canal system divides a city into six land masses connected by fifteen bridges, </span><span style="font-family: times new roman,times; font-size: medium;">as shown in the diagram below.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/canals.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Draw a planar graph to represent this map.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Write down the adjacency matrix of the graph.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">List the degrees of each of the vertices.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">State with reasons whether or not this graph has</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) an Eulerian circuit;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) an Eulerian trail.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Find the number of walks of length \(4\) from E to F.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<br><hr><br><div class="specification">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A group of people: Andrew, Betty, Chloe, David, Edward, Frank and Grace, has certain </span><span style="font-family: times new roman,times; font-size: medium;">mutual friendships:</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Andrew is friendly with Betty, Chloe, David and Edward;</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Frank is friendly with Betty and Grace;</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">David, Chloe and Edward are friendly with one another.</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Draw the planar graph \(H\) that represents these mutual friendships.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) State how many faces this graph has.</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Determine, giving reasons, whether \(H\) has</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) a Hamiltonian path;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (ii) a Hamiltonian cycle;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (iii) an Eulerian circuit;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (iv) an Eulerian trail.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Verify Euler’s formula for \(H\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">State, giving a reason, whether or not \(H\) is bipartite.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Write down the adjacency matrix for \(H\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">David wishes to send a message to Grace, in a sealed envelope, through mutual friends.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">In how many different ways can this be achieved if the envelope is passed seven </span><span style="font-family: times new roman,times; font-size: medium;">times and Grace only receives it once?</span></p>
<div class="marks">[7]</div>
<div class="question_part_label">f.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(G\) has the following cost adjacency matrix.<br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/finn.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">Draw \(G\) in planar form.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given that \(ax \equiv b(\bmod p)\) where \(a,b,p,x \in {\mathbb{Z}^ + }\) , \(p\) is prime and \(a\) is not a </span><span style="font-family: times new roman,times; font-size: medium;">multiple of \(p\), use Fermat’s little theorem to show that</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(x \equiv {a^{p - 2}}b(\bmod p)\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Hence solve the simultaneous linear congruences\[3x \equiv 4(\bmod 5)\]\[5x \equiv 6(\bmod 7)\]giving your answer in the form \(x \equiv c(\bmod d)\) .</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">B.b.</div>
</div>
<br><hr><br><div class="specification">
<p><img src="images/watch.png" alt></p>
<p><span style="font-family: times new roman,times; font-size: medium;">The diagram above shows the graph \(G\).</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain briefly why \(G\) has no Eulerian circuit.</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Determine whether or not \(G\) is bipartite.</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(iii) Write down the adjacency matrix of <strong><em>G</em></strong>. Hence find the number of walks of </span><span style="font-family: times new roman,times; font-size: medium;">length \(4\) beginning at A and ending at C.</span></p>
<div class="marks">[12]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The cost adjacency matrix of a graph with vertices P, Q, R, S, T, U is given by</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/14k.png" alt></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Dijkstra’s Algorithm to find the length of the shortest path between the </span><span style="font-family: times new roman,times; font-size: medium;">vertices P and S. Show all the steps used by the algorithm and list the order of </span><span style="font-family: times new roman,times; font-size: medium;">the vertices in the path.</span></p>
<div class="marks">[12]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given the linear congruence \(ax \equiv b({\rm{mod}}p)\) , where \(a\) , \(b \in \mathbb{Z} \) , \(p\) is a prime and </span><span style="font-family: times new roman,times; font-size: medium;">\({\rm{gcd}}(a,p) = 1\) , show that \(x \equiv {a^{p - 2}}b({\rm{mod}}p)\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Solve \(17x \equiv 14(\bmod 21)\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Use the solution found in part (i) to find the general solution to the </span><span style="font-family: times new roman,times; font-size: medium;">Diophantine equation \(17x + 21y = 14\) .</span></p>
<div class="marks">[10]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The following diagram shows a weighted graph \(G\) .</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/andre.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain briefly what features of the graph enable you to state that \(G\) has </span><span style="font-family: times new roman,times; font-size: medium;">an Eulerian trail but does not have an Eulerian circuit.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Write down an Eulerian trail in \(G\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Use Kruskal’s algorithm to find and draw the minimum spanning tree for \(G\) . </span><span style="font-family: times new roman,times; font-size: medium;">Your solution should indicate the order in which the edges are added.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) State the weight of the minimum spanning tree.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Dijkstra’s algorithm to find the path of minimum total weight joining </span><span style="font-family: times new roman,times; font-size: medium;">A to D, and state its weight. Your solution should indicate clearly the use of </span><span style="font-family: times new roman,times; font-size: medium;">this algorithm.</span></p>
<div class="marks">[10]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(H\) has the following adjacency matrix.</span></p>
<p><br><span style="font-family: times new roman,times; font-size: medium;"><img style="display: block; margin-left: auto; margin-right: auto;" src="images/naomi.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Show that \(H\) is bipartite.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Draw \(H\) as a planar graph.</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain what feature of \(H\) guarantees that it has an Eulerian circuit.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Write down an Eulerian circuit in \(H\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Find the number of different walks of length five joining A to B.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Determine how many of these walks go through vertex F after passing </span><span style="font-family: times new roman,times; font-size: medium;">along two edges.</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">A.c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Find the maximum number of extra edges that can be added to \(H\) while keeping </span><span style="font-family: times new roman,times; font-size: medium;">it simple, planar and bipartite.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">A.d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Find the smallest positive integer \(m\) such that \({3^m} \equiv 1(\bmod 22)\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Given that \({3^{49}} \equiv n(\bmod 22)\) where \(0 \le n \le 21\) , find the value of \(n\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">B.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Solve the equation \({3^x} \equiv 5(\bmod 22)\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">B.c.</div>
</div>
<br><hr><br><div class="specification">
<p style="text-align: center;"><img src="images/Schermafbeelding_2017-08-18_om_11.42.18.png" alt="M17/5/FURMA/HP2/ENG/TZ0/01"></p>
<p>The diagram shows the graph \(G\) with the weights of the edges marked.</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>State what features of the graph enable you to state that \(G\) contains an Eulerian trail but no Eulerian circuit.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down an Eulerian trail.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D, stating this total weight. Your solution should show clearly that this algorithm has been used.</p>
<div class="marks">[7]</div>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p class="p1">Consider the following weighted graph.</p>
<p class="p1" style="text-align: center;"><img src="images/Schermafbeelding_2017-02-08_om_16.38.29.png" alt="M16/5/FURMA/HP2/ENG/TZ0/01"></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Determine whether or not the graph is Eulerian.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Determine whether or not the graph is Hamiltonian.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Use Kruskal’s algorithm to find a minimum weight spanning tree and state its weight.</p>
<div class="marks">[6]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Deduce an upper bound for the total weight of a closed walk of minimum weight which <span class="s1">visits every vertex.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Explain how the result in part (b) can be used to find a different upper bound and state <span class="s1">its value.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A connected planar graph has \(e\) edges, \(f\) faces and \(v\) vertices. Prove Euler’s </span><span style="font-family: times new roman,times; font-size: medium;">relation, that is \(v + f = e + 2\) .</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) A simple connected planar graph with \(v\) vertices, where \(v \ge 3\) , has no </span><span style="font-family: times new roman,times; font-size: medium;">circuit of length \(3\). Deduce that \(e \ge 2f\) and therefore that \(e \le 2v - 4\).</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Hence show that \({\kappa _{3,3}}\) is non-planar.</span></p>
<div class="marks">[9]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(P\) has the following adjacency table, defined for vertices A to H, </span><span style="font-family: times new roman,times; font-size: medium;">where each element represents the number of edges between the respective </span><span style="font-family: times new roman,times; font-size: medium;">vertices.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><img src="images/prince.png" alt></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Show that \(P\) is bipartite.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Show that the complement of \(P\) is connected but not planar.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p>While on holiday Pauline visits the local museum. On the ground floor of the museum there are six rooms, A, B, C, D, E and F. The doorways between the rooms are indicated on the following floorplan.</p>
<p style="text-align: center;"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAU8AAADJCAYAAACjU7CDAAAXAElEQVR4Ae2dDXBVZXrH/zdYK4qoiFMTERmlCa67igZ0u+CCMEZju8JAhUqXjxLsohV3ZSTISqujBRH8mBVX3Uoi+MGIGCZxXSlUsqGGnVGS4uzSYjLYcYdsrq0SWERBp+R23gsnXk7uDecm59x7Pn7vTCb3nPOe9zzP73nv/7zn/Tg3lkgkEiJBAAIQgEBWBAqyyk1mCEAAAhBIEjgtlUMsFkvd5DMEIAABCJwgYH9Ip+VJ1YAABCDQCwIntTyt8+0Ka+3nv7sENm3apKlTpwre7nINcmnW0x91wj9RtGJit4iWp50I2xCAAAQcEEA8HUAiCwQgAAE7AcTTToRtCEAAAg4IIJ4OIJEFAhCAgJ0A4mknwjYEIAABBwQQTweQyAIBCEDATgDxtBNhGwIQgIADAoinA0hkgQAEIGAngHjaibANAQhAwAEBxNMBJLJAAAIQsBNAPO1E2IYABCDggADi6QASWSAAAQjYCSCediJsQwACEHBAAPF0AIksEIAABOwEEE87EbYhAAEIOCCAeDqARBYIQAACdgKIp50I2xCAAAQcEEA8HUAiCwQgAAE7AcTTToRtCEAAAg4IIJ4OIJEFAhCAgJ0A4mknwjYEIAABBwQQTweQyAIBCEDATgDxtBNhGwIQgIADAoinA0hkgQAEIGAngHjaibANAQhAwAEBxNMBJLJAAAK9JXBUrdXTFIvFevwrWlyvQ729RJ7OQzzzBN5ctry8XLt27cqjBVwaAl4TOEPFc19X4tgeVZUVqrBym/6YSCjR9XdMn+9Zq/J+XtvhfvnBFM/O32tTxSjdVP2hOt1nkrMS+/fvr5EjR+bselzI/wQsUfG/pW5ZWKABI/5SM0ed6VaBOSsnkOLZuXebflHdrK0bfqO9QVbPnIWZC0HApwQ6W1VX16HvT/muBvrUxExmBVA8D2rXm/+pG1b9gwq3/qsa9x7N5Bv7IQABnxPojO9R88FgtoCCJ56H/kOvN1yhKfOmaGbhRi2t+k3gOpp9Xp89Mu8z1S8e1eOgQSw2TdWt3Aw9CoAvio2vnKhzUgaP+g25U+8d84VpWRsRMPE8qtY3XpcW3qric6/UTTNLFX/5HTUdCuadK+toBfqEwZrwWJMSf9ymykJ1Hzg41qZtS/5ELW2HA+0lxvdM4OQBIzNY9JhKAzhYZLwMlnh2fqzGHd/StGsHSRqs8RV3qSy+VVuaOnqOGEf9T6DgIo2fc6su9L+lWOgagQINKL5O150bLBmy3A+Q1Z061LBem8aU6eoBx80uGP49TS9r18uv/rv+QOPTimkA/x/VR83/pcPF03XvhMEBtB+Te02goFiTJhUHrBV33NsAiWeHmra8rV9VXK5+Vp9Jv8tVsTWuePVr2sLAUa/rb95PPPxbvfnr/827GRiQRwKHd6u+OVhPkIERz87WN/WkVtom2CZ0rK1GcwsbtaHx40DP+cxjtc3LpU8aODj7Oq36lEeHvATCBxftjO/QUz+uk/78XB9Y49yEgIinmZ7UoikV3+s2F6zgou/rb2cWMefTecx9kfOkgYPPf6dHS/7UF3ZhhNsETizPtJ4SbaPtZtlmv6KxWjX4LzRqYEDk6ASiAFj7teL1P9N9T/bTsAtPTxPZARpScqm0dal+tPTfFKcBk4aRz3cNGK6xV53ncyMxr3cETizP7FqOmbo085vP7Y9N6NYw6t31cneWz8XT3LV+qKKJD6kh/qgmnvM3tnmA5vgslVRslBRXw6NlKhryU9UzdSl3NciVK52hy0q/FbgvjyuuU0hgCZzmb8tP3LXmZrLyVMczncd+CEAAAn0j4POWZ9+c42wIQAACXhFAPL0iS7k2AieWZ54zUSvj0vHR9lFaXP+ZLR+bEAgGgVjCvAPrRDIjXyal7LIO8R8CEIBAJAlk0kVanpGsDjgNAQj0lQDi2VeCnA8BCESSAOIZybDjNAQg0FcCiGdfCXI+BCAQSQKIZyTDjtMQgEBfCSCefSXI+RCAQCQJIJ55DHtHR4fa2tryaAGX9huBjz76SLt37/abWdiThgDimQaK17uMaD7zzDM6//zzdfHFF3t9OcoPAAEjmtOmTdPw4cN14403BsBiTEQ8c1gHjhw5ok2bNunmm2/WggULNHr06BxenUv5kUCqaG7cuFFXXnmlPvnkEz+aik02AoinDYgXm5Zojhs3TlOnTtX48ePV0tKi+++/34vLUWYACJinj8rKSl111VUyomlam3v37tWDDz4YAOsx0RBAPD2sB5lEc+XKlSouLvbwyhTtVwKWaA4dOlSrVq3SFVdcoS1btmjr1q267LLL/Go2dqUhgHimgeLGLvNlsLc0EU03yAazjEyi+d5776msrCyYTkXcap+/zzN40dmxY0eyRVFXV6dJkyZp165dGjlyZPAcwWLXCJhH8SeeeEJffPGFrr32Wj3yyCMIpmt081cQLU+X2BvRnDx5ssaOHZsssbGxUbW1tQinS3yDWMzzzz+voqIiPfzwwxo4cKBee+010dIMYiTT24x4pufieG8m0RwzZozjMsgYLgKWaN55551Jx5577jm1t7dr+vTp4XI04t4gnr2sAK2trcnRUtPSNF8Mq6WJaPYSaAhOyySa8+fPD4F3uGAngHjaiZxi2xLNkpISNTQ0qKamRtu3bxeieQpwIT5sBgdHjBghe0sT0Qxx0CUxYOQwvmbaken4N9NLzOR2I5rl5eXq37+/wxLIFjYCZoL7jBkz9P777+uss87SokWLknN3Bw0aFDZX8ScNAcQzDZR0u/bv368DBw4gmungRHRfU1OT9u3bh2hGNP6Ip8PADxkyRC+88ILD3GSLAgEzAMQgUBQind5H+jzTc2EvBCAAgR4JIJ494uEgBCAAgfQEEM/0XNgLAQhAoEcCiGePeDgIAQhAID0BxDM9F/ZCAAIQ6JGAb8TTLHM0fyTnBMyLlc2kfdLJBMyk9bBxMfOMX3rpJZn/YUomTqYeBzH5RjzN24fMUkfz6i6SMwKbN29OLhF1ljs6uZ599tkklzAJjZlnPHv27OSLk8MUSfN7TeYF4UH83vtGPM1KDZPWr18fprrhqS9z5syRefVdUO/cXsF56KGHklzMzSUsycwzNiuYjIAGUWgyxcH8qoJJb731VqYsvt3vG/E0S9pWr16d/G2fMFUOLyNv1tObd4auWLEidI9zfeFm3p9qhCaoLZpMvls/2xKmBob53ptYmR9EDFryjXgacLQ+s68+5u30O3fuVJhaWdlT6H7GPffck9xp3nQUlpTawAhTn65pAJg6/MEHHwQqVL4Sz9TKQevTWT0yv4Vk7ty0Pk/mZR5z161bpwceeCBUg0cVFRXJF9OsWbPmZIcDvGWeoMzLdt5+++1AeeEr8TTkaH1mX3/mzZtH6zMNtttuuy35pTS/UhmWZN7iZR7fzdu9wtT6nDVrVvJGF6RGk+/Ek9Zn9l/z1NZnkCpf9p5md4YRmqeeeio5eGSmL4UlmVchmpZamG4K5idsTDLvyA1K8p14GnC0PrOvPlbrM0yDCdlT6H6GeSQ0bJYuXRqaQbXUm0JY5kabbhYTJzOXNTApkZIkJcyfH9Lq1auTtuzfv98P5nhiQ01Njau8ly1bFnpmvQlES0tLkoupU35P2dSJSZMmJUaPHp348ssv/e6WI/saGxuTcdq1a5ej/LnKlEkXfdnyNHceWp/Z33+tn32g9XkyO9OtYU2DC1M/oZnPGqaZFtdcc00ycOb3wIKQfCue9H1mX31glpmZuRmbfsIwjVJb81nDMtPCdEdYN7kgrA7zrXiarwGtz8xikOmIxSxM8xsz+ZrNfnNjsUapw9JPaPy3+rqrqqqyweHbvGVlZUnb3n33Xd/a2GVYar9Bpmf71Dy5/hzmvs9s+rey4W4xM319pJMJ+L2fsDd1wop3WMYHTIzMn19SJl30dcvTKLzVkqIfr+t+d8oPYZxIfUqnHWYIWz+hcdv6jpjH9zCku+66Kzm9rK2tzdfu+F486cfLvv6EdSJ19iS6n2H1E4Zp3bv5jpjVVGGZOH/99dcnA1dbW9s9gD7a43vxNKysOyutT+c1x5pIHaYBEufe95zTesFGWFpqxltrNVUY4m1u/suWLfP/+0tT+xUyPdun5snX57D16xiOvenfyoa/VT59n92p+ZWNZVd3i0+9xzrXzJcMejJzPY0e+cGXTLoYiJanubPS+uy5NZXuqNX6DNMyvnR+9mZfGNkYn8wbiszje9CT6V4xvqxdu9a/rqTeoTIpbGqefH4OW+vTail4yXTLli2+uYN76WdvyrZWtJg4+CX1tU5YPpm4Bz1ZLPbt25dXVzLpYmBanub2Q+sz+5uwmTcXltZI9t73fIZZ9269zi8sL1QJ01p+6y3z9fX1PQcyT0dPS3ddPz/mmVUiCxYsSAqpGWX0IpmXE5jfVvE6WUsFc8Hb/FyHmRxuvlxepFgs5kWxXWUakfMimRiYJY5mMPLuu+/24hJavny5Dh486KhsN+rEp59+mvTJTDS3Jp07ungWmcxbqt55550szuh9VvOWefPKOreSW3U1rXi6ZaQX5Zi7kXl9lVfC6YXNmcosLCzULbfckumwa/utV9ZdcsklrpUZloIsNldffbVnLpk3BjkVT1MnrCes3hpk+TRs2LDeFnHK8/pa9oEDB5JLZc0KqfPOOy/j9cxNc+jQoRmP9+ZAIpGQGwIaM50JlgFWgSm7rEP8h0BeCFAn84Ld84uaFnZJSYlaWlpkxN7PKVMdDFSfp58BYxsEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EPAFgTPPPDNph/XfF0ZlaUQskUgkrHNisVjyY8ou6xD/IQABCLhKoKOjQ4MGDXK1TC8Ky6SLiKcXtCkTAhAIDYFM4slje2hCjCMQgEAuCSCeuaTNtSAAgdAQQDxDE0ocgQAEckkA8cwlba4FAQiEhgDiGZpQ4ggEIJBLAohnLmlzLQhAIDQEEM/QhBJHIACBXBJAPHNJm2tBAAKhIYB4hiaUOOIvAl8r3vy23nh8topiMZmJ1rEbFqu6rlnx/2tVXV2rOv1lcACt6dSh+p9+w9fi3PW/SDcsfkGb6lt12APvEE8PoFJkxAl0xvX+U3eo9Acb9PGl96j5WEJmyXNi20901bFf6/6h4/XsfqSz77WkQAMnLFd74lNtqyyVyqrUYrFOHNPnLa9opt7Q1IklKp69Th8edpc54tkVwVPdxb6j2Y9vUH3roa4z+ACB7gS+1h9ql2nywv1a+Muf6b4ppSq0vmUFhSqdslA//+UiqaXdk9ZQd3uiuqdAA4onaO5jG7Wnaq700hLd+XyTq8ytsEaVcIrfPd3FvlJ7U6Uu/NW9mjj+XlV/iICmgONjKoFDjXr67p9LlQv196Xnph458blAA0pnasl1x98qlCYDu1wlMFAj5vyTnpl7vhoWPa7XW4+6Vjri6Qjl6SosnalHf/HPKotXa+mLTUI+HYGLWKajan3jea2MF+o7JUUakNH7wRo/5bsamPE4B1wlUPBn+vaYyyU1akPjx671NSOerkaJwqJN4LDaWv5bUpFGDhssvlx+qQ2n68Jhw1WouH7nYnfJaX5xz+92dMbf18tVG7S1cK6q/m4UrQa/Bwz7IOAxAcQzE+CtFSrpV2E7WqrKba9q7ggeuGxg2EwSGKAhJZdKMq1Pkn8IfK1PPt6ruApV1mN3SnYW82SRiddJ0x7MgFGNVs36Sisn3qDZ1btdHbXLZAL7g0bgDA0fe7PK1KyXt/yWfnG/hK/zf7R7xx6pcIp+dNOlrnWnIJ6OAmwGjKbovhc3qqpsv16qeNjVUTtHJpApEAQKim/V4spSxVc+qX9pPpje5s64mhu8mbid/oJR3ntIH659WHdX79f4hbNUdtHprsFAPLNBWTBYw0YWJR/LWtq8WLOQjTHk9SeBwZrwj2tVNev3WjRquhZX16u1a3J2pw631mvd2madNWp4D6Px/vQsWFYdZ129+DZdXrFZJUvWaf3Ca11ljnhmUyM6v9DBz76SdKlKhmSeiJJNkeQNIYEB39bcF7eqqfavpZd/qJKz+51YnrlEr+85R2Vz/kojBvDV63vkrYUtF2jiymYpOU5xYilsrJ/OLvmxtl8wW7VNzdq2/MZvFiv0/cLJEhgwcgiyM96s2lefPt78X3KHyoef4fBMskWSgFlNNOmO5N9jkQSQC6ethS3Lc3Gxbtfg1zO7kJi72FKNmPio4l37bB/GV6rqJ9NU/oOUJXe2LGxCAALhIpDp1zMRz3DFGW8gAAGXCWQSTzpeXAZNcRCAQDQIIJ7RiHMgvdyxY8fxgZZYLJD2Y3RmAsn3m8Zi6ujoyJzJ50cQT58HKIrmGdGcPHmyxo4dG0X3Q+2zFVvLyUGDBlkfA/cf8QxcyMJrcGtrqyorK5Oi2d7ersbGxvA6GzHPLNEM0w0R8YxYJfaju5ZolpSUqKGhQTU1Ndq+fbvGjBnjR3OxKQsCVmyNaFo3xNra2ixK8G9W5nn6Nzaht8x8sdasWaNVq1Zp9OjRSdEsLy9X//79Q+972B2MQmwRz7DXYh/619bWpqeffhrR9GFs+mpSFETTYoR4WiT47zkBM7K6fv16LViwIHmt1atXq6Kigpam5+S9v4CJ7YoVKyJ1Q0Q8va9Xkb9COtGcMWOGgjzSGvmgngCQLrZRuSEinnwLPCOQ7ouFaHqGO6cFE1sJ8cxplYvGxY4cOaLNmzdr6tSpSYfN4zmiGY7YI5rfxBHx/IYFn/pIwBJN0/e1c+dOLVq0SPPmzVNxcXEfS+b0fBOwx3bZsmWaP39+pLteEM9818oQXf/2229XXV1dUjRfeeUVRDNEsR03blzXDZHYHg8sb1UKUQXPtytmFckFF1zgqmhmeqNNvn2N2vXdjm2Q4prJVsQzat+CgPmbqeIGzA3MtREIUlwz2cryTFtQ2YQABCDghADi6YQSeSAAAQjYCCCeNiBsQgACEHBCAPF0Qok8EIAABGwEEE8bEDYhAAEIOCGAeDqhRB4IQAACNgKIpw0ImxCAAAScEEA8nVAiDwQgAAEbAcTTBoRNCEAAAk4IIJ5OKJEHAhCAgI0A4mkDwiYEIAABJwQQTyeUyAMBCEDARgDxtAFhEwIQgIATAoinE0rkgQAEIGAjgHjagLAJAQhAwAkBxNMJJfJAAAIQsBFAPG1A2IQABCDghADi6YQSeSAAAQjYCCCeNiBsQgACEHBCAPF0Qok8EIAABGwEEE8bEDYhAAEIOCGAeDqhRB4IQAACNgKIpw0ImxCAAAScEEA8nVAiDwQgAAEbAcTTBoRNCEAAAk4IIJ5OKJEHAhCAgI0A4mkDwiYEIAABJwQQTyeUyAMBCEDARuA023ZyMxaLpdvNPgjkjQB1Mm/oPb1wkONKy9PTqkHhEIBAWAmc1PJMJBJh9RO/IAABCLhKgJanqzgpDAIQiAoBxDMqkcZPCEDAVQKIp6s4KQwCEIgKgf8HvIisxMfyM/0AAAAASUVORK5CYII="></p>
</div>
<div class="specification">
<p>There are 6 museum s in 6 towns in the area where Pauline is on holiday. The 6 towns and the roads connecting them can be represented by a graph. Each vertex represents a town, each edge represents a road and the weight of each edge is the distance between the towns using that road. The information is shown in the adjacency table.</p>
<p style="text-align: center;"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAr0AAAC1CAYAAABS6EecAAAgAElEQVR4Ae2dDXRU1b32nxl8kbc3Ri8XLWeCryyZlWAl3C6SxlvM244JTvRaLeXTaiGQLAsVpEsWmZhUVMQS87HC1QUtaickoFxJIYWqVzMyY+wF+5I7QSoqZG608TaZcRVKSZgqsDrnvOtMvs5MJkMMM2fmnDyzVlb27H1mf/yes/f+n3P+ex+DJEkS+CEBEiABEiABEiABEiABHRMw6rhtbBoJkAAJkAAJkAAJkAAJBAlcpeRgMBiUXxkmARIgARIgARIgARIgAc0SUDo0hBi9coJs+CoP0GwrdVBxapE8IlILapE8BJKnJuwX1CJ5CCRPTdgvkksLZW3o3qCkwTAJkAAJkAAJkAAJkIAuCdDo1aWsbBQJkAAJkAAJkAAJkICSAI1eJQ2GSYAESIAESIAESIAEdEmARq8uZWWjSIAESIAESIAESIAElARo9CppMEwCJEACJEACJEACJKBLAjo3ei+hu2ktTHdsRZtf1KWAbBQJkAAJkAAJkAAJkMDlCcTZ6L0AT92S4DZo8hYefX/ZKHWdUdTsDFyl2YpjlqDOc0GRzmDSExBPoa7ApNDQAIOpHK7egQsNEb2ucpgGzwEDDAV18AwkJ30DtVRB9rnEqxVBA7k/nPt4eD8Z7AfhfYTjYGx1DJ9n+uejQf7h6SYU1J0Ch6jYqtCXW4T+YTDAVOpCb39xoqcOBcr5wsD+EA8lhvIMH38G7DXFf1Mx6k4NKDT0S82F5NcQKz+AvE1vbD8Br0MqswgShDXS/q6LETLvkU7ai6QZy7dJR72R0iP8JFJU4H+kd975VApEStNgXDy0iCeGQLtdsmKWVLS/cwQNTktO2yrJ3v5lPKsRl7w1p4VafS4utKNnqhUtAl37pSIBEqx2qX1wUOob6wQIktV+clg/CfYhy1OS80rGwej4YpqqFS36Gh2Qzrfvl2zyXARIgs0p9YTQ+FJqty+WYCmT9reHpoQclqRftKWFJAW8h6Xa5bMkIEuyOU8Pp9rjlGyCVbLVH5W8g/1n+GHJGKM1LSTpS6m9/hmp9qg3bEy6KHXtXyMJUef1ZFRgqE7hWsT5Tm/fNYBRyMdjG1dA8P0Z5/4W6dp5IoxIQ/nPipEjTBzjhYMI//u/we5PL47x9/xZbAhcjSnX/QNUObFiU2Fd5qJOn9Mlupg1ypj2ryh9ZjFwogNdg+5VqZi5ogTPWIETRz6GL2Q4FOHv6sT/WrYUljGPgzGrvg4zMiIlfQEq9jSgzCLAV1WLF9vO9bdThL/tl1i1+1Y49zyFBempOmx/cjXJKNyOR7fbUW3xoqryt2FP/i6h+1Azera9iIrCHAicUOIsnh/ea/JRnCMo5m4R/lP/jvK124GiTXh6/k2KtDhXJ47Zq3QqGZGaMx/rLcew+7cfwB/eILETh1tnINc8KTxl9N/9buzY8Dy6Rv8LHkkCOiagQp/TMb3YNG0SzLl3wepzoNl9dihL43TkLs2Fr+5VNHcoXbnOwt38ZyzIna6LyWWowckVki8Iy39ZgeXCGyjZsDO43kP0ObGl/DM88nIZ8njBoZ5gKdn4sXxDzLEVlQc+G3QnEbtfx2bHbdioE0NLPaBjLSkV3/h2OlKUP5dtqp+UYVdGLV57bj7SVLIWlVWIR1i9ZqTMxn3L5qCl9gBaB3095SaJ6G3Zj1arBeZgbUT4Pc2oKczs8xE1FaLmbU+/oSyntWBfTSHMpf+BU63bUWjKRGHN8yi9dz5KWj6Bo/gWTDD0+w37PXDtq0GhWelfKpfZC8/bW1Fo6vNXMRVuR6vvkoJvePpWvO0Z8GWR69CE0jtMMMh1a/pPtLR+POiLpMiEQRJILIFR97nEVlPPpRvNc7HU6sXu5g8UY4QfXe2fAjiMvYc7Byd69H6A5o9yruziX88wY9Y2I1Jm/hBbtq2B0FKNDdteQf2mN2B+7mksSBvrk8aYVW6cZWREqmUVthUBdWurcaD7EiB+hgObj8K68Xu6MbSSX9SJuEGYrLjYPoe2HU+jpGUOqmtWIitFPVMx3qxUbMkkpC9aDRvqUbnPMzTQ4yzchyZgybwbYYT8iOlFbH4jBQ/uPAFJCuC8Kw8nCh/AZnnxW28LNlvuwOKSXfji8z+i98bFWLfejP/Bv2Cj0wW7dQas9pMISG5U5gGuzQ8gf3EJdn2hxHgObTWFWPXOLDzbJUEKdGLbVTtw24qX+x+vnEPb1hq8ce392OmVIEk9cH33QxRanu1bmCV60Lj+d7jt5U5I3gZsmP9/0HPyr8oCGCaBJCEwmj6XJFXVazUG7uruPgT3wMV+7wc4hEWosAKOve+hI+jiIKLX3YKPFsztv/jXK5BkaddEpC14Bq9Vz0FLWSn25qzGipl0aUiIOsabMP/pTSjCdqx9/hA+PvALOKwPYz4vQBIiB3AJPtdz2FDyGZbbn8XqrOsSVI/4FKui0QsgdTYKlpng2P0m3u/3cRO7f4dG5CA7Va7KWbQ2/gpV63NhmiDfhZ2Aa25ZgV2+tr47Jal5qDzlhE0AMPUWzBRuQNaG3+CdDTmht+WDrKYgr/Iw2u2LQ8n1HkPjjluw8bH8Pj8ho4Bvr1qN5ejB+S9EQE6v3oz1t5kwIbh69FrcUlwHX/8jSrHjPew99ld8evREnz+e8SZ8v/B2cLgMxcxvSULgsn0uSeqp22qEuzjIxm0rUPAgFizNBRxv4XDQxYGuDeqfAl+Dac63YIEvZE5Svx4sccD/3Vd1D259IQPr6daQsJNCdi15/EdPob1oE7asmBXBtkpY1WJSsLpGL6bAUvwwrC11+IXjTxBxAR3NDlw7b3af0Sg/3tt9M+ztX8pbSIT8eSvzYmBYyhPOIewOufM7EULOGjQ0P4qsFPSlZ9rRHggtXwrePZ4Cozkfq+4+hpKF2chaWYN9rgHXi5jowUxIIMYELtPnYlwasxtOINTFQX6yBczLTuvz9x1wcaBrw3BwcY6RJ/dNjbfil0drYZHdHHa4h683iXMdmP0Agf6nUoIA61I+7Rigovp/2bXkiSdRhzXY9rQ+3UtUNnrRZzTK/jsvONHxd3kB27dRbJmi0DbMz02RErOg7wMc++8BH90IuQ7efYmQZrwJC15ywH3gRSz7n1oszs9AenETukNWYUf43TiIMk6djm8KXhzvPKNwX1E0XDyDzo9uwPSp9JtTUIl7MHihFrXPxb0K47sApYvDn97Hof4nW33GsOzi8J9wH6Vrg6onib8VteVdeKhmAWbmrESN7OZQshFbXN2Rxy5VK8fCSCARBM6hrXYNFtaZUPZyWQT3kgvw+/+eiIrFtEzVjV4Yb8S8B+8NrtbcVPwEmnJuG/JhG3gUW/xTlDW0KrbzOYf3XX9QLAQZKwMjUqaZkQl51W4VmgYXpwHwfwhX2zmkZs/DMuHXKF71JBrafEMDYDC9fwW2UUDW9x9C5Tud8B7dhjvf3ILnW5Qv3Bhr/TT+u379TrR7I94xEX0fo3W2pd+VReNt1VL1o/U5LbVDs3UdcHF4DfbHXwUGnmz1G8NwvIDSLZ9x1wa19BW74ap6HZPLVvQv0LkOWaufhX25FxU/quhbTKVWXVgOCSQFAXk91U5sKDkGS/VmlOelKRa19VVQ9LwLp5dG7xjkGthK6S/YswthA/1k5Cx5EBY4ULXitn6/Xtm390dwXnvTKNwbvkDQ4PL/AQddsvvE8I8xfQG2VN8DtFRgYca1Q28Ru/dtXJtxHZA6B0vWy+lVWJE94NdrgGEgvff/oWnQwJ2Ir6cJuAo3I2NayGYfwwseFzGTkbPyEdy5+6d4pKYZnsG9SXvhcdWhrMiBnOXZo9BxXMBSsZHR+pyK1RjHRfXd1f0L9rz9dczLntxPYhLMBfejSGhDy8TvcteGuJ8fl+Bra0LNyiI0W9ahSLlwLeUbWFR4LwTfdiz81kPY2qq44RH3erEAJYFLZ3sR4oGoTGQ4PgSCW75Wo8VSgprV2cP8eEXfETxX6cY1enhKO/Teir5Q+NsrwtNj873/zTchbyoayPmi5HXvGnxrDoTlUrWjXTovSVLfG78QfJsO5lokyz3KNx1dlLzOpyQLBMlS5pC8AfntX1l9x0L+zeKhN4EFvJK73iZZgvGCZLHZJafyDTwh6ZCE5bWSYyC954TkPPCGtN/e/3uLTap3h7/FZKAtV/ZfHS2urI7Dfy2/9cgp2W1WBftZ0vLqV0MZD/9hUsdoUwsl0mh9Tnlc8oe1qUUf/+FvAZPHqbkR386W/EpIwT6uhXpKgZOS3dr3Jjb5/Al9C1hA6nGWSUIwvn9+kcMR56fkba02+4XMM3yuDtcneZmPVDNtaRGJv6IfDPQLjfWHAW3CtTDICcpLB4PBEFxApoxjODEEqEViuEcqlVpEopKYOGqRGO6RSqUWkagkJo5aJIZ7pFKpRSQqiYkL10J9n97EtJulkgAJkAAJkAAJkAAJjGMCNHrHsfhsOgmQAAmQAAmQAAmMFwI0eseL0mwnCZAACZAACZAACYxjAjR6x7H4bDoJkAAJkAAJkAAJjBcCIQvZZIdffkiABEiABEiABEiABEhADwSU+zVcpWyQnBC+0k2ZzrC6BKiFuryjlUYtotFRN41aqMs7WmnUIhodddOohbq8o5VGLaLRUTdN1kL5oXuDkgbDJEACJEACJEACJEACuiRAo1eXsrJRJEACJEACJEACJEACSgI0epU0GCYBEiABEiABEiABEtAlARq9upSVjSIBEiABEiABEiABElASoNGrpMEwCZAACZAACZAACZCALglo1+gVT6GuwBTcbUJenRf8M5XD1Sv2CyWi11UO00Ca/L+gDp6BZF3KyUaRAAC/B66mPagpLECp60wEJL3wuA5iX00hzKUu9EY4glGxICDC72lB074aFJqVY5My70vwte1G6R3yWJaJwq1H4OMYpQQUh3CEuWFwnliCOs+FOJTJLEMIcIwKwZG4L5ebC+QxrBk1hZn9tlYBShtaNT1GadfoNc5EUbMXgXY7rJiFov2dCHi3IC91oElGpOZtgVc6DadtFeztX0JqLkL6QHLizjKWTALxIyBfDN7/OBr2V6Bk118ilHMBnrpHsamhHutKduGLCEcwKjYERE897t+0E/vXlWBXRNAi/G3b8cCGT1GwpxNS4C0Unq7AA7Wt8MemCswlIoGzcDc74IuUZr0LueZJkVIYFysCHKNiRfIK87n8XCB2v4WX3gDu2/4HSNJFeI/eh8/L5mt6jNKJCXg1plz3D9BJY67wRObPxzUB+WLw9UbsfPJRWCOCmIT0Ijte2VmBZ6xCxCMYGRsCxvQivP7KC3jymcWRMxQ9aCzfh5yNa5AnTASMach7bD1yamvQyLuNkZnFIrb3Qxy7ugLegAR5b/q+vwB6nBtxz9K5MHMiiQXlkfPgGDUyG1VTLjcXXMAf/3sylvy0AOkpcqeYCCGnGD97JhcttQfQOvhUXdVKX3Fh7N5XjJAZkAAJkMBXJyB2vIe9jjRkTEsZ+nHqbBQs68bew52gl8MQlliGxL/diB/Y8iEoZz/Rg32Vn2BB7nTePIklbOalYQKTMMPyL0hT9hNMxNTpZmj5dklIczSsDqtOAiRAAhoicAEdh9+CQzBj+tSJYfW+CMfe99BBqzeMS2y+GoUZmBG8czWUn3wB0jRtIQro2jAEhSESGIHA1+7ORkZYHxrh0KSLptGbdJKwQiRAAvon4EdX+6dAphnTNDp56Ecj+QKkFbc++J2wu1r6aSFbQgKxISD7w3dj9cN5mu0rNHpjcyYwFxIgARIgAS0SEDtxuOkGFGRP1mLtWWcSUImAvPB2DxquX4PVWdepVGbsi6HRG3umzBFn4CrNjrKdHBGRwHgnkIJpGTcDJzrQ5acfQyLPhqBrw60WZA/u/JPI2rBsEkhSAn43Xmr8R5StzoZiFUKSVnbkamne6DVOnY5vCl4c7zwTeeGHeAadH90QwW9uZChMIQESIIH4EpgEc+5dw3fYkMer4+dg5S4C8cU/mHu/a0PBbKQOxjFAAiQQQkD8DAdf+iPu3vggZmrcHUvzRi+Cq51NONHujbi3pej7GK2zeRUfcgLH/csU5FW6FdsBSZBC9lCOewVYAAkkPQGjeS6WZr6LZvfZobr6vWg/MQdLuYvAEJN4hujaEE+6zFsPBMRuuJ57E9fc/4Mhg9f/IRrqjmjyxUbaN3oxGTkrH8Gdu3+KR2qa4Rl8VCi/aaQOZUUO5CzP5lW8Hjof20ACeiJgTMeSLYvQunk7XL5LgDy5PFuL1vUbsCSdL0hQQ2q6NqhBmWVoloD/FJrKipC//ifIN1095LJ4jRV78E/adHOQwj6AfINOa5+AdL7dKdltVkmuf9/fLGl59auSs71Ha40ZrK82tRisvq4C2tHitOS0ZSn6ASRY7VJ7YECOgNTjLJOEwX4i95fFkr39y4EDkv6/ZrTocUo2YWA8kv8LktV+UhqUIkj6ouQ9uk1aHjzOKtnqj0re0AOSWg/NaBGR4pdSu90mVbv/GjFVa5Ha0YJjVHKcW5eZCwKd0v6iWaFzyeC8oZ05I7xfGGT4yqsQg8EQfCytjGM4MQSoRWK4RyqVWkSikpg4apEY7pFKpRaRqCQmjlokhnukUqlFJCqJiQvXQgfuDYkByVJJgARIgARIgARIgAS0Q4BGr3a0Yk1JgARIgARIgARIgATGSIBG7xjB8WckQAIkQAIkQAIkQALaIUCjVztasaYkQAIkQAIkQAIkQAJjJECjd4zg+DMSIAESIAESIAESIAHtEAjZvUFe5cYPCZAACZAACZAACZAACeiBgHKTsquUDZITwrd3UKYzrC4BaqEu72ilUYtodNRNoxbq8o5WGrWIRkfdNGqhLu9opVGLaHTUTZO1UH7o3qCkwTAJkAAJkAAJkAAJkIAuCdDo1aWsbBQJkAAJkAAJkAAJkICSAI1eJQ2GSYAESIAESIAESIAEdEmARq8uZWWjSIAESIAESIAESIAElARo9CppMEwCJEACJEACJEACJKBLAho2ei/AU7ckuNuEvDqv7y8bpa4zCqHOwFWarThmCeo8FxTpDMaMgN8DV9Me1BQWhGkwUEIvPK6D2FdTCHOpC70D0fxPAuOKQPiYZEJB3SmI44pBIhorwu9pQdO+GhSay+HqjUBc9KF1ayFMwfmkAKVNp+BPRFXHdZmX0N20FqaCOngiSDSu0ajceNHXhoNyfzEZYDCN0GdUrlMsitOw0TsJ6UWNCHgdKLMIgLAG+7veQ2XeFAWXKcirdOGkvQgzlm/DUe/LKEqfpEhnMCYExFOou/9xNOyvQMmuv0TIUr5AeRSbGuqxrmQXvohwBKNIYDwQELt/h1d2tymamouludOh4YFY0ZbkDYqeety/aSf2ryvBrogD0Dm8f+AIcP9L8EoX4T16Hz5f+yNsDrmJkrzt00vNxO7X8cTa7fDppUGabMcl+Fq3Y2XWCjR13ojClh5I3i3IS9XHKKX5VhiFfDy2cQUE359x7m+RLg0nwog0lP+sGDnCRE2egklfaeNMFL3eiJ1PPgprxMrKFyh2vLKzAs9YhYhHMJIE9E/gHN7/94OY8vJpyHui9/018kJcBeGN6UV4/ZUX8OQziyOWJn7yEXpuu69/jpgIIWcpCpcBu5s/4FOpiMTiEOlvRW357zDlzllxyJxZjo6ACH/bdjwwvxXfPODAzg1LkZeeOrqfauQozRu9gBGpOfOx3nIMu3/7wfDHUWInDrfOQK6Zd3g1ck6ymiSgTwK9x9BYuwtVm6tR19QCjz/SRbo+m57srTLOuB2WNMVNEfEMOo/fiPVL5kBfU36yKnEObTv2AOseRsHUq5O1kvqvl9+NHRtewc3bnsZPcwRdPoHSgdELIGU27ls2By21B9Aa4qslordlP1qtFpj10VL9dzq2kAR0SeACPPt2oEp+bttSheKFdyDj3sfR5KF3e3LJLfv+ulBX9m/oKN2G9VnXJVf1dFkb+e7iLjyPB7A6a7IuW6iNRl2Ap7EGJcjH7eKvsVL25TVkorCmWVcX6DoxBSchfdFq2FCPyn0exaKQs3AfmoAl827U5RWLNjoSa0kCJAD0rUGQZH9R92uw26xASwUWrrKjjXd8k+QEkRcZ5uCajHwUV/0Wv28+ig5qE39t5LuLzwPrVmcjJf6lsYSRCMhPxfcegyVnFv759nVo8AZw/uQGoHYlVu1wD3+KPlI+SR6vE6MXQOpsFCwzwbH7TbzfP1DJi0YakYNsnThgJ/m5xOqRAAlclsBECFnfQ1Hla/A6n4Kl5RU0tp697K94gBoE5IXPbkgBL9z1y4CqhbD89AC66YUSR/jn0PaSCzdvWY2sFP2YI3EEFr+s/V60n7gOOQV3Iyu4/smIlJlL8bNnctFSUoNGnex8paOzbAosxQ/D2lKHXzj+BBEX0NHswLXzZtMnK37dhDknPYHwLbL0tf1M0uMfsYITIeStwUYbF0uNiChRCUYBWYWb8IJ9MXxvutHOu71xUkJ2a3gV+2/6IeYr/anjVBqzjU5A/LwTx4dtmzEJ5ty7YMWnaO/SxwZ+OjJ6AaM5H6uKgLoXnOj4u7yA7dsotii3MIsuOlNJgARIQD0CKZiWkYHMDBMf66oHfZQlDUz2ozych42BwFm0Nv4KFQunY8LgXvvXI7+qDXAUI2MC97AeA9Qx/8Q4dTq+KXhxvPOMwkV0ILubkTFNH84nujJ6YbwR8x68F4JjKzYVP4GmnNu4gG3gnOX/cUqg/5Ht4BZZkq72XNS2qH50dWSidFE61xwknZAi/F0d+OTubGTwsXuc1IkwNkmn4bRlAVY72gNeNBfNZN+IE/1h2fa7iJ448jF8gy49ff3ghPUu3eyApS+jd3D7sr9gzy5gATd9H3ZeM4IESCABBEQf2g7+B9p8l/oKD779qxYt85bBwjUHCRBEWWT/W8DuKEVDmy94l0v0OfFs5VmUl8xDms5mSWXLGSaBIQJTYFlXjrvffBLl9R8GF66Jvt/D3vAZ1m9ZgHSd9AOdNGNItr7ty3IBHV2ZKFqXpME+v9EJGcVwoA1V+dfDEPIaSRG9rnKYJtyCYocPvqp8XGvgK6GTVExWKy4ERPQcfQ7Zpqv7tgGq/R389zyGp/PSeCcrLrzDMu11odT0v5FR/GvAV4H8a6cpXv98Fa79xrdwZ3sVVmSbMMGQiZWvnMfC+udRNJO79IaR5FcdEzCmzcdzLTXIfPeHuMZgwIQHfovJ62p0tXWfQZJfC6T4GAyG4JuCFFEMJogAtUgQ+AjFUosIUBIURS0SBD5CsdQiApQERVGLBIGPUCy1iAAlQVHhWujvTm+CwLJYEiABEiABEiABEiCB5CVAozd5tWHNSIAESIAESIAESIAEYkSARm+MQDIbEiABEiABEiABEiCB5CVAozd5tWHNSIAESIAESIAESIAEYkSARm+MQDIbEiABEiABEiABEiCB5CUQsnuDvMqNHxIgARIgARIgARIgARLQAwHlJmVXKRskJ4Rv76BMZ1hdAtRCXd7RSqMW0eiom0Yt1OUdrTRqEY2OumnUQl3e0UqjFtHoqJsma6H80L1BSYNhEiABEiABEiABEiABXRKg0atLWdkoEiABEiABEiABEiABJQEavUoaDJMACZAACZAACZAACeiSAI1eXcrKRpEACZAACZAACZAACSgJ0OhV0mCYBEiABEiABEiABEhAlwQ0aPRegKduSXCXCXlVXvDPVA7XuY9RV2AKjS+og0eUdRPR6yqHaeB4wxLUeS7oUtDENEqE39OCpn01KDSXw9UbhB5WlUvwte1G6R2yRpko3HoEvkiHhf2KX2NB4AxcpdmKvmFCQd0pEH8s2DIPbRDohcd1EPtqCmEudaF3pEr3ulBq6p9XgvMF54qRUI09fjRacL4YO9+v8svxp4UGjd5JSC9qRKBrP4oEAFY72ru2IO+6b6Co+RRO2osgQIDVfhKB5iKkB1toRGreFnS122G1PAWn92UUpU/6KmcGj41CQPTU4/5NO7F/XQl2fRHpQBH+tu14YMOnKNjTCSnwFgpPV+CB2lb4Ix3OuJgSELt/h1d2tynyzMXS3OnQYOdXtIFBEhgtAflGyaPY1FCPdSW7EHGICmZ1Cd2HmrDbp8jXehdyzZwrFESuMDgaLThfXCHkUf58nGohhX0AhMUk69cvpXb7YglCmeTsCQxVMnBSslsFSSjaL3UpoiUpIPU4N0r32E9KIdFDv0y6kHa0kNGNoIecFNRkrmRznh5i3OOUbMJiyd7+5VBcEoe0pYUS5F8ld/XyUPbKZA2GtauFBmFfpsqa0mJgbrA5pZ5I7Tp/VKq2bgydTyIdl6RxutGC84W6Z1i0fqFDLTR8s2cSzLl3wepzoNl9dujKxjgduUtz4at7Fc0dSheGs3A3/xkLeIdriJVKIbHjPex1pCFjWspQiamzUbCsG3sPd/Ix+xCV2Id6j6GxdheqNlejrqkFHj+dGmIPmTlqn4CI3tYDqHX8Cpt/bkeTy8OnUAkSlfNFgsBHKFaPWmjY6AWM5rlYavVid/MHCh8tP7raPwVwONSg6v0AzR/l8FFVhBM7vlEX0HH4LTgEM6ZPnRhW1EU49r6HDtphYVxi9fUCPPt2oEp+XNtSheKFdyDj3sfR5BnRozFWBTMfEtAWAdGDfZX18MGHlqofY2G+BfeWNvEiUXUVOV+ojnzEAvWphaaNXgzc1d19CO6BxVO9H+AQFqHCCoVBJaLX3YKPFsyFWdstHvH0TN6E/ouQTDOmpRC+ujr1+b9L0kV43a/BbrMCLRVYuMqONt7xVVcKlpbcBIwzUdTshRTwwn3gRdgs8nXiWqza4eYdX1WV43yhKu6ohelTC41bIeEuDrJx2woUPIgFS3MBx1s4HHRxoGtD1HObiTonMBFC1vdQVPkavM6nYGl5BY2tCpcgnbeezSOBURMwCsj6/kOodP4XnGWZaKk9gNaBGyqjzoQHkrhmdFYAABrCSURBVAAJJCsBjRu94S4OZ+E+BMzLTuvz9x1wcaBrQwLPvxRMy7gZONGBLt5dTKAOctETIeStwUYbwlyCElytcVN8+NZxBhjk7RZpVCXfGWBMQ95jpbAhbM1I8tVUZzXifJE8gupTC80bvSEuDn96H4eQg+xUY7+/r+zi8J9wH6VrQ+I6Uv/d+PAKiGfQefwcrEvpchKOJr7f5YEsA5kZJiiWFca3SOZOAlokkGJCRmZG6AJcLbZDU3XmfJE8culTC+0bvRhwcXgN9sdfBebNRqp81vT7+8LxAkq3fMZdGxLYk4ILDjPfDd1lw+9F+4k53C9WdV386OrIROmidO7Tqzr7KcirdMt7Qg79ebcgL1UHw7DqLFUo0O9FR1YxFnFPdxVgDxXB+WKIRaJDetRCF6Nt3y4Of8Get7+OedmT+8+TSTAX3I8ioQ0tE7/LXRsS2XuM6ViyZRFaN2+Hy3cJELvherYWres3YAknlPgpI/rQdvA/0CYzlz+iD61ba9EybxksNLTix505a46A6GvDwYNtg2+JFH1HsPXnxzDvkdy+myiaa5GGK8z5InnE06MW4bsga2qD68HK970YQRi26fhpyWmbK1k19EKKwSbJt4O08qKQ4IsmEKyvXGdAiMD8ouQ9uk1aLsjpVslWf1TyauUtIVrSQnkCBbokZ5m1X5dZ0vLqVyVne8Rt+ZW/SvqwZvpF0pO88gpqQwv5xURlkhAcmwbGqdAX4wS8DqnMIvT1FWG5VP3rd6T28xoaoDQzRl1ei76zkvPFlffOy+UwPrUwyFiUlxUGgyH46E0Zx3BiCFCLxHCPVCq1iEQlMXHUIjHcI5VKLSJRSUwctUgM90ilUotIVBITF66FLtwbEoOSpZIACZAACZAACZAACWiFAI1erSjFepIACZAACZAACZAACYyZAI3eMaPjD0mABEiABEiABEiABLRCgEavVpRiPUmABEiABEiABEiABMZMgEbvmNHxhyRAAiRAAiRAAiRAAlohELJ7g7zKjR8SIAESIAESIAESIAES0AMB5SZlVykbJCeEb++gTGdYXQLUQl3e0UqjFtHoqJtGLdTlHa00ahGNjrpp1EJd3tFKoxbR6KibJmuh/NC9QUmDYRIgARIgARIgARIgAV0SoNGrS1nZKBIgARIgARIgARIgASUBGr1KGgyTAAmQAAmQAAmQAAnokgCNXl3KykaRAAmQAAmQAAmQAAkoCdDoVdJgmARIgARIgARIgARIQJcENGz0noGrNDu424S8Om/wr6AOHlHWKjzdhIK6Uwgm6VLKZGmUiF5XOUxKTQbDS1DnuZAsFdVpPXrhcR3EvppCmEtd6I3UStGH1q2F/RoVoLTpFPyRjmPcFRIYhRZyCb0ulJoUY5iB/eQKwfPnmiJwCb623Si9wxScx02FW/G2J+LIpalWaaOy42+M0rDROwV5la04374fNosQPL8EmxM9zUVID7ZKTj+MdvtiwFKG/e2n0Fw0ExpusDb6EM7C3eyAL1JtrXch1zwpUgrjYkLgAjx1j2JTQz3WlezCFxHzPIf3DxwB7n8JXukivEfvw+drf4TNrjMRj2bkWAmMRgs570voPtSE3coOw34yVuj8neYIiPC3bceK53uxcE8nJKkHru9+iEJLOZq6L2muNdqq8PgcozRuAxqRkr4AFXsaUGYR4KuqxYtt5/rPO7kz/RKrdt8K556nsCA9VVvno1Zr2/shjl1dAW9Agrzvc99fAD3Ojbhn6VyYNX7GJbcsk5BeZMcrOyvwjLXvQjC8vuInH6HntvuQI0wEMBFCzlIULgN2N38Q+a5weAb8PkoCl9cimJH/OP79hcl4uScw1F8GL9xHWRQPIwGtEhA9aCzfh28WLu0fk1Ixc8UT2Hb3u1j7/GGOSXHVdXyOUbowQYxCPsp/WYHlwhso2bATbX4Ros+JLeWf4ZGXy5AXnODjevYw834C4t9uxA9s+RCUZ5bowb7KT7AgdzrvtCf4TDHOuB2WNNng7f+IZ9B5/EasXzIHvCwcgKLWfxG9rQdQ6/gVNv/cjiaXh24maqFnOUlBQOx4D3sdaciYljJUH+PXMev2W+DbfQjuXjokDoFJREh/Y5TSNEkE0RiVaUTKzB9iy7Y1EFqqsWHbK6jf9AbMzz2NBcoJPkalMZuRCRiFGZiREnpayQNb07SFKKBrw8jgVE8R4fe4UFf2b+go3Yb1WdepXoNxX2DwYrAePvjQUvVjLMy34N7SJnj8nOjH/bkxLgCI8Hd14MSwtk7E1OlmCL4OdH5OF4dheNSM0OEYFWqdqAkz5mVNRNqCZ/Ba9Ry0lJVib85qrJjJe1cxx/yVM7yAjsOtuPXB7yBNR2fbV8aQVD+QF3nm4JqMfBRX/Ra/bz6KDhpa6itknImiZi+kgBfuAy/CZgFaqtZi1Q437/iqrwZLVJ2AESnTzMjEYew93Dl8kblgxvSpiqdSqtePBUKHY5TOzJCvwTTnW7DAB8fuN/E+J/LE91qxE4ebbkBB9uTE14U16CcgL/J09xlb9cuAqoWw/PQAunmDMTFniFFA1vcfQqXzv+Asy0RL7QG08rFuYrRgqaoSMKbfh1KbCY7Hq1F/qm/HBtHnxm+a2+DLNGNa2FNDVSvHwoYI6GiM0pXRK3a/jk2Nt+KXR2thkd0ceMdk6KRNUCjo2nCrBdmpujrVEkQzxsXKA1nhJrxgXwzfm2608yIxxoC/YnbGNOQ9VgobHGh2n/2KP+bhX41A+JaWBhhM5XDxYuOrYbzio6cgb+MeONb/HY/fci0MpkLUHvkDPm79BFYufL5iujHPQAdjlH4sEX8rasu78FDNAszMWYka2c2hZCO2uLqHPzaJ+ZnADCMT6HdtKJjNRVKRASVB7CSYc++CNQlqwioASDEhIzMjdGEPwZCAngmkpOPODQ3wyrv9eBuwfvYEHG9fgtJF6Vz4nIy6a3yM0ofRK3bDVfU6JpetQFbwcch1yFr9LOzLvaj4UQUOcL+/xHQdujYkhvtXKrVvMcknd2cjg48SvxK5uBzs96IjqxiL0rmfdVz4Dmba7+IzuK2ibHBtQR6fSA0SSkRA9L2Nx1e9hjtfs1GLRAgwmjI1PkZp3OiV3+TShJqVRWi2rEORcuFayjewqPBeCL7tWPith7C11cc7vqM5oWN4DF0bYggzJlldQnfTWpjuKEVDW19/kLf2e7byLMpL5nGhYUwYjz4T0deGgwfb4Ov3pRZ9R7D158cw75FcPhkZPUYeqQcCfg9c+2qw8v++jOsrf8HdZJJEU12OUVLYB5D3SNfAJ3BSslsFSa5v31+WZHOe7q94QOpxlknCYFr/MVa71B7QQNv6q6gZLSIi/VJqt9ukavdfI6ZqLVIbWkQ67xdL9vYv+3EHpPMn66XlwkCfmSUtr94vub0XNSWHPrSQpIDXIZVZ+scwYblU/et3pPbzGhqg5DfPaGW+0NQZPrbKalKLHqdkC45HVslmd2ru/B9JKW1ocbn5Qp9jlEEWTXlRYTAYgm8GUsYxnBgC1CIx3COVSi0iUUlMHLVIDPdIpVKLSFQSE0ctEsM9UqnUIhKVxMSFa6Fx94bEQGSpJEACJEACJEACJEAC2iJAo1dberG2JEACJEACJEACJEACYyBAo3cM0PgTEiABEiABEiABEiABbRGg0astvVhbEiABEiABEiABEiCBMRCg0TsGaPwJCZAACZAACZAACZCAtgiE7N4gr3LjhwRIgARIgARIgARIgAT0QEC5SdlVygbJCeHbOyjTGVaXALVQl3e00qhFNDrqplELdXlHK41aRKOjbhq1UJd3tNKoRTQ66qbJWig/dG9Q0mCYBEiABEiABEiABEhAlwRo9OpSVjaKBEiABEiABEiABEhASYBGr5IGwyRAAiRAAiRAAiRAArokQKNXl7KyUSRAAiRAAiRAAiRAAkoCNHqVNBgmARIgARIgARIgARLQJQENG70X4KlbEtxtQl6dN/BnKnWht18q0VOHAkWawbAEdZ4LuhQy4Y3ye+Bq2oOawgKUus5EqE4vPK6D2FdTCLNCowgHMipuBC6hu2ktTAV18IhxK4QZDxIYzTl/Cb623Si9wwSDIROFW4/AR20GCcYvoORugKlwK972DMwc8SuVOZNA8hIQ0esqhynEZhqwrfRjO2nY6J2E9KJGBLyHUbt8FoAs2Jyn4a3MQ2r/WWVML0JzjxM2wQpb/VF4A40oSp+UvOecVmsmnkLd/Y+jYX8FSnb9JUIr5AuUR7GpoR7rSnbhiwhHMCr+BMTu1/HE2u3wxb8oloDRnPMi/G3b8cCGT1GwpxNS4C0Unq7AA7Wt8JNgHAn0cV/xfC8WytylHri++yEKLeVo6r4Ux3KZNQkkM4GzcDc7Is8P1ruQa9aH7aRho7fv5DEKt+PR7XZUW7yoqvxt2B2sS+g+1IyebS+iojAHguZbm6QdxjgTRa83YueTj8IasYryBYodr+yswDNWIeIRjIwzAX8rast/hyl3yheI/MSfwCjOedGDxvJ9yNm4BnnCRMCYhrzH1iOntgaNfCIVP4n6uX+zcClyZO5IxcwVT2Db3e9i7fOHB58Uxq8CzJkEkpBA74c4dnUFvAEJ8jsb+v4C6HFuxD1L58KsE/tJH81IycaPN66A4NiKygOfYeDpoHxna7PjNmycfxP00dAk7CiskgYInEPbjj3AuodRMPVqDdR3fFRR7HgPex1pyJiWMtTg1NkoWNaNvYc7B8exoUSGYkEgInfj1zHr9lvg230I7t6BGSQWpTEPEtAGAfFvN+IHtvzQm4OiB/sqP8GC3Om6saF0YgsakWpZhW1FQN3aahyQH1GJn+HA5qOwbvwe0nTSSm10HdYyuQjIj3J34Xk8gNVZk5OrauO6NhfQcfgtOAQzpk+V7zYqPxfh2PseOmh7KaHEKCzC39WBE8Nym4ip080QfB3o/JwuDsPwMEL3BIzCDMxICTWW5AvEpmkLUaAT1wZZxNAWallW402Y//QmFGE71j5/CB8f+AUc1ocxPy18QtFyI1l3EviKBPxu7HgeWLc6G4r7iV8xEx4eewJ+dLV/CmSaMS1sool9WcxxiIARKdPMyMThyHfTI16EDP2aIRIYPwTkC/NW3Prgd3R141A/Rq9swaf9K0qfWQxf1T249YUMrKdbw/jpn2xpBALn0PaSCzdvWY0sGlYR+DBqPBIwpt+HUpsJjserUX+qb8cG0efGb5rb4ONFyHg8JdjmSATEThxuugEF2fp6QqgroxeYhPRFq2ETBFh15Hgd6XxkHAlEJyC7NbyK/Tf9kE87ooNKUGoKpmXcDJzoQJeffgzqijAFeRv3wLH+73j8lmthMBWi9sgf8HHrJ5w31BWiv7QzcJVmD247Gtx+1FQOF32rE6LGQKFB14ZbLchO1ZeZqK/WDKjF/yQw7gmcRWvjr1CxcDomDO67eD3yq9oARzEyJphQUHeKi6USdp5Mgjn3ruG7nYhn0Hn8HI2veOuSko47NzTAK69S9zZg/ewJON6+BKWL0nXk8xdviMxfvwT6XRsKZg9uAauXttLo1YuSbAcJhBCYgrxKt2LrGXkLmtNw2rIAqx3tAS+ai2Zygg9hpu4Xo3kulma+i2b32aGC/V60n5iDpTpaLT3UuOQMib638fiq13Dnazbk6eyuVnISD69VhLHKu4VahGNS87tOXRtkhLo1ei+d7eVLENTsJCyLBEjgqxEwpmPJlkVo3bwdLp+840w3XM/WonX9BizhS3S+GsuxHC2/RXJfDVb+35dxfeUvsD7rurHkwt+QgO4I6NW1QRZKR0Zvv1/Qtfmo8vnQUnIbrjFkj/BKXN2dowluUB/7CRnFcKANVfnXwxDyqtv+1xtOuAXFDh98Vfm4lq+ETrBmLD6+BEZzzhuRkrUGeyqnoCHrahgmFKE54wnsWZ/DnTbiKU6vC6UmAwzXPILm3jn42fGdeDRH0NNkGE96zFv3BGTXhnZYlszRnWuDLJ1Bkl+7ofjITuRhUYpUBtUkQC3UpB29LGoRnY+aqdRCTdrRy6IW0fmomUot1KQdvSxqEZ2PmqnhWujoTq+aGFkWCZAACZAACZAACZCAlgjQ6NWSWqwrCZAACZAACZAACZDAmAjQ6B0TNv6IBEiABEiABEiABEhASwRo9GpJLdaVBEiABEiABEiABEhgTARo9I4JG39EAiRAAiRAAiRAAiSgJQIhuzfIq9z4IQESIAESIAESIAESIAE9EFDuSHaVskFyQvj2Dsp0htUlQC3U5R2tNGoRjY66adRCXd7RSqMW0eiom0Yt1OUdrTRqEY2OummyFsoP3RuUNBgmARIgARIgARIgARLQJQEavbqUlY0iARIgARIgARIgARJQEqDRq6TBMAmQAAmQAAmQAAmQgC4J0OjVpaxsFAmQAAmQAAmQAAmQgJIAjV4lDYZJgARIgARIgARIgAR0SUAHRq+IXlc5TAZDcOcJeaXesD9TMepO9epSwORolAi/pwVN+2pQaC6Hq1cMq5ac3oyawsx+bQpQ2tAKX/hhYb/i19gSEH1tOChrZDLAYIqkU2zLY2698LgOYl9NIcylLkQegS7B17YbpXeYYDBkonDrEfaLuJw4o9ECQK8LpXL/GJxHlqDOcyEuNWKmMoFo8zfZ8xyJPQEdGL2X8Pmf/gElR70ISBLkbdf6/i6ia/8aCJiFom1PYMXM1NjTY45BAqKnHvdv2on960qw64vhUMTut/DSG8B92/8ASboI79H78HnZfDxQ2wr/8MMZE3MCl+Br3Y6VWSvQ1HkjClt6IHm3IC9VB90/5qxileEFeOoexaaGeqwr2YUI3SI44fvbtuOBDZ+iYE8npMBbKDxdwX4RKwkG8xmNFvLBl9B9qAm7fYM/BKx3Idc8SRHBYGwJnIW72QEl8sH8yX4QBQMxJCCFfQDZZtTS57T0zv7fSz0hVQ5I50/WS8sFSELRfqkrEJKomS/a0uJLqd2+WIJQJjl7lMC/lDre+X2YBiMdm7zSaEsLJceAdN5dK1mE5VLtUa+kVEZ5lJbCmtIicFKyWwVJsDnDxihJkoJpcyWb8/QQ/h6nZBMWS/b2L4fikjikGy1kxuePStXWjWHjVxLDD6uaprQYqHvPO1L1RofkDRmYAlKPc6N0j/2kZscrTWoxoInO/odroYNbPan4xrfTkaK8EPC7seMnZdiVUYvXnpuPNB20Utk8bYUnYYblX8I0mIip080QtNUQbdZW7gsbXsHN257GT3MEsCskj4xix3vY60hDxjTF6JU6GwXLurH3cCfo/aOmViJ6Ww+g1vErbP65HU0uD59CqYBf/NuN+IEtH4JyYBI92Ff5CRbkTud4pYIG460I5amm0bZPxA3CZEXnOIe2HU+jpGUOqmtWIitFB03UqDKXq/bX7s5GBvW5HKYrSL8AT2MNSpCP28VfY2XQVzEThTXN8PhpUl0B2Bj89AI6Dr8Fh2DG9KkTw/K7CMfe99BBicK4xPFr0NCqhw8+tFT9GAvzLbi3tIn9JI7I5ayNwgzMCJsD5IvBpmkLUUC3kjjTH5/Z68wivASf6zlsKPkMy+3PYnXWdeNT1aRvtezH1Y3VD+eF3QFO+oprq4JiJw7vPQZLziz88+3r0OAN4PzJDUDtSqza4eadrISq6UdX+6dAphnTwib9hFZrvBZunImiZi+kgBfuAy/CZgFaqtayn6h+PsgXg6249cHvcG5Qnf34KFBXRq/Y/Toe/9FTaC/ahC0rZoW6PIwPPTXQShH+tj1ouH4NL0rirZbfi/YT1yGn4G5kCfLdRCNSZi7Fz57JRUtJDRq5Kj3eCjB/rREwCsj6/kOodP4XnGWZaKk9gNZhu9ForVEaqq98od50AwqyJ2uo0qyqlgjox+gVP8OBJ55EHdZg29Pf41Visp6FfjdeavxHlK3O5kVJnDUSP+/E8WHLoifBnHsXrPgU7V3cOyPOEkTJPgXTMm4GTnSgi64mUTglKMmYhrzHSmGDA83uswmqxPgrNujacKsF2dxZJkHin4GrNFuxZZ/+trfUidF7Dm21a7CwzoSyl8swPy3cR+4C/P6/J+gkYrGDBMTPcPClP+LujQ9iJh/pDmKJV8A4dTq+KXhxvPNMhEVRN4cuoIpXJZjvCAQGLj7CksUz6Dx+Dtalc2HWyegc1kLtfE0xISMzg/1ENcX6XRsKZoMbjKoGfdwVpINhVX5cvhMbSo7BUr0Z5XlpikVtfXqKnnfh9NLoTejZLXbD9dybuOb+HwwZvP4P0VB3ZIRN+xNaW30UHtwJwIQTRz5WvPBAhL+rAye4B2bCNTaa52Jp5ruhdxKDLilzsJQr1xOuD/xedGQVY1E69+lVRQy6NqiCOXohU5BX6Va870DS3Z7u2jd6g1syVaPFUoKaCI/MRd8RPFfpxjXDVkhHl56pMSTgP4WmsiLkr/8J8k1XDz06ucaKPfgnujnEEHVoVlNgWVeOu998EuX1HwYXrom+38Pe8BnWb1mAdO33/tDmau2bMR1LtixC6+btcPkuAfKF4bO1aF2/AUtoaKmqZvBthQfbBi8O5Xlj68+PYd4jubzrqJISdG1QCfR4LyZ8H+LwjXzD05Pr+2nJacuS5DpH/bPapfaQza+TqxUj1UYzWgQ31FdqIEjWgY3FA53S/qJZI+jDTfhH0j528QHpfPtbUvXyfg0sNqnere2XVGijX8gb7JdJQsjYFOl8vyh5j24LvkgHsEq2+qNhG/XH7kyIR0560SLgdUhlFqFvnBKWS9W/fkdqP6+tSUMbWox0FsovLLJJ1e6/jnSApuK1rYWmUF+2suFaGORfKA1/+Z3jYVHKZIZVJEAtVIR9maKoxWUAqZhMLVSEfZmiqMVlAKmYTC1UhH2ZoqjFZQCpmByuBR9wqgifRZEACZAACZAACZAACSSGAI3exHBnqSRAAiRAAiRAAiRAAioSoNGrImwWRQIkQAIkQAIkQAIkkBgCNHoTw52lkgAJkAAJkAAJkAAJqEiARq+KsFkUCZAACZAACZAACZBAYgiE7N4gr3LjhwRIgARIgARIgARIgAT0QEC5I9lVygYpE5TxDJMACZAACZAACZAACZCAlgnQvUHL6rHuJEACJEACJEACJEACoyJAo3dUmHgQCZAACZAACZAACZCAlgn8f9Ta7q1glDFjAAAAAElFTkSuQmCC"></p>
<p style="text-align: left;">Pauline wants to visit each town and needs to start and finish in the same town.</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Draw a graph<em> G</em> to represent this floorplan where the rooms are represented by the vertices and an edge represents a door between two rooms.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain why the graph <em>G</em> has an Eulerian trail but not an Eulerian circuit.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain the consequences of having an Eulerian trail but not an Eulerian circuit, for Pauline’s visit to the ground floor of the museum.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down a Hamiltonian cycle for the graph <em>G</em>.</p>
<div class="marks">[2]</div>
<div class="question_part_label">c.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain the consequences of having a Hamiltonian cycle for Pauline’s visit to the ground floor of the museum.</p>
<div class="marks">[1]</div>
<div class="question_part_label">c.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Use the nearest-neighbour algorithm to determine a possible route and an upper bound for the length of her route starting in town Z.</p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>By removing Z, use the deleted vertex algorithm to determine a lower bound for the length of her route.</p>
<div class="marks">[6]</div>
<div class="question_part_label">e.</div>
</div>
<br><hr><br>