draw a tree 10 vertices total degree 24
Notes on Problems for Quiz 8 (11/21/97) from Epp:
11.1 : 1-9, 22, 24, 27, 30
11.2 : 2, 4, 7, 9, 24, 29, 37, 39
11.3 : 3, 5, 20
11.4 : 1-5
11.5 : 15-19, 43-51
11.6: 1-10
Problem 11.1(1):
(1) A graph, in the sense of Chapter 11, consists of three things: a set of vertices V, as set of edges E, and a function f that assigns to each edge either a set of two vertices or a single vertex. ANY WAY you specify these three ingredients is a correct specification of a graph. The graph is sometimes written as a triple G = (V, E, f). One common way to specify a graph is with a picture, as in this exercise (page 616). Another way is shown in the solution to this exercise on page 788. For this graph, V={v_1, v_2, v_3}, E={e_1,e_2,e_3}, and f can be specified explicitly: f(e_1)={v_1,v_2}, f(e_2)={v_1,v_2}, and f(e_3)={v_3}.
(2) If, instead of f(e) being a set of two vertices, such as {x,y}, we make f(e) an ordered pair of vertices, (x,y), then the graph G=(V,E,f) is called a directed graph (see top of page 607 for a definition). Graphs and directed graphs occur everywhere in computer science. Here is some code extracted from a computer-science application of directed graphs:
Do you understand what is going on here?
Problem 11.1(2)
(1) G=(V,E,f) where V={v_1,v_2,v_3,v_4}, E={e_1,e_2,e_3,e_4,e_5}, f(e_1)={v_1,v_2}, f(e_2)={v_2,v_3}, f(e_3)={v_2,v_3}, f(e_4)={v_2,v_4}, f(e_5)={v_4}. Note that f(e_2)=f(e_3), although e_3 and e_2 are different elements of E.
Problem 11.1(3)
(1) One way is shown on page 788. v_4 and v_5 are "isolated vertices."
Problem 11.1(4)
(1) Here are two if infinitely many ways:
Problem 11.1(5)
(1) There is an important point that is not quite correct in the way this exercise is stated. You are asked to "... show that the two drawings represent the same graph by labeling the vertices and edges of the right-hand drawing to correspond to those of the left-hand drawing." Remember, to specify a graph G=(V,E,f), you must specify all three of the essential components (V, E, and f) in the definition of a graph. As it stands, the right-hand drawing doesn't specify any of these three components, let alone all of them! It is thus wrong to say that these two drawing represent the same graph. The left-hand drawing represents a graph, but the right hand drawing doesn't. What the author means to say is "... show that it is possible to label the edges and vertices of the right-hand drawing so that, when you are done, you have given a pictorial representation of exactly the same graph in the right-hand drawing as that in the left."
(2) Here is another graph that has the property that it can be represented by labeling the "unlabeled graph" on the right-hand side in this exercise. When two graphs can be represented by putting labels on the same unlabeled graph they are called "isomorphic." See pages 656-664. The graph below and the graph represented by the left-hand drawing of Exercise 11.1(5) are, therefore, isomorphic.
Problem 11.1(6)
(1) Label the vertices of the right-hand drawing v_1, v_3, v_2, v_4 clockwise starting at any vertex (or counterclockwise starting at any vertex). The edge labels are then forced. If you label with v_1, v_2, v_3, v_4 clockwise or counterclockwise you will not make a drawing that represents the same graph as the left-hand side.
Problem 11.1(7)
(1) The degree of a vertex k in a graph is the number of non-loop edges s with k an element of f(s) plus two times the number of loop-edges t with k an element of f(t). For the graph shown above, in the discussion of problem 9.1(5), the vertex d has degree 3 (d is in f(s) for s=x, v, and w). The degrees in the unlabeled graph on the right-hand side must correspond to the degrees in the graph on the left-hand side after you have done the labeling of the right-hand side. Thus, the one vertex of degree 4 on the right-hand side must be labeled with the vertex v_6 of degree 4 on the left-hand side. The list of degrees of this graph are (4,3,3,2,2,2,2). This is the list of degrees of any graph isomorphic to the graph of this exercise. This list can be helpful in larger examples of isomorphic graphs.
Problem 11.1(8)
(1) See page 789.
Problem 11.1(9)
(1) For (i), e_1, e_2 ; for (ii) v_1, v_2; for (iii) e_2, e_7; for (iv) e_1, e_3; for (v) e_4 and e_5 are parallel; for (vi) v_4 is the only isolated vertex; for (vii) deg(v_3)=2; for (viii) 12.
Problem 11.1(29)
(1) Each edge contributes exactly 2 to the sum of all the degrees of all the vertices. Thus, in this case, the sum is 16 so the number of edges is 16/2 = 8.
Problem 11.1(37)
(1) If a graph contains a simple circuit of odd length then it is not bipartite. If a graph has no circuits then it is bipartite. If a graph contains only circuits of even length it may or may not be bipartite, further checking is necessary. For this problem (a) is bipartite, (b) has a simple circuit of length 3 so is not bipartite, (c) has no circuits so it is bipartite, (d) has a simple circuit of length three so is not bipartite, (e) is bipartite, (f) is not as it is a simple circuit of length 5.
Problem 11.1(39)
(1) For (a) see page 791. For (b) V is the same, E={{v_1, v_3}, {v_3, v_4}}. Note that for simple graphs (no parallel edges or loops) the names of the edges are often just taken to be the set of pairs of vertices incident on that edge. Thus instead of saying "The edge e ..." we say "The edge {v_1, v_2}..." .
Problem 11.2(2)
(1) The definition of walk, path, simple path, closed walk, circuit, simple circuit on page 621 should be understood for this and the other problems of this section. A "circuit" is also called a "cycle." (a) just a walk because e_2 is repeated twice; (b) simple circuit (or cycle) Note here that there are now parallel edges so the use of the symbols representing the edges in a walk is redundant. (c) closed walk - it starts and ends at v_4, but repeats the edge e_5 twice. (d) circuit; (e) path but not a simple path (f) simple path.
(2) Note also 11.2(3). No to both (a) and (b). For (b), the start vertex of the closed walk isn't specified.
Problem 11.2(4)
(1) See page 791.
(2) Note the related problem 11.2(5). Suppose there were five edges instead of four? What would be the forumla for n edges?
Problem 11.2(7)
(1) For (a) try a simple path with n edges (n+1 vertices). For (b) a simple circuit with n edges (n vertices) will suffice. An edge that disconnects a graph is called an "isthmus."
Problem 11.2(9)
(1) For (a), see page 792. Note that this graph does have an Euler path by Corollary 11.2.5 on page 631. For (b), yes - the graph is connected and all vertices have even degree. For (c), not necessarily (if the graph isn't connected). You should make sure that it is possible to have graph which is not connected and has vertices of degrees 2,2,4,4,6. Can you find such a graph without loops? Without loops or parallel edges?
Problem 11.2(24)
(1) Finding Hamiltonian circuits in general is hard. It is also hard to make up an example where it is hard to find a Hamiltonian circuit (seems contradictory!). This exercise is easy and falls victum to a simple trick for piecing together two circuits that contain every edge of a graph:
Problem 11.2(29)
(1) First it helps to look at 11.2(25, 26, 27). For 11.2(25) note that the vertex c is a "articulation vertex" (so called) in that removing it, and all edges adjacent to it, disconnects the graph. A Hamiltonian graph does not have such a vertex since the graph is a single simple circuit, plus extra edges joining vertices on this circuit. Forget about these extra edges and note that removing a single vertex of the circuit still leaves the circuit connected (it becomes a simple path). For 11.2(26) note that a vertex of degree two (such as a, c, d, g here) must have both of its incident edges on any Hamiltonian circuit. Thus the path j a b c d g h must be a part of any Hamiltonian circuit. To complete the Hamiltonian circuit you must construct a path from j to h using vertices i, f, and e. This path cannot use any edges with a vertex on j a b c d g h . It is easy to see that this is impossible. For 11.2(27) note that B is an articulation vertex. Let's apply these ideas to 11.2(28, 29, 30, 31). For 28, there is no Hamiltonian circuit, applying the vertex-of-degree-two trick (in particular, apply it to d and c). For 29 (the assigned problem) there is a Hamiltonian circuit. For 30, there is a Hamiltonian circuit (apply the trick of 11.2(24) above to the edges {v_1, v_2} and {v_5, v_6}. For 31, use the vertex-of-degree-two trick (in particular, apply it to d and b).
Problem 11.2(37)
(1) For (a) see page 792. Note that (b) is the contrapositive of (a) and is thus logically equivalent to (a).
Problem 11.2(39)
(1) If v_1 e_1 v_2 e_2 ... v_i e_i v_{i-1} ... v_n e_n v_{n+1} is a circuit then
v_{i-1} ... v_n e_n v_1 e_1 v_2 e_2 ... v_i is a path, using the fact that v_1=v_{n+1}.
Problem 11.3(3)
(1) Part (a) is on page 793. One representation of part (b) is as follows:
Problem 11.3(5)
(1) Part (a) is on page 793. The graph of part (b) is isomorphic to a subgraph of the graph of part (a) (shown on page 793). Can you find the isomorphism in the sense of the definition on page 657?
Problem 11.3(20)
(1) You should draw the graph first. Then compute A^2 and A^3. Check your answers to parts a, b, and c directly from the graph. Here is what we get for A^2 and A^3.
| 2 | 2 | 2 | 2 |
| 2 | 6 | 2 | 3 |
| 2 | 2 | 6 | 3 |
| 2 | 3 | 3 | 3 |
| 4 | 8 | 8 | 6 |
| 8 | 9 | 17 | 11 |
| 8 | 17 | 9 | 11 |
| 6 | 11 | 11 | 9 |
It is helpful here to note that the powers of symmetric matrices are symmetric. That cuts down the computation a bit (compute A^2(1,4) and you have A^2(4,1) for free).
Problem 11.4(1)
(1) They are isomorphic:
| v_1 | v_2 | v_3 | v_4 | e_1 | e_2 | e_3 | e_4 |
| w_4 | w_3 | w_2 | w_1 | f_4 | f_3 | f_1 (f_2) | f_2 (f_1) |
Problem 11.4(2)
(1) Not isomorphic. The degree sequences aren't the same.
Problem 11.4(3)
(1) Isomorphic. To get the isomorphism, note that the simple circuits v_1 v_2 v_3 and w_3 w_1 w_w_2 must correspond in that order of vertices.
Problem 11.4(4)
(1) Not isomorphic. Degree sequences don't correspond.
Problem 11.4(5)
(1) No. Degree sequences again...
Problem 11.5(15)
(1) V={1,2,3,4,5,6,7}, E={{1,2}, {3,4}, {5,6}, {5,7}}. You can draw the picture!
Problem 11.5(16)
(1) A tree with 12 vertices and 15 edges doesn't exist. A tree always has |V| = |E| + 1.
Problem 11.5(17)
(1) Take G to be a simple circuit with 5 vertices and 5 edges together with a 6th isolated vertex.
Problem 11.5(18)
(1) A tree with five vertices and total degree 10 doesn't exist. Total degree 10 means there are 10/2 = 5 edges. A tree always has |V| = |E| + 1.
Problem 11.5(19)
(1) HINT: How many vertices and edges does a spanning tree have for this graph?
Problem 11.5(43)
(1) No such graph. A full binary tree has one more terminal than internal vertex (not one less).
Problem 11.5(44)
(1) A binary tree of height 4 where each vertex, except the one of height 4 (the one terminal vertex) has exactly one terminal vertex. You can add terminal vertices one at a time, keeping the height constant, until you get to 16 terminal vertices (the full binary tree of height 4). Thus, along the way, you hit one with eight terminal vertices. The answer to this problem is that such a graph exists. You should draw one.
Problem 11.5(45)
(1) Such a graph exists. Start with a simple path 1,2,3,4. Add edges {3,5}, {2,6}, {1,7}, and take the vertex 1 to be the root. Let 2, 3, and 4 be left sons and 5, 6, and 7 right sons. Draw this graph.
Problem 11.5(46)
(1) If i is the number of internal vertices then i+1 is the number of terminal vertices (true for any full binary tree). The total number of vertices is 2i+1, an odd number. 9+5=14 is even.
Problem 11.5(47)
(1) Yes. Draw one!
Problem 11.5(48)
(1) The most number of terminal vertices in any binary tree is 2^h, where h is the height. If the height is 4, then 16 is the maximum number of terminal vertices. Draw this full binary tree.
Problem 11.5(49)
(1) The number of vertices in full binary tree is always odd. See 11.5(46).
Problem 11.5(50)
(1) Yes. Take the full binary tree of height 3 and 2^3=8 terminal vertices. Remove a pair of terminal vertices that are the left and right child of the same internal vertex.
Problem 11.5(51)
(1) If t is the number of terminal vertices then h >= lg(t) for any binary tree. If the binary tree is full then h <= t-1. This problem doesn't require that the binary tree be full, so all we can say is that h >= lg(25) so h > 4 (or h >= 5) for part (a). For (b), h > 5. For (c), h >5.
Problem 11.6(4)
(1) There are four ways to break the outer circuit v_0, v_1, v_2, v_3 by removing an edge. All four of the resulting graphs are isomorphic and consist of a simple circuit of length three with a pendant edge attached to one vertex of the circuit. There are three ways to break this circuit, leaving at total of 4 + 3 = 7 spanning trees. You should list all seven.
Problem 11.6(6)
(1) Since all of the edges have a different label, we refer to the edges by their labels. The order in which the tree edges are added by Kruskal's algorithm are: 2, 4, 5, 8, 10, 13, 19. The total weight is 61.
Problem 11.6(8)
(1) Using Prim's algorithm we would add edges in the order 2, 5, 10, 4, 8, 13, 19, again total 61.
Problem 11.6(10)
(1) Referring to an edge such as {t,u} as simply tu, Kruskal's algorithm (part (a)) requires that we add the edges as follows: yu (yx and uv in either order) tz (xw or vw) (tu or zy). There are a total of eight minimal spanning trees using Kruskal's algorithm. Using Prim's algorithm (part (b)) requires: yu (yx and uv in either order) (xu or vw) (tu or zy) tz. Again eight.
logananobaciping01.blogspot.com
Source: https://cseweb.ucsd.edu/classes/fa97/cse21/q8notes.html
0 Response to "draw a tree 10 vertices total degree 24"
Post a Comment