代做Math 137A Assignment 1代写数据结构程序
- 首页 >> Database作业Math 137A Assignment 1
1. Draw the graph whose vertices are all ternary sequences of length 2 (i.e., ordered pairs where each entry is 0, 1, or 2.) and where two vertices are adjacent if they differ in exactly one entry. Draw this in such a way that all edges are straight line segments. Make the graph as aesthetically pleasing as you can!
2. Recall that a graph is k-regular if every vertex has degree k. A cubic graph is another name for a 3-regular graph.
(a) Draw two different (non-isomorphic) simple cubic graphs on 6 vertices.
(b) Draw all simple cubic graphs on 7 vertices.
(c) Draw all simple cubic disconnected graphs with 8 vertices. Ex-plain why your list is complete.
(d) Let n > 2. Find a construction that takes a simple cubic graphon 2n vertices and modifies it somehow to produce a new simplecubic graph on 2n+ 2 vertices.
3. Prove that the two drawings below are really the same graph. More precisely, find labelings of both graphs with labels {1, 2, . . . , 7} such that ij is an edge in the left graph if and only if ij is an edge in the right graph.
4. For every n, show how to construct a simple graph with degree se-quence (n, n, n − 1, n − 1, . . . , 4, 4, 3, 3, 2, 2, 1, 1).
5. For all n ≥ 4, show how to construct a simple graph on n vertices with degree sequence (n − 1, 3, 3, . . . , 3).
6. If we allow parallel edges and loops, prove that there is a graph with degree sequence (d1, d2, . . . , dn) if and only if di is even.
7. Show that any simple graph with more than one vertex must have at least two vertices with the same degree. Hint: If not, what is the degree sequence?
8. If (d1, d2, . . . , dn) is the degree sequence of a simple graph, then prove
for all 1 ≤ k ≤ n.