Transcribed TextTranscribed Text

Problem Set: Graph Theory In this problem set we investigate some concepts in graph theory. The problems are of varying difficulty; not all will be equally weighted in the grading. Problem 0. Properties of Graphs. Use the Lab page Graph Properties to learn or to remind yourself of the definitions of the diameter of a graph, of complete, cycle, grid, path, star and wheel graphs, and of the conditions under which a graph is connected, regular, planar and/or bipartite. When you want to return to this page, use the Back option of your browser, not the Previous button given on Graph Properties. The list below gives a number of true statements (Facts; these you don’t have to prove), and asks some questions. Please answer each question. Fact 1: All complete graphs, cycle graphs, grid graphs, path graphs, star graphs and wheel graphs are connected. Fact 2: All cycle graphs, grid graphs, path graphs, star graphs and wheel graphs are planar. Question: Is a complete graph Kn ever planar? If yes, for what n is Kn planar? Answer: Fact 3: All complete graphs and cycle graphs are regular, but only two star graphs, and only one wheel graph, are regular. Question: Can you identify these special wheel graphs and star graphs? Which grid graphs are regular? Answer: 1Fact 4: The diameter of a complete graph is always 1. Question: What is the diameter of a path graph Pn? And that of a cycle graph Cn? Or a grid graph Gm,n? The answer should be given in terms of any n and m. Answer: Question: Show that the diameter of a star graph Sn for n > 2 or a wheel graph Wn for n > 4 is always 2. Answer: Fact 5: All grid graphs, path graphs, and star graphs are bipartite. Question: Can you identify the two special sets of vertices in each of these cases? Answer: 2Question: Which cycle graphs are bipartite? And which complete graphs? Wheel graphs? Answer: Problem 1. Directed and Undirected Graphs. Draw a directed graph G, and label two vertices x and y in such a way that the distance from x to y is 7 in the directed graph G, but so that the distance from x to y would be 2 if we made an undirected graph H by erasing directions on the edges of G. Answer: Problem 2. Sum of Degrees. a) Draw three small graphs (4-10 edges each) and, for each vertex, write the degree next to the vertex. Answer: 3b) For each of the three graphs in part (a), add up the degrees of the vertices in that graph. Note that the sum for each graph is even. Answer: c) Explain why for any graph, the sum of the degrees of the vertices is always even. Answer: Problem 3. Trees. a) Draw three small (8-15 vertices) trees. Answer: 4b) For each of the three trees in part (a), count the number of vertices, V , and the number of edges, E. Note that V − E = 1 for each tree. Answer: c) Explain why for any tree, V − E must always equal 1. Answer: 5Problem 4. The Chinese Postman Problem. In class, we briefly touched on a simplified version of the Chinese Postman Problem, a close cousin of the Koenigsberg bridge problem that was studied by the Chinese mathematician Meigu Guan in the 1960s. We will now explore the original Chinese Postman Problem. On his first day on the job, a new postman is given the map below and instructed that he must deliver letters to houses along each of the streets on the map. The postman wants to find the shortest possible route that includes each of the streets on the map at least once and returns him to his starting point at the post office (the intersection in the upper lefthand corner). a) Draw the graph corresponding to the given map. Vertices in your graph will represent intersections and edges will represent the streets that connect pairs of intersections. Answer: 6b) Add a weight to each edge (in the graph you drew above) to represent the length of the corresponding street. Answer: c) Since the postman must travel each street at least once and return to his starting point, an Eulerian cycle, if it exists, will be the shortest possible route. Is it possible to find such a cycle for this graph? Use the result of Euler discussed in class to explain why or why not. Answer: d) Add a new edge parallel to an existing edge (that is, connecting the same two vertices as an existing edge) in such a way that you make an Eulerian cycle possible. Verify that you can now find an Eulerian cycle in the graph. Answer: 7e) How would the postman actually travel the route represented by your Eulerian cycle? In particular, since the postman can’t build new streets, how does he travel your new edge? Answer: f) In view of your answer to (e), what should the weight of your new edge be? Answer: g) Find the total distance the postman needs to travel to complete the route represented by your new Eulerian cycle. Is this route the shortest route that satisfies the postman’s constraints? If yes, explain why. If not, find a shorter route. Answer: 8h) Now consider the following example: How many ways are there to add 2 parallel edges to this graph so as to make an Eulerian cycle possible? Which way creates the shortest possible Eulerian cycle? Answer: i) Using what you’ve learned, explain how in general a postman can find the shortest route that includes each street at least once and ends at his starting point. Answer:

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

    By purchasing this solution you'll be able to access the following files:

    for this solution

    or FREE if you
    register a new account!

    PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

    Find A Tutor

    View available Mathematics - Other Tutors

    Get College Homework Help.

    Are you sure you don't want to upload any files?

    Fast tutor response requires as much info as possible.

    Upload a file
    Continue without uploading

    We couldn't find that subject.
    Please select the best match from the list below.

    We'll send you an email right away. If it's not in your inbox, check your spam folder.

    • 1
    • 2
    • 3
    Live Chats