《图论GraphTheorych7章节》由会员分享，可在线阅读，更多相关《图论GraphTheorych7章节（102页珍藏版）》请在金锄头文库上搜索。
1、1,Chapter 7 Edges and Cycles ,2,7.1.1. Definition. The line graph of G, written L(G), is the simple graph whose vertices are the edges of G, with ef E(L(G) when e and f have a common endpoint in G.,3,Some questions about edges in a graph G can be phrased as questions about vertices in L(G). When ext
2、ended to all simple graphs, the vertex question may be more difficult. If we can solve it, then we can answer the original question about edges in G by applying the vertex result to L(G). In Chapter 1, we studied Eulerian circuits. An Eulerian circuit in G yields a spanning cycle in the line graph L
3、(G). (Exercise 7.2.10 shows that the converse need not hold!) In Section 7.2, we study spanning cycles for graphs in general. As discussed in Appendix B, this problem is computationally difficult.,4,In Chapter 3, we studied matchings. A matching in G becomes an inde- pendent set in L(G). Thus a(G) =
4、 a(L(G), and the study of a for graphs is the study of a for line graphs. Computing a is harder for general graphs than for line graphs. Section 3.1 considers this for bipartite graphs, and we describe the general case briefly in Appendix B. In Chapter 4, we studied connectivity. Mengers Theorem gav
5、e a min-max relation for connectivity and internally disjoint paths in all graphs. By applying this theorem to an appropriate line graph, we proved the analogous min-max relation for edge-connectivity and edge-disjoint paths in all graphs.,5,In Chapter 5, we studied vertex coloring. Coloring edges s
6、o that each color class is a matching amounts to proper vertex coloring of the line graph. Thus edge-coloring is a special case of vertex coloring and therefore potentially easier. We discuss edge-coloring in this section. Our main result, when stated in terms of vertex coloring of line graphs, is a
7、n algorithm to compute X(H) within 1 when H is the line graph of a simple graph. Thus line graphs suggest the problems of edge-coloring and spanning cycles that are discussed in this chapter. We first study these separately. In Section 7.3, we study their connections to each other and to planar grap
8、hs.,6,7.1.2. Example. Edge-coloring of K2n . In a league with 2n teams, we want to schedule games so that each pair of teams plays a game, but each team plays at most once a week. Since each team must play 2n - 1 others, the season lasts at least 2n - 1 weeks. The games of each week must form a matc
9、hing. We can schedule the season in 2n - 1 weeks if and only if we can partition E(K2n) into 2n -1 matchings. Since K2n is 2n-1-regular, these must be perfect matchings.,7,7.1.3. Definition. A k-edge-coloring of G is a labeling f: E(G) S, where |S| = k (often we use S = k). The labels are colors; th
10、e edges of one color form a color class. A k-edge-coloring is proper if incident edges have different labels; that is, if each color class is a matching. A graph is k-edge-colorable if it has a proper k-edge-coloring. The edge-chromatic number X (G) of a loopless graph G is the least k such that G i
11、s k-edge-colorable. Chromatic index is another name for X (G).,8,9,7.1.7. Theorem. (Konig 1916) If G is bipartite, then X(G) =(G). 7.1.10. Theorem. (Vizing 1964, 1965, Gupta 1966) If G is a simple graph, then X(G) (G) + 1. 7.1.11. Definition. A simple graph G is Class 1 if X(G) =(G). It is Class 2 i
12、f X(G) =(G) + 1.,10,7.2.1. Definition. A Hamiltonian graph is a graph with a spanning cycle, also called a Hamiltonian cycle.,11,7.2.2. Example. Bipartite graphs. A spanning cycle in a bipartite graph visits the two partite sets alternately, so there can be no such cycle unless the partite sets have
13、 the same size. Hence Km.n is Hamiltonian only if m = n. Alternatively, we can argue that the cycle returns to different vertices of one partite set after each visit to the other partite set.,12,7.2.3. Proposition. If G has a Hamiltonian cycle, then for each nonempty set S V, the graph G - S has at
14、most |S| components. Proof: When leaving a component of G - S, a Hamiltonian cycle can go only to S, and the arrivals in S must use distinct vertices of S. Hence S must have at least as many vertices as G - S has components.,13,7.2.5. Example. The graph on the left below is bipartite with partite se
15、ts of equal size. However, it fails the necessary condition of Proposition 7.2.3. Hence it is not Hamiltonian. The graph on the right shows that the necessary condition is not sufficient. This graph satisfies the condition but has no spanning cycle. All edges incident to vertices of degree 2 must be
16、 used, but in this graph that requires three edges incident to the central vertex.,14,7.2.8. Theorem. (Dirac 1952b). If G is a simple graph with at least three vertices and (G) n(G)/2, then G is Hamiltonian. 7.2.9. Lemma. (Ore 1960) Let G be a simple graph. If u, V are distinct non-adjacent vertices of G with d(u) + d(v) n(G), then G is Hamiltonian if and only if G + uv is Hamiltonian.,15,7.2.10. Definition. The (Hamiltonian) closure of a graph G,
