Difference between revisions of "Graphs"
(→Assignment) |
(→Assignment) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 5: | Line 5: | ||
# 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. | # 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. | ||
# 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. | # 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. | ||
| − | # MCS Problem 12.33 | + | # MCS Problem 12.33. Assume we are talking about graphs that are undirected and without self loops. |
# MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph. | # MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph. | ||
| − | # MCS Problem 12.50. Diameter - largest distance between any two vertices. Note - "degrees of separation", "Erdos number". | + | # 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. |
Latest revision as of 02:48, 18 November 2022
Assignment
Problems from Mathematics for Computer Science (MCS). These are tentative, I will probably remove a few after working them out myself.
- 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.
- MCS Problem 12.12 (ungraded). Bipartite: 2 parts.
- 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.
- 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.
- MCS Problem 12.33. Assume we are talking about graphs that are undirected and without self loops.
- MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph.
- 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.
