A maior rede de estudos do Brasil

Grátis
655 pág.

Pré-visualização | Página 35 de 50

```such that G \ e
is separable. Show that the block tree of G \ e is a path.
(G.A. Dirac; M.D. Plummer)
—————
—————
5.2.12
a) By employing the splitting-oﬀ operation, show that every even graph has an
odd number of cycle decompositions.
b) Deduce that each edge of an even graph lies in an odd number of cycles.
(S. Toida)
5.3 Ear Decompositions
Apart from K1 and K2, every nonseparable graph contains a cycle. We describe
here a simple recursive procedure for generating any such graph starting with an
arbitrary cycle of the graph.
Let F be a subgraph of a graph G. An ear of F in G is a nontrivial path in G
whose ends lie in F but whose internal vertices do not.
Proposition 5.6 Let F be a nontrivial proper subgraph of a nonseparable graph
G. Then F has an ear in G.
Proof If F is a spanning subgraph of G, the set E(G)\E(F ) is nonempty because,
by hypothesis, F is a proper subgraph of G. Any edge in E(G) \ E(F ) is then an
ear of F in G. We may suppose, therefore, that F is not spanning.
Since G is connected, there is an edge xy of G with x ∈ V (F ) and y ∈ V (G) \
V (F ). Because G is nonseparable, G−x is connected, so there is a (y, F −x)-path
Q in G− x. The path P := xyQ is an ear of F . �
The proofs of the following proposition is left to the reader (Exercise 5.3.1).
Proposition 5.7 Let F be a nonseparable proper subgraph of a graph G, and let
P be an ear of F . Then F ∪ P is nonseparable. �
A nested sequence of graphs is a sequence (G0, G1, . . . , Gk) of graphs such that
Gi ⊂ Gi+1, 0 ≤ i < k. An ear decomposition of a nonseparable graph G is a nested
sequence (G0, G1, . . . , Gk) of nonseparable subgraphs of G such that:
� G0 is a cycle,
� Gi+1 = Gi ∪ Pi, where Pi is an ear of Gi in G, 0 ≤ i < k,
� Gk = G.
126 5 Nonseparable Graphs
G0 G1 G2
G3 G4 G5
Fig. 5.6. An ear decomposition of the Petersen graph
An ear decomposition of the Petersen graph is shown in Figure 5.6, the initial
cycle and the ear added at each stage being indicated by heavy lines.
Using the fact that every nonseparable graph other than K1 and K2 has a
cycle, we may deduce the following theorem from Propositions 5.6 and 5.7.
Theorem 5.8 Every nonseparable graph other than K1 and K2 has an ear decom-
position. �
This recursive description of nonseparable graphs can be used to establish many
of their properties by induction. We describe below an interesting application of
ear decompositions to a problem of traﬃc ﬂow. Further applications may be found
in the exercises at the end of this section.
Strong orientations
A road network in a city is to be converted into a one-way system, in order that
traﬃc may ﬂow as smoothly as possible. How can this be achieved in a satisfactory
manner? This problem clearly involves ﬁnding a suitable orientation of the graph
representing the road network. Consider, ﬁrst, the graph shown in Figure 5.7a.
No matter how this graph is oriented, the resulting digraph will not be strongly
connected, so traﬃc will not be able to ﬂow freely through the system, certain
locations not being accessible from certain others. On the other hand, the graph
of Figure 5.7b has the strong orientation shown in Figure 5.7c (one, moreover, in
which each vertex is reachable from each other vertex in at most two steps).
Clearly, a necessary condition for a graph to have a strong orientation is that
it be free of cut edges. Robbins (1939) showed that this condition is also suﬃcient.
The proof makes use of the following easy proposition (Exercise 5.3.9).
5.3 Ear Decompositions 127
(a) (b) (c)
Fig. 5.7. (a) A graph with no strong orientation, and (b) a graph with (c) a strong
orientation
Proposition 5.9 A connected digraph is strongly connected if and only if each of
its blocks is strongly connected. �
Theorem 5.10 Every connected graph without cut edges has a strong orientation.
Proof Let G be a connected graph without cut edges. By Proposition 5.9, it
suﬃces to show that each block B of G has a strong orientation. We may assume
that B �= K1. Moreover, because G has no cut edges, B �= K2. Thus B contains a
cycle and, by Theorem 5.8, has an ear decomposition (G0, G1, . . . , Gk). Consider
the orientation of B obtained by orienting G0 as a directed cycle and each ear
as a directed path. It can be veriﬁed easily, by induction on i, that the resulting
orientation of Gi is strong for each i, 0 ≤ i ≤ k. In particular, the orientation
assigned to B = Gk is strong. �
Exercises
�5.3.1 Deduce Proposition 5.7 from Theorem 5.2.
�5.3.2 An edge e of a nonseparable graph G is called deletable if G \ e is non-
separable, and contractible if G/e is nonseparable. Show that every edge of a
nonseparable graph is either deletable or contractible.
5.3.3 Show that if G has no even cycles, then each block of G is either an odd
cycle or a copy of K1 or K2.
5.3.4 Let G be a nonseparable graph, and let x and y be two vertices of G. Show
that there is a linear ordering v1, v2, . . . , vn of the vertices of G such that v1 = x,
vn = y, and each vertex vj , 2 ≤ j ≤ n − 1, is joined to some vertex vi with i < j
and some vertex vk with k > j.
5.3.5 Prove the following dual version of Theorem 5.2: A connected graph is non-
separable if and only if any two of its edges are contained in a common bond.
128 5 Nonseparable Graphs
5.3.6 Let G be a graph and let B∼ denote the binary relation on E deﬁned by e B∼ f
if and only if either e = f or there is a bond of G containing both e and f . Show
that:
a) the relation B∼ is an equivalence relation on E,
b) the subgraphs of G induced by the equivalence classes under this relation are
its nontrivial blocks.
5.3.7 Deduce the result of Exercise 5.1.4 from Theorem 5.8.
5.3.8 Let G be a nonseparable graph diﬀerent from K1 and K2, and let (G0, G1,
. . . , Gk) be an ear decomposition of G.
a) Show that k = m− n.
b) Suppose that Gi+1 = Gi ∪Pi, where Pi is an ear of Gi in Gi+1, 0 ≤ i < k. Set
C0 := G0 and, for 1 ≤ i ≤ k, let Ci be a cycle in Gi containing the ear Pi−1.
Show that (C0, C1, . . . , Ck) is a basis for C(G), the cycle space of G.
�5.3.9 Prove Proposition 5.9.
—————
—————
5.3.10 Let G be a nonseparable nonbipartite graph.
a) Show that the cycle space C(G) of G has a basis consisting of m−n even cycles
and one odd cycle.
b) Deduce that the dimension of the subspace of C(G) generated by the even
cycles of G is m− n. (M.A. Henning and C.H.C. Little)
5.3.11 Call a family of subgraphs of a graph linearly independent if the incidence
vectors of their edge sets are linearly independent over GF (2). Let G be a nonsep-
arable graph on at least two vertices.
a) If x and y are two vertices of G, show that there are m − n + 2 linearly
independent xy-paths in G, and that this number is the greatest possible.
b) Let e be an edge of G. Deduce that the cycle space C(G) of G has a basis
consisting entirely of cycles containing the edge e.
c) Deduce that G has at least
(
m−n+2
2
)
cycles.
d) Which nonseparable graphs G have exactly
(
m−n+2
2
)
cycles?
5.3.12 Vine
A vine on a path xPy in a graph G is a sequence (xiQiyi : 1 ≤ i ≤ r) of internally
disjoint ears of P in G such that:
x = x1 ≺ x2 ≺ y1 � x3 ≺ y2 � x4 ≺ · · · � xr ≺ yr−1 ≺ yr = y
where ≺ is the precedence relation on P (see Figure 5.8).
Let xPy be a path in a nonseparable graph G.
a) Show that there is vine (xiQiyi : 1 ≤ i ≤ r) on P .
5.4 Directed Ear Decompositions 129
x y
P
Q1 Q2 Q3
Q4
Q5
Fig. 5.8. A vine on a path
b) Set Pi := xiPyi and Ci := Pi ∪ Qi, 1 ≤ i ≤ r. Show that Cjk := �{Ci : j ≤
i ≤ k} is a cycle of G, 1 ≤ j ≤ k ≤ r.
c) Suppose that r = 2t− 1 is odd.
i) Show that the t2 cycles Cjk, 1 ≤ j ≤ t ≤ k ≤ r, together cover the path P
at least t times and each ear Qi min{i, 2t− i} t times.
ii) Deduce that if P has length
, then one of these cycles has length at least
(```