Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAST30011 Graph Theory Assignment 1 Student Name Student Number Tutor’s Name Practical Class Day/Time Submit your assignment online in Canvas LMS. Please attach this cover sheet to your assignment or use a blank sheet of paper as the first page of your assignment with Student Name, Student Number, Tutor’s Name, Practical Class Day/Time clearly stated. • Late submission will not be accepted unless accompanied by a medical certificate (or a similar special consideration). If there are extenuating circumstances you need to contact your lecturer, preferably prior to the submission deadline. Medical certificates are usually required. • Information on how to submit assignments can be found in the Canvas LMS. • Full working must be shown in your solutions. • Marks will be deducted for incomplete working, insufficient justification or incorrect use of terminology. • There are 6 questions (on two pages) worth 40 marks in total. • This assignment will contribute 10% to your final mark. MAST30011 Graph Theory 2022 ASSIGNMENT 1 Due 13:00pm Thursday 14 April 2022 1. In the following graph, [8 marks] (a) give an example of a longest trail (b) give an example of a longest cycle (c) give an example of a longest path (d) list all induced subgraphs which are paths of length 4 (e) list all bridges of the graph (f) compute the eccentricities of a, b, c, d, respectively (g) give the diameter of the graph (h) give an automorphism of the graph which is not the identity map from the vertex set to itself. w a b c d u v Figure 1: Question 1 2. Let T be a tree with order n ≥ 8 in which every non-leaf vertex has degree 7. Prove that n ≡ 2 mod 6 (that is, there exists an integer k such that n = 6k + 2). Prove further that the number of leaves of T is strictly greater than 5n 6 . [6 marks] 3. Prove that a nontrivial graph is a tree if and only if it has exactly one spanning tree. [6 marks] 4. Let G be the following weighted graph, where the number next to each edge is the weight of the edge. Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G. State what the labels of vertices are when each new vertex is chosen to be added to the set S. Draw the tree of shortest paths obtained from your implementation of the algorithm, and explicitly give the shortest path from a to every other vertex obtained from this tree. [6 marks]