Graphs

Assignment

Problems from Mathematics for Computer Science (MCS). These are tentative, I will probably remove a few after working them out myself.

1. MCS Problem 12.2, but instead of 20, use (first two letters of your last name, add them up, % 10, *2, +10). Kinne: Ki, 10+8, 18, %10 = 8, *2 = 16, +10 = 26. Note: simple graph is unweighted, undirected, no self loops.
2. MCS Problem 12.12 (ungraded). Bipartite: 2 parts.
3. MCS Problem 12.23 and note that Chi(G) is the chromatic number of G - the smallest number of colors that can be used to color the vertices of the graph.
4. MCS Problem 12.25. Connected component - can get from any vertex in the component to any other in the component, and cannot go outside the component.
5. MCS Problem 12.33. Assume we are talking about graphs that are undirected and without self loops.
6. MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph.
7. MCS Problem 12.50. Diameter - largest distance between any two vertices. Note - "degrees of separation", "Erdos number". Note that a tree is a connected graph without any cycles.