辅导Math 184A、讲解Python，c/c++设计、辅导Java，Python程序、讲解graphs
- 首页 >> OS编程 Math 184A, Winter 2019, Prof. Tesler
Homework #8, Due Wednesday March 6, 2019
Chapter 9# 8, 9, 34, 41
Chapter 10# 2, 10, 26, 34
and the problems below, H-801 and H-802.
Notes:
Problem 9.8: The book’s solution is incomplete; small values of n work differently on some parts.
Drawings of a few of the graphs requested:
1 C2 C6 P5
C S5
Problem 10.26: The length of a walk/trail/path is the number of edges, not the number of vertices.
The two longest paths may or may not be tied for the same length. Assume the tree is finite (the
problem statement left that out).
Problem H-801. In each part below, information about a graph is given. Decide if a graph, without
loops, exists that satisfies the specified conditions or not. Justify your answers.
(a) A simple graph with degree sequence (1, 1, 2, 3, 3, 5) (that is, six vertices, where two vertices have
degree 1, one has degree 2, two have degree 3, and one has degree 5).
(b) A multigraph with degree sequence (1, 2, 2, 3, 3, 5).
(c) A simple graph with degree sequence (1, 2, 2, 3, 3, 5).
(d) A simple graph with degree sequence (3, 3, 3, 3).
(e) A tree with six vertices and six edges.
(f) A tree with three or more vertices, where two vertices have degree 1 and the rest have degrees ≥ 3.
(g) A disconnected simple graph with 10 vertices, 8 edges, and a cycle.
Problem H-802. These problems refer to this graph:
(a) Give an example of an Eulerian trail in this graph (starting/ending at different vertices), and also
an example of an Eulerian cycle. Or if either of these do not exist, prove it.
(b) Give an example of a Hamiltonian path in this graph (starting/ending at different vertices), and
also an example of a Hamiltonian cycle.
(c) Give an example of a spanning tree in this graph.
(d) First, give an example of a path of length 4 in the graph from vertex 1 to vertex 2. Second, give
an example of a walk of length 4 from vertex 1 to vertex 2, such that it’s a walk but is not a path.
Recall that the length of a path or walk is the number of edges in the sequence of edges.
Homework #8, Due Wednesday March 6, 2019
Chapter 9# 8, 9, 34, 41
Chapter 10# 2, 10, 26, 34
and the problems below, H-801 and H-802.
Notes:
Problem 9.8: The book’s solution is incomplete; small values of n work differently on some parts.
Drawings of a few of the graphs requested:
1 C2 C6 P5
C S5
Problem 10.26: The length of a walk/trail/path is the number of edges, not the number of vertices.
The two longest paths may or may not be tied for the same length. Assume the tree is finite (the
problem statement left that out).
Problem H-801. In each part below, information about a graph is given. Decide if a graph, without
loops, exists that satisfies the specified conditions or not. Justify your answers.
(a) A simple graph with degree sequence (1, 1, 2, 3, 3, 5) (that is, six vertices, where two vertices have
degree 1, one has degree 2, two have degree 3, and one has degree 5).
(b) A multigraph with degree sequence (1, 2, 2, 3, 3, 5).
(c) A simple graph with degree sequence (1, 2, 2, 3, 3, 5).
(d) A simple graph with degree sequence (3, 3, 3, 3).
(e) A tree with six vertices and six edges.
(f) A tree with three or more vertices, where two vertices have degree 1 and the rest have degrees ≥ 3.
(g) A disconnected simple graph with 10 vertices, 8 edges, and a cycle.
Problem H-802. These problems refer to this graph:
(a) Give an example of an Eulerian trail in this graph (starting/ending at different vertices), and also
an example of an Eulerian cycle. Or if either of these do not exist, prove it.
(b) Give an example of a Hamiltonian path in this graph (starting/ending at different vertices), and
also an example of a Hamiltonian cycle.
(c) Give an example of a spanning tree in this graph.
(d) First, give an example of a path of length 4 in the graph from vertex 1 to vertex 2. Second, give
an example of a walk of length 4 from vertex 1 to vertex 2, such that it’s a walk but is not a path.
Recall that the length of a path or walk is the number of edges in the sequence of edges.