Difference between revisions of "Graphs"
(Created page with "=Assignment= Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS). These are tentative, I will probably remove a few aft...") |
(→Assignment) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Assignment= | =Assignment= | ||
Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS). These are tentative, I will probably remove a few after working them out myself. | Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf 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 ( | + | # 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) | + | # 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.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 | + | # 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 | + | # MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph. |
| − | # MCS Problem 12.50 | + | # 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.
