Introduction to Graph Theory West 2e solutions 图论导引 第二版 West 答案

好东西不多说了 图论导引 英文版 第二版 West 答案
Solutions Preface Comments just to state the result and give an example (the next edition will include There are several underlying themes in the course, and mentioning a purely inductive proof that uses only determinant expansion, not the these at appropriate moments helps establish continuity. These include CauchyBinet Formula). Students find the material on graceful labelings 1) TONCAS (The Obvious Necessary Condition(s) are Also Sufficient) enjoyable and illuminating; it doesnt take long, but also it isnt required 2)Weak duality in dual maximation and minimization problems The material on branchings should certaily be skipped in this course 3)Proof techniques such as the use of extremality, the paradigm for induc 2.3: Many students have seen rooted trees in computer science and tive proofs of conditional statements, and the technique of transforming a find ordinary trees unnatural; Kruskal's algorithm should clarify the dis problem into a previously solved problem tinction. Many CS courses now cover the algorithms of Kruskal, Dijkstra, Students sometimes find it strange that so many exercises concern and Huffman; here cover Kruskal and perhaps Dijkstra(many students the Petersen graph. This is not so much because of the importance of the have seen the algorithm but not a proof of correctness), and skip huffman Petersen graph itself, but rather because it is a small graph and yet has complex enough structure to permit many interesting exercises to be asked. Chapter 3 3.1: Skip "Dominating Sets, but present the rest of the section Chapter 1. In recent yo ears,most students enter the course having 3.2: Students find the hungarian algorithm difficult; explicit examples been exposed to proof techniques, so reviewing these in the first five sec need to be worked along with the theoretical discussion of the equality tions has become less necessary; remarks in class can emphasis techniques subgraph. " Stable Matchings"is very popular with students and should be as reminders. To minimize confusion, digraphs should not be mentioned presented unless far behind in schedule. Skip"Faster Bipartite Matching until section 1.4; students absorb the additional model more easily after 3. 3: Present all of the subsection on tutte s 1factor theorem The becoming comfortable with the first material on ffactors is intellectually beautiful and leads to one proof of 1.1: p36 contain motivational examples as an overview of the course the ErdosGallai conditions, but it is not used again in the course and is an this discussion should not extend past the first day no matter where it aside". Skip everything on Edmonds'Blossom algorithm: matching algo ends (the dcfinitions are later repeated where needed). The material on rithms in general graphs are important algorithmically but would require the Petersen graph establishes its basic properties for use in later examples too much time in this course this is"recommended reading and exercises 1.2: The definitions of path and cycle are intended to be intuitive; one shouldnt dwell on the heaviness of the notation for walks Chapter 4 1.3: Although characterization of graphic sequences is a classical topic 4.1: Students have trouble distinguishingkconnected from"connec some reviewers have questioned its importance. Nevertheless, here is a tivity k”and" bonds”from“ edge cuts”. Bonds are dual to cycles in the computation that students enjoy and can perform matroidal sense; there are hints of this in exercises and in Chapter 7, but 1.4: The examples are presented to motivate the model; these can be the full duality cannot be explored before Chapter 8 skipped to save time. The de Bruijn graph is a classical application. It is 4.2: Students find this section a bit difficult. The proof of 4.2.10 is desirable to present it, but it takes a while to explain similar to that of 4.2.7, making it omittable, but the application in 4.2.14 is appealing. The details of 4.2.2021 can be skipped or treated lightly, Chapter 2 since the main issue is the local version of Menger,s theorem. 4.2.2425 are 2.1: Characterization of trees is a good place to ask for input from the appealing applications that can be added; 4.2.5 (CSDR) is a fundamental class, both in listing properties and in proving equivalence. result but takes a fair amount of effort 2.2: The inductive proof for the prufer correspondence seems to be 4.3: The material on network flow is quite easy but can take a long easier for most students to grasp than the full bijective proof; it also illus time to present due to the overhead of defining new concepts. The basic trates the usual type of induction with trees. Most students in the class idea of 4.3. 1315 should be presented without belaboring the details too have seen determinants, but most have considerable difficulty understand much. 4.3.16 is a more appealing application that perhaps makes the point ing the proof of the Matrix Tree Theorem; given the time involved, it is best more effectively. Skip "Supplies and Demands Solutions Preface Chapter 5 Characterization of Line graphs", although if time and interest is plenti 5.1: If time is short, the proof of 5. 1.22(Brooks'Theorem)can be merely ful the necessity of Krausz's condition can be explained sketched 7.2: Chvatal's theorem(7.2. 13)is not as hard to present as it looks if 5.2: Be sure to cover Furans Theorem, Presentation of dirac's the the instructor has the statement and proof clearly in mind. Nevertheless orem in 5. 2.20 is valuable as an application of the Fan Lemma (menger's the proof is somewhat technical and can be skipped(the same can be said Theorem). The subsequent material has limited appeal to undergraduates. of 7 2.17). More appealing is the ChvatalErdos Theorem(7.2. 19), which 5.3: The inclusionexclusion formula for the chromatic polynomial is rtainly should be presented Skip"Cycles in Directed graphs derived here(5.3.10)without using inclusionexclusion, making it access 7.3: The theorems of Tait and grinberg make a nice culmination to ble to this class without prerequisite. However, this proof is difficult for the required material of the course. Skip "Snarks"and "Flows and Cycle students to follow in favor of the simple inclusionexclusion proof, which Covers". Nevertheless, these are lively topics that can be recommended for will be optional since that formula is not prerequisite for the course. Hence advanced students this formula should be omitted unless students know inclusionexclusion Chordal graphs and perfect graphs are more important, but these can also Chapter 8. If time permits, material from the first part of sections of be treated lightly if short of time. Skip "Counting Acyclic Orientations Chapter 8 can be presented to give the students a glimpse of other topics The best choices for conveying some understanding in a brief treatment are Chapter 6. Section 8.3 (Ramsey Theory or Sperner's Lemma) and Section 8.5 Random 6.1: The technical definitions of objects in the plane should be treated Graphs). Also possible are the Gossip Problem(or other items) from Sec very lightly. It is better to be informal here, without writing out formal tion 8.4 and some of the optional material from earlier chapters. The first definitions unless explicitly requested by students. Outerplanar graphs part of Section 8. 1(Perfect Graphs)may also be usable for this purpose if are useful as a much easier class on which to solve problems(exercises!) perfect graphs have been discussed in Section 5.3. Sections 8.2 and 86re like those on planar graphs; 6. 1820 are fundamental observations about quire more investment in preliminary material and thus are less suitable outerplanar graphs, but other items are more important if time is short. for giving a“ glimpse” 6.1.28(polyhedra) is an appealing application but can be skipped 6.2 The preparatory material 6. 47 on Kuratowski's Theorem can be presented lightly, leaving the annoying details as reading; the subsequent material on convex embedding of 3connected graphs is much more inter esting Presentation of the planarity algorithm is appealing but optional skip the proof that it works. 6.3 The four color problem is popular; for undergraduates, show the flaw in Kempe's proof (p271), but dont present the discharging rule un less ahead of schedule. Students find the concept of crossing number easy to grasp but the results are fairly difficult; try to go as far as the recur sive quartic lower bound for the complete graph. The edge bound and its geometric application are impressive but take too much time for under graduates. The idea of embeddings on surfaces can be conveyed through the examples in 6.3.21 on the torus. Interested students can be advised to read the rest of this section Chapter 7. 7.1: The proof of Vizing 's Theorem is one of the more difficult in the course, but undergraduates can gain follow it when it is presented with sufficient colored chalk. The proof can be skipped if short of time. Skip Chapter 1: Fundamental Concepts Section 1. 1: What Is a graph? 1. 1.5. Ifevery vertex of a graph g has degree 2, then g is a cycleFALSE Such a graph can be a disconnected graph with each component a cycle (lf infinite graphs are allowed, then the graph can be an infinite path 1.FUNDAMENTAL CONCEPTS 1.1.6. The graph below decomposes into copies of pg 1.1. WHAT IS A GRAPH? 1.1.1. Complete bipartite graphs and complete graphs. The complete bipar 1.1,7. a graph with more than six vertices of odd degree cannot be decom tite graph Km.n is a complete graph ifand only ifm n= l or m, n)=(1, 0) posed into three paths. Every vertex of odd degree must be the endpoint of some path in a decomposition into paths. Three paths have only six 1.1. 2. Adjacency matrices and incidence matrices for a 3vertex path endpoints. 01 010 00 100 10 1. 8. Decompositions ofa graph. The graph below decomposes into copies 010 of K1.3 with centers at the marked vertices. It decomposes into bold and solid copies of P4 as shown 1 10 10 0 10 0 10 11 Adjacency matrices for a path and a cycle with six vertices 010000 01000 101000 101000 010100 010100 001010 001010 000101 1. 1. 9. A graph and its complement. With vertices labeled as shown, two 000101 000010 100010 vertices are adjacent in the graph on the right if and only if they are not adjacent in the graph on the left. 1.1.3. Adjacency matrix for Km 01 10 h 1. 1.4.G= H if and only if g= H. If f is an isomorphism from g to H, then f is a vertex bijection preserving adjacency and nonadjacency, and 1.1.10. The complement of a simple disconnected graph must be connected hence f preserves nonadjacency and adjacency in g and is an isomor TRUE. A disconnected graph G has vertices x, y that do not belong to a phism from g to H. The same argument applies for the converse, since the path. Hencex and y are adjacent in G. furthermore x and y have no com complement of G is G mon neighbor in G, since that would yield a path connecting them. Hence 3 Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? every vertex not in (x, y) is adjacent in g to at least one of [x, y]. Hence color. Each pair of adjacent squares has one of each color, so the remaining every vertex can reach every other vertex in G using paths through Ir, yl squares cannot be partitioned into sets of this type 1.1.11. Maximum clique and ma. mum independent set. Since two ver Generalization: the two partite sets of a bipartite graph cannot be tices have degree 3 and there are only four other vertices, there is no clique matched up using pairwisedisjoint edges if the two partite sets have un of size 5. A complete subgraph with four vertices is shown in bold equal sizes Since two vertices are adjacent to all others, an independent set con 1.1. 15. Common graphs in four families: A= paths, B=cycles, C which the maximum size of an independent set is two, as marker p,in taining either of them has only one vertex. Deleting them leaves Pa, in [complete graphs), d= bipartite graphs AnB= 0: In a cycle, the numbers of vertices and edges are equal but this is false for a path AnC=KI. K2): To be a path, a graph must contain no cycle AnD=A: nonbipartite graphs have odd cycles B∩C=Ka: Only when n=3 B∩D={C2k:k≥2}: odd cycles are not bipartite. CnD=[K1, K2]: bipartite graphs cannot have triangles 1.1.12. The Petersen graph. The Petersen graph contains odd cycles, so it is not bipartite; for example, the vertices 12, 34, 51, 23, 45 form a 5cycle 1.1. 16. The graphs below are not isomorphic. The graph on the left has four The vertices 12, 13, 14, 15 form an independent set of size 4, since any cliques of size 4, and the graph on the right has only two. Alternatively, the two of these vertices have 1 as a common element and hence are nonadja complement of the graph on the left is disconnected(two 4cycles), while cent. Visually, there is an independent set of size 4 marked on the drawing the complement of the graph on the right is connected (one 8cycle) of the Petersen graph on the cover of the book. There are many ways to show that the graph has no larger independent set Proof 1. Two consecutive vertices on a cycle cannot both appear in an independent set, so every cycle contributes at most half its vertices. Since the vertex set is covered by two disjoint 5cycles, every independent set has size at most 4 Proof 2. Let ab be a vertex in an independent set s, where a, bE [5]. We show that s has at most three additional vertices Thc vertices not adjacent to ab are ac, bd, ae, bc, ad, be, and they form a cycle in that order. 1.1. 17. There are exactly two isomorphism classes of 4regular simple Hence at most half of them can be added to s graphs with 7 vertices. Simple graphs G and h are isomorphic if and only if their complements G and H are isomorphic, because an isomor 1. 13. The graph with vertex set (0, 1]and x<>y when x and y differ in phism V(G)>V(H) is also an isomorphism from g to H, and vice one place is bipartite. The partite sets are determined by the parity of the versa.Hence it suffices to count the isomorphism classes of 2regular sim number of I's. Adjacent vertices have opposite parity. (This graph is the ple graphs with 7 vertices. Every component of a finite 2regular graph is a kdimensional hypercube; see Section 1. 3.) cycle. In a simple graph, each cycle has at least three vertices. Hence each 1.1.14. Cutting opposite corner squares from an eight by eight checkerboard class it determined by partitioning 7 into integers of size at least 3 to be the sizes of the cycles. The only two graphs that result are Cr and C3+C4 leaves a subboard that cannot be partitioned into rectangles consisting of a single cycle or two cycles of lengths three and four. two adjacent unit squares. 2coloring the squares of a checkerboard so that adjacent squares have opposite colors shows that the graph having l.1. 18.Isomorphism. Using the correspondence indicated below, the first vertex for each square and an edge for each pair of adjacent squares two graphs are isomorphic; the graphs are bipartite, with u: <> U; if and is bipartite The squares at opposite corners have the same color; when only if i+j. The third graph contains odd cycles and hence is not isomor these are deleted, there are 30 squares of that color and 32 of the other phic to the e others. Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? the two drawings, the two adjacency matrices are the same, but that is harder to verify 4 l2 G is not isomorphic to F or to H. In F and in I, the numbers form an independent set, as do the letters. Thus F and H are bipartite The graph ∥3U1 G cannot be bipartite, since it contains an odd cycle. The vertices above the horizontal axis of the picture induce a cycle of length 7 It is also true that the middle graph contains a 4cycle and the others Visually, the first two graphs are @3 and the graph obtained by delet do not, but it is harder to prove the absence of a 4cycle than to prove the ing four disjoint edges from K4.4. In 23, each vertex is adjacent to the absence of an odd cycle vertices whose names have opposite parity of the number of 1s, except for the complementary vertex. Hence Q3 also has the structure of K4.4 with four disjoint edges deleted; this proves isomorphism without specifying an explicit bijection g 3 1. 1. 19. Isomorphism of graphs. The rightmost two graphs below are iso morphic. The outside 10cycle in the rightmost graph corresponds to the intermediate ring in the second graph. Pulling one of the inner 5cycles of the rightmost graph out to the outside transforms the graph into the same drawing as the second graph 1.1.21. Isomorphism. Both graphs are bipartite, as shown below by mark The graph on the left is bipartite, as shown by marking one partite set ing one partite set. In the graph on the right, every vertex appears in It cannot be isomorphic to the others, since they contain 5cycles eight 4cycles. In the graph on the left, every vertex appears in only six 4cycles (it is enough just to check one). Thus they are not isomorphic Alternatively, for every vertex in the right graph there are five vertices having common neighbors with it, while in the left graph there are six such vertices YA 产设 1. 1. 20. Among the graphs below, the first ( F)and third (h)are isomorphic, and the middle graph( G) is not isomorphic to either of these F and h are isomorphic. We exhibit an isomorphism(a bijection from V()to V(H) that preserves the adjacency relation). To do this, we name 1. 22. Isomorphism of explicit graphs. Among the graphs below, the vertices of F, write the name of each vertex of f on the corresponding [G1, G2, Gs) are pairwise isomorphic. Also G3= G4, and these are not vertex in H, and show that the names of the edges are the same in H and isomorphic to any of the others. Thus there are exactly two isomorphism F. This proves that h is a way to redraw F. We have done this below using classes represented among these graphs the first eight letters and the first eight natural numbers as names To prove these statements, one can present explicit bijections between To prove quickly that the adjacency relation is preserved, observe that vertex sets and verify that these preserve the adjacency relation(such as 1, a, 2, b, 3, C, 4,d, 5, e, 6,f,7,8, 8, h is a cycle in both drawings, and the ad by displaying the adjacency matrix for example). One can also make other ditional edges 1c, 2d, 3e, 4 f, 5g, 6h, 7a, 8b are also the same in both draw structural arguments. For example, one can move the highest vertex in G ings. Thus the two graphs have the same edges under this vertex corre down into the middle of the picture to obtain G; from this one can list the spondence. Equivalently, if we list the vertices in this specified order for desired bijection Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? One can also recall that two graphs are isomorphic if and only if their different lists of vertex degrees(similarly for 4 edges). For 3 edges, the complements are isomorphic. The complements of G1, G2, and Gs are c three isomorphism classes have degree lists 3111, 2220, and 2211, all dif cles of length 7, which are pairwise isomorphic. Each of G3 and G4 consists ferent. Hence nonisomorphic simple graphs with the same vertex degrees of two components that are cycles of lengths 3 and 4; these graphs are must have at least five vertices isomorphic to each other but not to a 7cycle 1. 1.24. Isomorphisms for the Petersen graph. Isomorphism is proved by giving an adjacencypreserving bijection between the vertex sets. For picto rial representations of graphs, this is equivalent to labeling the two graphs with the same vertex labels so that the adjacency relation is the same in both pictures; the labels correspond to a permutation of the rows and G columns of the adjacency matrices to make them identical. The various drawings of the Petersen graph below illustrate its symmetries; the label 1.1.23. Smallest pairs of nonisomorphic graphs with the same vertex de ings indicate that these are all"the same"(unlabeled)graph The number grees. For multigraphs, loopless multigraphs, and simple graphs, the re of isomorphisms from one graph to another is the same as the number of appear below. We must prove that these constructions are smalles ounds quired numbers of vertices are 2, 4, 5; constructions for the upper be isomorphisms from the graph to itself. 24 51 34 23 45 1 52 35 34 a)general b)loopless c)simple a)With 1 vertex, every edge is a loop, and the isomorphism class 12 23 determined by the number of edges, which is determined by the vertex 41 52 degree. Hence nonisomorphic graphs with the same vertex degrees have 35 41 at least two vertices b)Every loopless graph is a graph, so the answer for loopless graphs 12 12 is at least 2. The isomorphism class of a loopless graph with two vertices 35 34 35 34 is determined by the number of copies of the edge, which is determined by the vertex degrees. The isomorphism class of a loopless graph with three vertices is determined by the edge multiplicities. Let the three vertex 41 52 41 52 degrees be a, b, C, and let the multiplicities of the opposite edges be x, y, z, 24 51 where Since a= y +z,b=x+z, and c=x+ y, we can solve for the multiplicities in terms of the degrees byx =(b+ca)/ 2, y=(a+cb)/2 23 13 and z =(a+bc)/2. Hence the multiplicities are determined by the 23 13 degrees, and all loopless graphs with vertex degrees a, b, c are pairwise 4 isomorphic. Hence nonisomorphic loopless graphs with the same vertex degrees have at least four vertices 1.1.25. The Petersen graph has no cycle of length. 7. Suppose that the Pe c)Since a simple graph is a loopless graph, the answer for simple tersen graph has a cycle C of length 7. Since any two vertices of C are graphs is at least 4. There are 11 isomorphism classes of simple graphs connected by a path of length at most 3 on C, any additional edge with with four vertices. For each of 0, 1, 5, or 6 edges, there is only one isomor endpoints on C would create a cycle of length at most 4. Hence the third phism class For 2 edges, there are two isomorphism classes, but they have neighbor of each vertex on C is not on C 9 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 10 Thus there are seven edges from v(C)to the remaining three vertices its neighbors. Since G has no cycle of length less than five, G is simple By the pigeonhole principle, one of the remaining vertices receives at least and any two neighbors of x are nonadjacent and have no common neighbor three of these edges. This vertex x not on C has three neighbors on C. other than x. Hence each E Sx has at least k1 neighbors that For any three vertices on C, either two are adjacent or two have a common are not in S and not neighbors of any vertex in S. Hence g has at least neighbor on C (again the pigeonhole principle applies). Using x this com k(k1)vertices outside S and at least k+ I vertices in S for at least k2+1 pletes a cycle of length at most 4. We have shown that the assumption of a altogether 7cycle leads to a contradiction The 5cycle achieves equality when k=2. For k=3, growing the graph Alternative completion of proof. let u be a vertex on C, and let u,w symmetrically from x permits completing the graph by adding edges among be the two vertices farthest from u on C. As argued earlier, no edges join the nonneighbors of x. The result is the Petersen graph.(Comment: For vertices ofC that are not consecutive on C. Thus u is not adjacent to v or w k >8. it is known that girth 5 with minimum degree k and exactly he for Hence u, u have a common neighbor off C, as do u, u. Since u has only one vertices is impossible, except for k= 7 and possibly for k=57. neighbor off C, these two common neighbors are the same. The resulting vertex x is adjacent to all of u, U, w, and now x, u, u is a 3cycle 1.1.26. A kregular graph of girth four has at least 2k vertices, with equality only for kkk. let g be kregular of girth four, and chose xy EE(G). Girth 4 implies that G is simple and that x and y have no common neighbors Thus the neighborhoods N(r) and N()are disjoint sets of size k, which forces at least 2k vertices into G. Possibly there are others Note also that N(x) and N()are independent sets, since G has no triangle. If G has no vertices other than these, then the vertices in N(x) 1. 28. The Odd Graph has girth 6. The odd graph Ok is the disjointness can have neighbors only in N(y. Since G is kregular, every vertex of N(r) graph of the set of kelement subsets of [2k+ 1] must be adjacent to every vertex of N(y). Thus G is isomorphic to Kk. k Vertices with a common neighbor correspond to ksets with k1 com with partite sets N(x) and N(y). In other words, there is only one such mon elements. Thus they have exactly one common neighbor, and Ok has isomorphism class for each value ofk no 4cycle. Two vertices at distance 2 from a single vertex have at least Comment. One can also start with a vertex x, choose y from among k2 common neighbors. For k>2, such vertices cannot be adjacent, and the k vertices in N(r), and observe that N(y)must have kl more vertices thus Ok has no 5cycle when k>2. To form a 6cycle when k 22, let not in N(xUx. The proof then proceeds as above A={2,,k},B={k+2,,2k},a=1,b=k+1,C=2k+1.A6 cycle is (An alternative proof uses the methods of Section 1.3. a trianglefree A∪{a},B∪{b},A∪{c},B∪{a},A∪{b},BU{c} simple graph with n vertices has at most n /4 edges. Since g is kregular The Odd Graph also is not bipartite. The successive elements this yields n/42 nk /2, and hence n2 2k. Furthermore, equality holds {1,,,k},+1,,2k},{2k+1,1,.,k1}, ,{k+2,,…,2k+1} in the edge bound only for Kn/2.n/2, so this is the only such graph with 2k form an odd cycle vertices.(C. Pikscher)) 1.1. 29. Among any 6 people, there are 3 mutual acquaintances or 3 mutual strangers. Let g be the graph of the acquaintance relation, and let x be one of the people. Since x has 5 potential neighbors, x has at least 3 neighbors or at least 3 nonneighbors. By symmetry (if we complement G, we still have to prove the same statement), we may assume that x has at least 3 neighbors. If any pair of these people are acquainted then with x we have NI N(y){x} 3 mutual acquaintances but if no pair of neighbors ofx is acquainted, then 1. 27. A simple graph of girth 5 in which every vertex has degree at least the neighbors of x are three mutual strangers k has at least k2+1 vertices, with equality achieveable when k e 2, 3) .Let 1.1.30. The number of edges incident to u; is the ith diagonal entry in MM g be kregular of girth five. Let s be the set consisting of a vertex x and and in a. In both MM and A' this is the sum of the squares of the entries 11 Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? 12 in the ith row. For MM, this follows immediately from the definition of matrix multiplication and transposition, but for A" this uses the graph H H H H theoretic fact that a=A i.e. column i is the same as row i. because G is simple, the entries of the matrix are allo or l, so the sum of the squares in a row equals the number of ls in the row. In m, the ls in a row denote incident edges; in A they denote vertex neighbors. In either case, the number of ls is the degree of the vertex. H H H ifitj, then the entry in position (i, j) of a is the number of common neighbors of vi and vj. The matrix multiplication puts into position(i, J the"product" row i and column j; that is kala;, aK, When G is simple, entries in A are 1 or 0, depending on whether the corresponding vertices tlo forn=4k+1, we add a vertex x to the graph constructed above. Join x to the 2k vertices in X1 and X4 to form G. The isomorphism showing that are adjacent. Hence ai. kak, i= 1 if Uk is a common neighbor of v; and u Gx is selfcomplementary also works for G(with x mapped to itself) otherwise. the contribution is 0. Thus the number of contributions of 1 to since this isomorphism maps NG(x)=X1U X to N(x)=X2UX3 entry(i, j)is the number of common neighbos of vi and vi Proof 2 (inductive construction). If G is selfcomplementary, then let Ifitj, then the entry in position(i,) of MM is the number of edges Hi be the graph obtained from G and P4 by joining the two ends of p4 to Joining vi and vi(0 or 1 when G has no multiple edges). The ith row of all vertices of G. Let H2 be the graph obtained from G and Pa by join M has 1s corresponding to the edges incident to vi. The jth column of ing the two center vertices of P4 to all vertices of G. Both H1 and H2 M is the same as the jth row of M, which has 1s corresponding to the are selfcomplementary. Using this with G= K1 produces the two self edges incident to v;. Summing the products of corresponding entries will complementary graphs of order 5, namely Cs and the bull contribute 1 for each edge incident to both u; and vi; 0 otherwise Selfcomplementary graphs with order divisible by 4 arise from re Comment. For graphs without loops, both arguments for(i, j) in gen peated use of the above using g= Pa as a starting point and self eral apply when i=j to explain the diagonal entries complementary graphs of order congruent to 1 modulo 4 arise from repeated use of the above using G= Ki as a starting point. This construction pro 1.1.31. Kn decomposes into two isomorphic ("selfcomplementary) sub duces many more selfcomplementary graphs than the explicit construction graphs if and only if n or n1 is divisible by 4 in Proof 1 a) The number of vertices in a selfcomplementary graph is congruent to 0 or 1(mod 4). If G and G are isomorphic, then they have the same I.1.32. Km n decomposes into two isomorphic subgraphs if and only if m number of edges, but together they have()edges(with none repeated), so and n are not both odd. The condition is necessary because the number the number of edges in each must be n(n1)/4. Since this is an integer of edges must be even. It is sufficient because Km.n decomposes into two and the numbers n and n1 are not both even, one of in, n1 must be copies of Kmn/2 when n is even divisible by 4 b)Construction of selfcomplementary graphs for all such n 1.1.33. Decomposition of complete graphs into cycles through all vertices Proof 1(explicit construction). We generalize the structure of the View the vertex set of K, as Zn, the values 0, .., n1 in cyclic order. Since selfcomplementary graphs on 4 and 5 vertices, which are P4 and Cs. For each vertex has degree n1 and each cycle uses two edges at each vertex take four vertex sets of size k, say X1, X2, X3, X, and Join all the decomposition has(n1)/2 cycles vertices of X, to those of X; +1, for i= 1, 2, 3. To specify the rest of G, within For n=5 and n=7, it suffices to use cycles formed by traversing the these sets let X1 and X4 induce copies of a graph h with k vertices, and let vertices with constant difference:(0, 1, 2, 3, 4)and(0. 2, 4, 1, 3) for n= 5 X2 and Xs induce H. (For example, H may be Kk )In G, both X2 and X and(0,1,2,3,4,5,6),(0,2,4,6,1,3.5),and(0,3,6,2,5,1,4)forn=7. induce I, while X1 and X4 induce I, and the connections between sets are This construction fails for n=9 since the edges with difference 3 form X2分X4分X1分X. Thus relabeling the subsets defines an isomorphism three 3cycles. The cyclically symmetric construction below treats the ver between G and G. (There are still other constructions for G) tex set as Zs together with one special vertex.
评论 下载该资源后可以进行评论 共3条

20190408

20170921

20150121
 3.35MB
图论导引习题答案 <em>Introductionem> to <em>Graphem> <em>Theoryem> solution manual 第二版
20190104图论导引习题答案 第二版 <em>Introductionem> to <em>Graphem> <em>Theoryem> solution manual SECOND EDITION (<em>2em>001) SUMMER <em>2em>005 VERSION
 12.83MB
谷歌与MIT联袂巨著：《计算机科学的数学》高清完整.pdf版下载
20170403该书用了千页的篇幅讲述了五大板块的内容。其中第一篇就由证明到数据型讲述了数学分析的基本内容，该篇幅为计算机科学的开发者们提供了宝贵的推理和逻辑演绎能力。随后在第二篇「结构」中，该书以数论开始讲述，首先
 62.65MB
<em>Introductionem> to <em>Graphem> <em>Theoryem>
20180720<em>Introductionem> to <em>Graphem> <em>Theoryem> Second Edition by D. <em>Westem>
图论导引习题答案 <em>Introductionem> to <em>Graphem> <em>Theoryem> solution manual 第二版下载_course
20190104图论导引习题答案 第二版 <em>Introductionem> to <em>Graphem> <em>Theoryem> solution manual SECOND EDITION (<em>2em>001) SUMMER <em>2em>005 VERSION
 3.2MB
图论导引 第二版 Douglas B. <em>Westem>
20120727图论导引 第二版 Douglas B. <em>Westem> 机械工业出版社 <em>Introductionem> to <em>Graphem> <em>Theoryem> Second Edition Solution Manual (by Dou
 19.16MB
Computer Vision  Linda Shapiro.pdf
20180206Computer Vision  Linda Shapiro.pdf Computer Vision  Linda Shapiro.pdf Computer Vision  Linda Shap
 16.50MB
图论导引 中文版 第二版
20141025图论导引 中文版 第二版图论起源于著名的哥尼斯堡七桥问题，在计算科学、社会科学和自然科学等各个领域都有广泛应用。本书是本科生或研究生一学期或两学期的图论课程教材。内容全面，证明与应用实例并举，不仅包括
 50.19MB
计算机视觉（英文版）
20180720CONTENTS I IMAGEFORMATION 1 1 RADIOMETRY — MEASURING LIGHT 3 1.1 Light in Space 3 1.1.1 Foreshorteni
 89.80MB
华章数学译丛18 图论导引 原书第<em>2em>版 中英文附答案
20190520华章数学译丛18 图论导引 原书第<em>2em>版 中英文附答案
 7.0MB
图论导引（<em>Introductionem> to <em>graphem> <em>theoryem>, <em>2em>nd edition) D. B. <em>Westem>
20100712DJVU格式；在网络上能找到的最好的；英文版；经典的图论教材

下载
国家新一代人工智能标准体系建设指南.pdf
国家新一代人工智能标准体系建设指南.pdf

下载
learning.zip
learning.zip

博客
SpringCloud学习笔记（1）Spring Cloud Eureka
SpringCloud学习笔记（1）Spring Cloud Eureka

博客
sourceflinksink实现端到端的状态一致性
sourceflinksink实现端到端的状态一致性

学院
JavaScript高级bom实战开发教程
JavaScript高级bom实战开发教程

学院
QT实战监控系统+linux RTSP监控服务器
QT实战监控系统+linux RTSP监控服务器

博客
String StringBuffer StringBuilder 的区别及应用场景
String StringBuffer StringBuilder 的区别及应用场景

下载
模糊控制与神经网络的应用研究
模糊控制与神经网络的应用研究

博客
如何克服比较心理？
如何克服比较心理？

博客
使用Python实现DICOM格式批量转换为JPG格式
使用Python实现DICOM格式批量转换为JPG格式

学院
基于OpenCV的钢管计数项目实战
基于OpenCV的钢管计数项目实战

学院
Qt入门和上位机开发实战
Qt入门和上位机开发实战

博客
HiveSQL基础练习一
HiveSQL基础练习一

博客
#JAVA自学第3天“小龙女说好想过过过过过过的生活”
#JAVA自学第3天“小龙女说好想过过过过过过的生活”

博客
HDU 6825 Set1（组合数学+数学推导）
HDU 6825 Set1（组合数学+数学推导）

下载
ApkParser.zip
ApkParser.zip

下载
TikTok 日本版.zip
TikTok 日本版.zip

学院
AI计算机视觉 系统入门+实战
AI计算机视觉 系统入门+实战

学院
esp8266 rtos开发基于esp_idf3.2微信小程序天猫精灵APP控制
esp8266 rtos开发基于esp_idf3.2微信小程序天猫精灵APP控制

学院
RHCE8官方培训第三册Ansible自动化
RHCE8官方培训第三册Ansible自动化

学院
一学即懂的计算机视觉深度学习篇
一学即懂的计算机视觉深度学习篇

学院
C++高级编程
C++高级编程

博客
网络协议总结
网络协议总结

博客
开发积累——异步任务队列
开发积累——异步任务队列

学院
linux实战之HLS(M3U8)服务器编写
linux实战之HLS(M3U8)服务器编写

博客
大数据从入门到放弃（四）— Shell的使用
大数据从入门到放弃（四）— Shell的使用

学院
Python数字货币量化投资
Python数字货币量化投资

学院
Python+FFmpeg搭建直播网站
Python+FFmpeg搭建直播网站

下载
小型空间飞行器集成化遥测系统设计与实现
小型空间飞行器集成化遥测系统设计与实现

学院
信息系统项目管理师通关教程第3阶段选择题2018上
信息系统项目管理师通关教程第3阶段选择题2018上