 |
| A 7-regular graph with 10 vertices: every vertex connects to 7 others. |
As I do the exercises I may outline some of the less obvious ones, if there isn't already a convenient reference on the web. Here's one.
The first chapter is on graphs, and exercise 2-3 asks you to take a graph with n vertices and no edges, and make it k-regular (regular to a given degree), if possible. In prior exercises, you've derived a Graph class from dict and added methods to interact with it. To make the whole thing more fun, Downey provides a library so you can easily draw graphs, as shown in the illustration above.
The "if possible" part is clear from Wikipedia: you can make a graph with n vertices k-regular if n>=k+1 and n*k is even. Also, if k is 0, no edges need to be added; a graph with n vertices and no edges is already 0-regular.
What distracted me for a while is that for most values of n, there are multiple solutions that are k-regular, as catalogued here. But eventually a thread on StackExchange gave me the hint that I should focus on a solution where the vertices are arranged in a circle and the resulting pattern of edges appears radially symmetrical (as in the illustration above).
More specifically, starting from a graph that meets the criteria above:
- Place the vertices in a "circle". That is, a data structure that lets you start from any vertex and move in either direction to every other vertex, in a fixed order, until you return to the vertex you started from.
- Starting with some vertex, for each vertex around the circle:
- If k is even, add edges to the next k/2 vertices in both directions on the circle.
- If k is odd, add edges to the next (k-1)/2 vertices in both directions around the circle, and then create an edge to the vertex that is "opposite" on the circle.
Note that in our Graph class, adding an edge between two vertices that are already connected doesn't create another edge (otherwise we'd no longer have a simple graph).
To make the "circle" in Python, I put the vertices in a list, which has indices 0 to n-1, and looped over the list of vertices. Where needed I added code to "wrap" the list. For example, if you are at vertex n-1 and are adding an edge to vertex n+1, subtract n to get to index 1 instead.
To get to the "opposite" vertex in the circle, add n/2 to the current index (which may require wrapping). This works because if k is odd, n must be even for a regular graph to be possible in the first place.
To make the "circle" in Python, I put the vertices in a list, which has indices 0 to n-1, and looped over the list of vertices. Where needed I added code to "wrap" the list. For example, if you are at vertex n-1 and are adding an edge to vertex n+1, subtract n to get to index 1 instead.
To get to the "opposite" vertex in the circle, add n/2 to the current index (which may require wrapping). This works because if k is odd, n must be even for a regular graph to be possible in the first place.
I won't post code, because that would be cheating, but this should be enough to solve it. To test it, it helps to create a method Graph.is_regular(). Then you can loop over combinations of n and k, make a regular graph for each combination, and test it, alerting you to any that failed.
