Due Friday, November 4, in Gradescope.
Find a graph that has an Euler tour (it is connected and all degrees are even) in which there exists a path \(uvw\) whose edges cannot be used consecutively as part of an Euler tour. (Hint: If it appears consecutively, it can appear at the start of the tour. Use Fleury's algorithm to show that, in your graph, using this path at the start of a tour would be a mistake.)
Let \(S\) be a set of integers, represented as a binary number as in the course lecture notes. Suppose we want to construct the set \(T\) of integers \(i\) for which both \(i\) and \(i+1\) belong to \(S\). For instance, when \(S=\{1,2,3,6,8,9\}\), we should construct \(T=\{1,2,8\}\). Write the simplest expression you can find for \(T\). Use programming notation, not mathematical set notation.
Define the width of a walk (just like the width of a path) to be the minimum weight of any of its edges. Define a "widest traveling salesperson tour" to be a walk through a graph, starting and ending at the same vertex and visiting every vertex, that has the largest possible width.
163 students only: For the four-vertex graph used as an example for the exact TSP algorithm, find a widest traveling salesperson tour. (Hint: Remember that walks are allowed to repeat vertices. The optimal solution is not one of the three tours used in the example.)
265 students only: Describe a polynomial-time algorithm for finding the widest traveling salesperson tour. (Hint: it is the same as one of the other TSP-related algorithms we studied.)
In the \(G(n,\tfrac12)\) model of random graphs, every graph on a given set of \(n\) vertices is equally likely, and therefore every graph is possible. Find a graph with four vertices that cannot be generated by the Barabasi–Albert model, no matter what parameter \(d\) is used.