DSIIF23BP2sol

pdf

School

University of Massachusetts, Lowell *

*We aren’t endorsed by this school

Course

3220

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by BarristerRoseMouse35

SECOND BIG PROBLEM - SOLUTION DISCRETE STRUCTURES II FALL 2023 For this Big Problem, you will experiment with different graph algorithms. (1) Draw a graph on seven vertices and label the vertices 1 through 7. Answer I decided to draw this graph: (2) Write out the adjacency matrix of your graph. Answer Because there are seven vertices, my adjacency matrix is 7 × 7: 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0

(3) Share your matrix with your partner and use your partner’s matrix draw a copy of your partner’s graph. Check each other’s drawings to make sure you both have it right. Answer I’m pretending my partner gave me this matrix: 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 And so I drew this graph: (4) If either of those two (or both) graphs has an Eulerian path or circuit, give the Eulerian path(s) or circuit(s). Answer Neither graph has an Eulerian path nor circuit. (5) If either of those two (or both) graphs has a Hamiltonian path or circuit, give the Hamiltonian path(s) or circuit(s). Answer My graph doesn’t have a Hamiltonian circuit and neither does my part- ner’s. My graph does have a Hamiltonian path, though! 1-4-5-2-3-6-7 is one example, there are a few more. My partner’s graph doesn’t have a Hamiltonian path. 2

(6) Explain how you checked for Eulerian paths and circuits. Answer Eulerian is easy to check by just looking at the degrees. In my graph, there are four vertices with odd degree (4, 2, 6, and 3), so I know there is no Eulerian path or circuit. Similarly, in my partner’s graph there are four vertices with odd degree (1, 3, 5, 7) so I know there is no Eulerian path or circuit. If there were just two vertices of odd degree, that would have told me there is an Eulerian path. If there were zero vertices of odd degree, that would have told me there is an Eulerian circuit. (7) Explain how your checked for Hamiltonian paths and circuits. Answer There are lots of different possible answers for this question, since there are lots of different possible graphs. This is just an example. Since there are over two million graphs you could have drawn I won’t go through all the possible answers. Since both my graph and my pretend partner’s graph are not Hamiltonian I have to give two explanations. The explanation for my partner is easy; there are no circuits at all in that graph, so in particular there are no Hamiltonian circuits. Furthermore there are three different vertices with just one edge. If any of those vertices were in a path, they would have to be the endpoint. Since a path only has two endpoints, it’s not possible to come up with a path that includes all three of those vertices. Therefore there is no Hamiltonian path, either. The explanation for my graph is more complicated. The problem is with vertex 5 and vertex 1. You can see there are just two edges for both of those vertices so any Hamiltonian circuit passing through those vertices would have to use those two edges. I’ve colored them in this picture so it’s easier to see what I’m talking about. 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

But if you include those edges, it cuts off the rest of the graph. You can see what happens in this picture. 4

There’s no way to make a Hamiltonian circuit without repeating a vertex if you include the red edges, so there is no Hamiltonian circuit. Incidentally, this is why any Hamiltonian path for this graph has to use 1 or 5 as an endpoint! (8) Which do you think is easier to find, Eulerian paths or Hamiltonian paths? Answer This is a personal decision! Sometimes you might think that Hamiltonian is easier; there is more flexibility about which edges you use, which can make things simpler. On the other hand, with Hamiltonian there is no way to know if you just need to look longer to find a path or if there truly isn’t one in the graph. With Eulerian, you can use the degree trick to know for sure whether or not there’s a path before you start looking. It depends on what you like best, really. 5

Related Documents

IT-212-X2249 -4-1 Discussion - Why Is My Internet So Slow.docx

cs1011-unit-1-practice-milestone.pdf

MUSIC_inReport.docx

JOURN_isChart.docx

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

Fundamentals of Information Systems

Computer Science

ISBN:9781305082168

Author:Ralph Stair, George Reynolds

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning