Hey guys just working on a discrete math graph theory problem. Unsure of how to
ID: 3198165 • Letter: H
Question
Hey guys just working on a discrete math graph theory problem. Unsure of how to proceed here. Uploading a picture of the graph, the bottom part of the question states, "She would also like to return to her starting point. What route should she follow if she does not wish to visit any city more than once?
A saleswoman wishes to visit all the "cities" on the map below: ? ? e would also like to return to her starting point. What route should she follow if she does not w sit any city more than once? (Hint: consider vertices of degree 2).Explanation / Answer
As it is mentioned the problem that the saleswoman does not wish to visit any city more than once, the path we are going to choose should contain each city only once. This is the first constraint.
So I considered E as the starting point randomly. Then as the degree of E is 2 the path can go through A or I (From the figure in problem).
If I choose A as the next point to E then the last point should be I or if I choose I as the next point then the last point will be A in her path because then only she can return to the starting point successfully. This is the second constraint.
Here as we have chosen the point with degree 2 there is one possibility for the ending point. If we choose point with degree 3 then there will be two possibilities for ending point which may increase the complexity.
Now one of the paths followed by the saleswoman is given as E --> A --> F --> K --> G --> D --> J --> B --> L --> C ---> H --> I --> E
Again you can try with any other point with degree 2 to get another path.