Assignment
1. [20 points] Given a pos!ve number k, let n ≥ max(k(k + 1), 3). Now place n points on a circle, let Gn, k be the graph obtained by joining each point to the k nearest points in each direc!on on the circle. Observe that Gn, k is a 2k-regular graph (each vertex has the same degree = 2k).
Example:
Compute the chroma!c number χ(k,n) for 1 ≤ k ≤ 5 and k(k + 1) ≤ n ≤ 2k(k + 1). [For k = 1, consider
3 ≤ n ≤ 4.] You must formulate your model as an LP, explain the variables, constraints, objec!ve func!on and then execute your code to get the results. Jus!fy your model and interpret your results.
Output your results in a form of a table (χ for each (k,n)). Based on the data, guess a formula for χ.
Bonus Try proving your guess.
2. [20 points] A well known result in Graph Coloring is the four-color theorem
It states that given any map in a plane, we can color the map using four colors in such a way that regions sharing a
. common boundary (other than a single point) do not have the same color.
Note that the requirement is that regions that share a boundary of length larger than 0 (that the boundary is not a point) must be of different colors (Utah and Arizona). In other words if Region R and Region S have just a point as their common boundary (Utah and New Mexico), then you may color them with same color.
Moreover, the map must not have holes (for example if there are waterbodies, then we must regard them as regions on their own right and color them as well).
For the assignment you must find a real world map and solve the coloring problem with minimum number of colors. You can do this by crea!ng a graph where ver!ces represents the regions and edges represent boundaries (other than point boundaries), and vertex color the graph. Formulate your problem as a linear programming model, giving jus!fica!on for the variables, constraints and object func!on. Solve the LP (this means solve it by programming) and interpret the result. Show your work by including pictures of the coloring of your map.
You can use regions as long as they are not countries or US states. The regions could be coun!es, provinces or some other subdivisions. You must have at least 25 regions in the largest connected component of your graph (in case your graph turns out to be disconnected).
You must consider a map (not a graph directly), convert the map to a graph and then solve the coloring problem.
Here you can find some maps that you may consider link
Submission Guideline Please upload a pdf file in the form of a report with your model, jus!fica!on and all your code and results. Include pictures of maps you consider. Upload your code/notebook as well.
0 comments