Suppose you are a DJ and you have a collection of n songs you want to play. You
ID: 3832931 • Letter: S
Question
Suppose you are a DJ and you have a collection of n songs you want to play. You are very picky about how to order your songs so that they sound good. You will only play song B after song A if song A ends on the same note that song B begins with.
You wish to play all n songs in your collection. A solution to this problem is a list of all the songs in your collection such that each song starts on the note that the previous song ended on.
(a) Describe how to model this problem with a graph so that finding a solution to the problem corresponds to finding a Hamiltonian path in the graph.
descrption: define a (directed/undirected) graph as follows. Let the vertices be ____... Place an edge from vertex v to vertex w if____..... When we set up the graph like this, each Hamiltonian path corresponds to a solution because___...
(b) Describe how to model this problem with a graph so that finding a solution to the problem crresponds to finding an eulerian path in the graph.
Description: Define a (directed/undirected) graph as follows. let the vertices be___...
Place an edge from vertex v to vertex w if____.....
When we set up the graph like this, each eulerian path corresponds to a solution because_____.....
Explanation / Answer
a)
Define a Directed graph as follows. Let the vertices be Songs .
Place an edge from vertex v to vertex w if song v ends on the same note that song w begins with.
When we set up the graph like this, each Hamiltonian path corresponds to a solution because
in a Hamiltonian path,we will visit all the vertices exactly once.Hence, a Hamiltonian path
will ensure that all the songs will be played.
b)
Define a Directed graph as follows. Let the vertices be Songs .
Place an edge from vertex v to vertex w if song v ends on the same note that song w begins with.
When we set up the graph like this, each eulerian path corresponds to a solution because
in a eulerian path,we will visit all the edges exactly once and all vertices atleast once.
Hence, a eulerian path will ensure that all the songs will be played.