Problem Set 2

Graphs

1 Song Order

In this problem, you’ve been hired as a consultant for guitar player extraordinaire - Andy McKee. You’ve been asked to help him figure out the ‘best’ song order for a live gig. Here is some more context:

A guitar has six strings, each of which can be tuned to one of 88 musical pitches1. The strings are typically tuned to specific pitches known as “standard tuning.” However, Andy uses many non-standard tunings, and for this problem, we assume that every song he plays is in a different tuning. See here for an example of Andy tuning his guitar.

Here is an example. In standard tuning, strings 1 through 6 are tuned to the pitches 44, 39, 35, 30, 25, and 20, respectively. Strings 1 through 6 are tuned to 42, 37, 35, 30, 25, and 18 in one altered tuning. To get from standard tuning to this altered tuning, you’d tune the first, second, and sixth strings down by 2 pitches each.

Let \(\mathrm{Tunings}\) be the set of possible guitar tunings. Let \(\mathrm{Songs}\subseteq\mathrm{Tunings}\) be the subset of \(\mathrm{Tunings}\) that Andy would like to play for the show. Let \(S\) be standard tuning and assume \(S \in \mathrm{Songs}\). Andy would like you to find the ordering of songs in \(\mathrm{Songs}\) such that.

  • The guitar starts and ends in standard tuning \(S\).

  • The total amount of shifting required is minimized.

1.1

Model this problem as one of the graph problems we studied in class. In particular, mathematically formalize the definitions of tunings, and fully specify the vertex set, the edge set, and edge weights (if any). Then, explain how a solution to the graph problem corresponds to the optimal song ordering described above.

Hint: define a notion of the cost of moving from tuning \(x\) to tuning \(y\).

Solution

Let \(\mathrm{Tunings}= [88]^6\), i.e., identify each tuning with a 6-tuple \((x_1,...,x_6)\) where \(x_i\) denotes the pitch of each string in a particular tuning.

Let \(V = \mathrm{Songs}\subseteq\mathrm{Tunings}\), and \(E\) be the set of all possible edges between vertices in \(V\). Let \(G = (V, E)\).

We’ll now define a notion of cost for moving between tuning \(x\) and tuning \(y\). We’ll encode this as our weight function \(w: V \to \mathbb{R}\). \[w((x_1,...,x_6), (y_1,...,y_6)) = \sum_{i=1}^6 |x_i - y_i|.\] Note that \(|x_i - y_i|\) is the number of pitches by which we need to tune string \(i\), so the sum over all strings is the total amount we need to tune to move between tuning \((x_1,...,x_6)\) and tuning \((y_1,...,y_6)\).

Then we claim that finding the ordering of songs in \(\mathrm{Songs}\) that starts and ends in standard tuning \(S\) and minimizes the total amount of shifting is given by the solution to the Traveling Salesman Problem on \(G\), starting at vertex \(S\), with weight function \(w\).

Let \(C = (S=s_1,...,s_n=S)\) be the solution to the TSP on \(G\). Since \(C\) is a cycle, we start and end in standard tuning, \(S\). Furthermore, since \(C\) is Hamiltonian, every tuning is found in the cycle (every song is played). Finally, since \(C\) is the Hamiltonian that minimizes the total weight, and we encode the cost of moving from one tuning to the next in the weight function, \(C\) corresponds to the sequence of tunings that minimizes the total amount of shifting.

Note: You can define the edge weights however you want, as long as you justify it!

2 Minimally Connected and Maximally Acyclic

In lecture, we showed two facts about trees.

  1. If \(G\) is a tree, then \(G\) is maximally acyclic.
  2. If \(G\) is a tree, then \(G\) is minimally connected.

In this problem, we will show the converse of these two facts.

2.1

Let \(G\) be a graph. Show that if \(G\) is maximally acyclic, then \(G\) is a tree.

Solution

Let \(G = (V, E)\) be a maximally acyclic graph. We want to show that \(G\) is a tree. Since \(G\) is acyclic by assumption, we just need to show that \(G\) is connected.

Let \(u, v \in V\) be any two vertices. We’ll show that there is a path from \(u\) to \(v\). If \(\{u, v\}\) is an edge in \(G\), then clearly, there is a path from \(u\) to \(v\) (namely the one consisting of just that edge).

Otherwise, \(\{u, v\}\) is not an edge. Since \(G\) is maximally acyclic, adding the edge \(\{u, v\}\) to \(G\) creates a cycle. Since \(G\) was acyclic to begin with, the cycle contains the edge \(\{u, v\}\). Let \(C = (u=u_1, v=u_2,...,u_k=u)\). Then \(P = (u=u_k, u_{k-1},...,u_2 = v)\) is a path from \(u\) to \(v\) in \(G\). Notice in particular that \(P\) does not use the additional edge!

2.2

Let \(G\) be a graph. Show that if \(G\) is minimally connected, then \(G\) is a tree.

Solution

Intuition: If you remove an edge from a cycle, you can still reach any vertex in the cycle from any other vertex in the cycle by going around the other way.

We’ll start by showing that removing any edge from a cycle preserves connectedness..

Suppose \(C = (u_1, u_2,...,u_k=u_1)\) is a cycle, and let \(u_i, u_j\) be any two distinct vertices. Then there are two paths from \(u_i\) to \(u_j\) \((u_i,u_{i+1},...,u_j)\), and \((u_i, u_{i-1},...,u_j)\). Let \(\{u_{\ell}, u_{\ell+1}\}\) be any edge in the cycle, and notice that it is in at most one of the paths. Thus, if it were to be removed, there would still be a path from \(u_i\) to \(u_j\).

Now, let \(G = (V, E)\) be minimally connected. We need to show that \(G\) is also acyclic. By contradiction, assume \(G\) has a cycle \(C = (u=u_1, v=u_2,...,u_k=u)\).

We claim that \(G-\{u,v\}\) (\(G\) with the edge \(\{u, v\}\) removed) is still connected (which is a contradiction, since \(G\) was supposed to be minimally connected).

Let \(x, y\) be any two distinct vertices in \(G\). Since \(G\) is connected, there is a path \(P = (x = x_1,...,x_n=y)\) from \(x\) to \(y\).

If this path doesn’t use the edge \(\{u, v\}\), then we’re done since this path still exists in \(G - \{u, v\}\).

Otherwise, the path includes the edge \(\{u, v\}\), Let \(i\) and \(j\) be the indices where \(P\) ‘enters’ and ‘leaves’ the cycle, that is \(i\) is the smallest index such that \(x_i \in C\), \(j\) is the largest index such that \(x_j \in C\). According to the earlier claim, there is still a path from \(x_i\) to \(x_j\). Furthermore, this path uses only vertices in \(C\) and therefore doesn’t intersect with the path from \(x\) to \(x_i\) or the path from \(x_j\) to \(y\).

3 Model a Problem

3.1

Model a real-world problem (not already seen in tutorial/lecture/hw) as one of the graph problems that we studied!

  • Describe the real-world problem

  • Define a graph

  • Explain how solving one of the problems we studied on that graph corresponds to a solution for the original problem.

Please submit your solution here to be shared with the class. I may even use one of your examples in a future exam.

4 Pokémon

In your town, a new set of young pokémon trainers are about to embark on a journey to become the very best (like no one ever was). Throughout the year, each prospective trainer has spent time with a few pokémon in the town, and the local professor has carefully noted their compatibility with each pokémon.

You are in charge of assigning each prospective trainer a starter pokémon and would like to maximize the total compatibility. Note that each trainer gets at most one Pokémon.

4.1

Model the problem of assigning starter pokémon to the cohort of pokémon trainers as one of the problems we studied in class. Fully define the graph, the problem you’re solving on the graph, and why a solution to the problem is the best assignment.

Solution

Define the graph \(G = (V, E)\) as follows. Let \(T\) be the set of prospective trainers and \(P\) be the set of starter Pokémon.

  • \(V = T \cup P\).

  • \(E = \{\{a, b\}: a \in T, b \in P\}\)

For each edge, \(\{a, b\}\), define the weight \(w(\{a, b\})\) to be the compatibility between \(a\) and \(b\) as observed/estimated by the professor. We want to find the matching in \(G\) that maximizes the total weight.

Let \(M \subseteq E\) be a matching that maximizes the total weight in \(G\). We can extract the assignment of Pokémon to trainers by taking the edges from \(M\). I.e., if \(\{a, b\} \in M\), then \(a\) and \(b\) will be assigned to be together. Note that since \(M\) is a matching, each trainer/pokemon will have at most one assignment, and since every edge is between a trainer and a pokemon, every assignment will contain one trainer and one pokemon. Furthermore, since weights in \(G\) correspond to compatibility, the matching of the highest weight corresponds to the assignment with the maximum total compatibility.

4.2

The remainder of this problem will be here.

Footnotes

  1. In reality, the set of possible pitches for each string is way smaller, but this assumption is OK for this problem since we restrict our attention to only the tunings that Andy uses.↩︎