Xem mẫu
2
Connectivity of Graphs
2.1 Bipartite graphs and trees
In problems such as the shortest path problem we look for minimum solutions that satisfy the given requirements. The solutions in these cases are usually subgraphs without cycles. Such connected graphs will be called trees, and they are used, e.g., in search algorithms for databases. For concrete applications in this respect, see
T.H. CORMEN, C.E. LEISERSON AND R.L. RIVEST, “Introduction to Algorithms”, MIT Press, 1993.
Certain structures with operations are representable as trees. +These trees are sometimes called construction trees, de-
y
composition trees, factorization trees or grammatical trees.
Grammatical trees occur especially in linguistics, where syn-
x
+
tactic structures of sentences are analyzed. On the right there
isatree of operations forthe arithmetic formula x (y + z ) + y . y
z
Bipartite graphs
DEFINITION. A graph is called bipartite, if has a partition to two subsets and G
Y
X
V
G
such that each edge connects a vertex of and a vertex of . In this case, X
(X ; Y )uv 2 E
Y
G
is a bipartition of , and is -bipartite. G
(X ; Y )
G
A bipartite graph (as in the above) is a complete -G
(m; k )
bipartite graph, if jX j = m, jY j = k , and uv 2 E for all G
and . u 2 X
v 2 Y
All complete -bipartite graphs are isomorphic. Let (m; k )
denote such a graph. K
m;k
A subset is stable, if is a discrete graph. X V
G[X ℄
G
K
2;3
The following result is clear from the definitions.
Theorem 2.1. A graph is bipartite if and only if has a partition to two stable subsets. V
G
G
Example 2.1. The -cube of Example 1.5 is bipartite for all . Indeed, consider Q
A = fu j
kk
k
has an even number of 0 s and has an odd number of 0 s Clearly, these sets g
g:B = fu j u
11
u
partition B k , and they are stable in Q . k
2.1 Bipartite graphs and trees 17
Theorem 2.2. A graph is bipartite if and only if it has no odd cycles. G
) Let be -bipartite. For a cycle of length , k
(X ; Y )
C : v ! : : : ! v = v
G)
1 1
k +1
implies , , ..., , . Consequently, is v 2 Y
v 2 X
k + 1 = 2m + 1v 2 Y
v 2 Xv 2 X
1 2 3 2i 2i +1
odd, and is even. k = jC j
(( ) Suppose that all cycles in G are even. First, we observe that it suffices to show the
claim for connected graphs. Indeed, if is disconnected, then each cycle of is contained in G
G
one of the connected components, G ; : : : ; G , of G. If G is (X ; Y )-bipartite, then (X [1 p i i i 1
is a bipartition of . G
X [ [ X ; Y [ Y [ [ Y )
2 p 1 2 p
Assume thus that is connected. Let be a chosen vertex, and define G
v 2 G
is even
g;X = fx j d (v ; x)
G
is odd
g :Y = fy j d (v ; y )
G
Since is connected, . Also, by the definition of distance, . G
X \ Y = ;V = X [ Y
G
be both in or both in , and let ? and ? be (among Y
P : v ! u
Q : v ! wu; w 2 G
X
the) shortest paths from to and . w
uv
Assume that x is the last common vertex of P and Q: P = P P , Q = Q Q , where 1 2 1 2
? and ? are independent. Since and are shortest paths, and Q
Q : x ! wP : x ! u
P
QP
2 2 1 1
are shortest paths v !? x . Consequently, jP j = jQ j. 1 1
jP j and jQ j have the same parity. Therefore 2 2
Q 1 P : w !? u is an even path. It follows that 2
2
u and w are not adjacent in G, since otherwise
Q 1 P (uw ) would be an odd cycle. Therefore G[X ℄ v2
2
and G[Y ℄ are discrete induced subgraphs, and G is
u
P
2
P
1
x
uw
Q
1
Q
bipartite as claimed. ut 2 w
Checking whether a graph is bipartite is easy. In-deed, this can be done by using two ‘opposite’
colours, say 1 and 2. Start from any vertex v , and 1
1
colour it by 1 . Then colour the neighbours of v by
1 2
1
2 , and proceed by colouring all neighbours of an al-
ready coloured vertex by an opposite colour. 2 22
If the whole graph can be coloured, then G is
(X ; Y ) -bipartite, where X consists of those vertices 1 1with colour 1 , and Y of those vertices with colour 1 2
2 ; otherwise, at some point one of the vertices gets both colours, and in this case, G is not bipartite.
Theorem 2.3 (ERDÖS (1965)). Each graph has a bipartite subgraph such that G
H G
1 . "
"
H
G
2
Proof. Let V = X [ Y be a partition such that the number of edges between X and Y is as G
large as possible. Denote
F = E \ fuv j u 2 X ; v 2 Y g ;
G
2.1 Bipartite graphs and trees 18
and let . Obviously is a spanning subgraph, and it is bipartite. By the maximum H
H = G[F ℄
condition,
1
d (v ) ;
d (v )
G
H
2
since, otherwise, is on the wrong side. (That is, if , then the pair 0 , v
X = X n fv g
v 2 X
0 does better that the pair .) Now X ; Y
Y = Y [ fv g
X X
1
1 1
1
d (v )
d (v ) = " :
" =
H
G G
H
2 2 2 2
v 2H v 2G
ut
Bridges
DEFINITION. An edge e 2 E is a bridge of the graph G, G
if has more connected components than , that is, if G
G e
. (G e) > (G)
In particular, and most importantly, an edge in a connected e
is a bridge if and only if is disconnected. On the right G
G e
the two horizontal lines are bridges. The rest are not.
Theorem 2.4. An edge is a bridge if and only if is not in any cycle of . e
Ge 2 E
G
Proof. First of all, note that e = uv is a bridge if and only if u and v belong to different
connected components of . G e
) If there is a cycle in containing , then there is a cycle ? , )
C = eP : u ! v ! uG
e
where P : v ! u is a path in G e , and so e is not a bridge.
( ) Assume that is not a bridge. Hence and are in the same connected com-(
v
ue = uv
. If ? is a path in , then ? is a cycle in that G e
eP : u ! v ! uP : v ! u
GG e
contains e . tu
Lemma 2.1. Let be a bridge in a connected graph . e
G
(i) Then . (G e) = 2
(ii) Let H be a connected component of G e . If f 2 E is a bridge of H , then f is a bridge H
of G.
Proof. For (i), let . Since is a bridge, the ends and are not connected in . v
G e
ue = uv
e
. Since is connected, there exists a path ? in . This is a path of , G
w 2 G
G eP : w ! v
G
unless ? contains , in which case the part ? is a path in . w ! u
e = uv
G eP : w ! u ! v
For (ii), if f 2 E belongs to a cycle C of G , then C does not contain e (since e is in no H
cycle), and therefore C is inside H , and f is not a bridge of H . ut
2.1 Bipartite graphs and trees 19
Trees
DEFINITION. A graph is called acyclic, if it has no cycles. An acyclic graph is also called a forest. A tree is a connected acyclic graph.
By Theorem 2.4 and the definition of a tree, we have
Corollary 2.1. A connected graph is a tree if and only if all its edges are bridges.
Example 2.2. The following enumeration result for trees has many different proofs, the first of which was given by CAYLEY in 1889: There are nn 2 trees on a vertex set V of n elements. We omit the proof.
On the other hand, there are only a few trees up to isomorphism:
n 1 2 3 4 5 6 7 8
trees 1 1 1 2 3 6 11 23
n 9 10 11 12 13
trees 47 106 235 551 1301
14 15 16
3159 7741 19 320
The nonisomorphic trees of order are: 6
Theorem 2.5. The following are equivalent for a graph . T
...
- tailieumienphi.vn
nguon tai.lieu . vn