chap05.htm

美国麻省理工的算法导论,英文版,看后程序员宏观的能力培养有好处

<img src="90_a.gif"><P>
<a name="0732_1272">5.4-2<a name="0732_1272"><P>
Show that in an undirected graph, the length of a cycle must be at least 3.<P>
<a name="0732_1273">5.4-3<a name="0732_1273"><P>
Show that if a directed or undirected graph contains a path between two vertices <I>u</I> and <I>v</I>, then it contains a simple path between <I>u</I> and <I>v.</I> Show that if a directed graph contains a cycle, then it contains a simple cycle.<P>
<a name="0732_1274">5.4-4<a name="0732_1274"><P>
Show that any connected, undirected graph <I>G = </I>(<I>V</I>,<I> E</I>) satisfies |<I>E| <img src="../images/gteq.gif"> |</I>V| -<I> 1.</I><P>
<a name="0732_1275">5.4-5<a name="0732_1275"><P>
Verify that in an undirected graph, the &quot;is reachable from&quot; relation is an equivalence relation on the vertices of the graph. Which of the three properties of an equivalence relation hold in general for the &quot;is reachable from&quot; relation on the vertices of a directed graph?<P>
<a name="0732_1276">5.4-6<a name="0732_1276"><P>
What is the undirected version of the directed graph in Figure 5.2(a)? What is the directed version of the undirected graph in Figure 5.2(b)?<P>
<a name="0732_1277">5.4-7<a name="0732_1277"><P>
Show that a hypergraph can be represented by a bipartite graph if we let incidence in the hypergraph correspond to adjacency in the bipartite graph. (<I>Hint</I>: Let one set of vertices in the bipartite graph correspond to vertices of the hypergraph, and let the other set of vertices of the bipartite graph correspond to hyperedges.)<P>
<P>


<P>







<h1><a name="0733_1271">5.5 Trees<a name="0733_1271"></h1><P>
<a name="0733_1270">As with graphs, there are many related, but slightly different, notions of trees. This section presents definitions and mathematical properties of several kinds of trees. Sections 11.4 and 23.1 describe how trees can be represented in a computer memory.<P>





<h2><a name="0734_1274">5.5.1 Free trees<a name="0734_1274"></h2><P>
<a name="0734_1271"><a name="0734_1272"><a name="0734_1273">As defined in Section 5.4, a <I><B>free tree</I></B> is a connected, acyclic, undirected graph. We often omit the adjective "free" when we say that a graph is a tree. If an undirected graph is acyclic but possibly disconnected, it is a <I><B>forest.</I></B> Many algorithms that work for trees also work for forests. Figure 5.4(a) shows a free tree, and Figure 5.4(b) shows a forest. The forest in Figure 5.4(b) is not a tree because it is not connected. The graph in Figure 5.4(c) is neither a tree nor a forest, because it contains a cycle.<P>
The following theorem captures many important facts about free trees.<P>
<a name="0734_1275">Theorem 5.2<a name="0734_1275"><P>
Let <I>G = (V, E</I>) be an undirected graph. The following statements are equivalent.<P>
1.     <I>G</I> is a free tree.<P>
2.     Any two vertices in <I>G</I> are connected by a unique simple path.<P>
3.     <I>G</I> is connected, but if any edge is removed from <I>E</I>, the resulting graph is disconnected.<P>
4.     <I>G</I> is connected, and |<I>E| = |</I>V| - 1.<P>
5.     <I>G</I> is acyclic, and |<I>E| = |</I>V| - 1.<P>
6.     <I>G</I> is acyclic, but if any edge is added to <I>E</I>, the resulting graph contains a cycle.<P>
<I><B>Proof     </I></B>(1) <img src="../images/rtbigar.gif"> (2): Since a tree is connected, any two vertices in <I>G</I> are connected by at least one simple path. Let <I>u</I> and <I>v</I> be vertices that are connected by two distinct simple paths <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB>, as shown in Figure 5.5. Let <I>w</I> be the vertex at which the paths first diverge; that is, <I>w</I> is the first vertex on both <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> whose successor on <I>p</I><SUB>1</SUB> is <I>x</I> and whose successor on <I>p</I><SUB>2</SUB> is <I>y</I>, where <I>x </I><img src="../images/noteq.gif"> <I>y.</I> Let <I>z</I> be the first vertex at which the paths reconverge; that is, <I>z</I> is the first vertex following <I>w</I> on <I>p</I><SUB>1</SUB> that is also on <I>p</I><SUB>2</SUB>. Let <I>p</I>' be the subpath of <I>p</I><SUB>1</SUB><I> </I>from<I> w</I> through <I>x</I> to <I>z</I>, and let <I>p</I>\" be the subpath of <I>p</I><SUB>2</SUB> from <I>w</I> through <I>y</I> to <I>z.</I> Paths <I>p</I>' and <I>p</I>\" share no vertices except their endpoints. Thus, the path obtained by concatenating <I>p</I>' and the reverse of <I>p</I>\"<I></I>is a cycle. This is a contradiction. Thus, if <I>G</I> is a tree, there can be at most one path between two vertices.<P>
<img src="91_a.gif"><P>
<h4><a name="0734_1276">Figure 5.4 (a) A free tree. (b) A forest. (c) A graph that contains a cycle and is therefore neither a tree nor a forest.<a name="0734_1276"></sub></sup></h4><P>
<img src="92_a.gif"><P>
<h4><a name="0734_1277">Figure 5.5 A step in the proof of Theorem 5.2: if (1) G is a free tree, then (2) any two vertices in G are connected by a unique simple path. Assume for the sake of contradiction that vertices u and v are connected by two distinct simple paths p<SUB>1</SUB> and p<SUB>2</SUB>. These paths first diverge at vertex w, and they first reconverge at vertex z. The path p' concatenated with the reverse of the path p\" forms a cycle, which yields the contradiction.<a name="0734_1277"></sub></sup></h4><P>
(2) <img src="../images/rtbigar.gif"> (3): If any two vertices in <I>G</I> are connected by a unique simple path, then <I>G</I> is connected. Let (<I>u, v</I>) be any edge in <I>E</I>. This edge is a path from <I>u</I> to <I>v</I>, and so it must be the unique path from <I>u</I> to <I>v.</I> If we remove (<I>u, v</I>) from <I>G</I>, there is no path from<I> u</I> to <I>v</I>, and hence its removal disconnects <I>G.</I><P>
(3) <img src="../images/rtbigar.gif"> (4): By assumption, the graph <I>G</I> is connected, and by Exercise 5.4-4, we have |<I>E| <img src="../images/gteq.gif"> |</I>V| - 1. We shall prove |<I>E| <img src="../images/lteq12.gif"> |</I>V| - 1 by induction. A connected graph with <I>n</I> = 1 or <I>n</I> = 2 vertices has <I>n</I> - 1 edges. Suppose that <I>G</I> has <I>n</I> <img src="../images/gteq.gif"> 3 vertices and that all graphs satisfying (3) with fewer than <I>n</I> vertices also satisfy |<I>E| </I><img src="../images/lteq12.gif"> |V| - 1. Removing an arbitrary edge from <I>G</I> separates the graph into <I>k</I> <img src="../images/gteq.gif"> 2 connected components (actually <I>k</I> = 2). Each component satisfies (3), or else <I>G</I> would not satisfy (3). Thus, by induction, the number of edges in all components combined is at most |<I>V| - </I>k<I> <img src="../images/lteq12.gif"> |</I>V| - 2. Adding in the removed edge yields |<I>E| <img src="../images/lteq12.gif"> </I>|V| - 1.<P>
(4) <img src="../images/rtbigar.gif"> (5): Suppose that <I>G</I> is connected and that |<I>E| = |</I>V| - 1. We must show that <I>G</I> is acyclic. Suppose that <I>G</I> has a cycle containing <I>k </I>vertices <I>v</I><SUB>1</SUB>,<I> v</I><SUB>2</SUB>,<I> . . . </I>,<I> v<SUB>k</SUB>. Let G<SUB>k</SUB> = </I>(<I>V<SUB>k</I></SUB>,<I> E<SUB>k</I></SUB>) be the subgraph of <I>G</I> consisting of the cycle. Note that |<I>V<SUB>k</SUB>| = |E<SUB>k</I></SUB>|<I> = k.</I> If <I>k &lt; |V|, there must be a vertex </I>v<SUB>k<I>+1</SUB> <img src="../images/memof12.gif"> </I>V -<I> </I>V<SUB>k<I></SUB> that is adjacent to some vertex </I>v<SUB>i</SUB> <I><img src="../images/memof12.gif"> V<SUB>k</I></SUB>, since <I>G</I> is connected. Define <I>G<SUB>k+</I>1</SUB><I> = </I>(<I>V<SUB>k</I>+1</SUB>,<SUB> </SUB><I>E<SUB>k</I>+1</SUB>)<I> </I>to be the subgraph of <I>G</I> with <I>V<SUB>k</I>+1</SUB><I> = V<SUB>k</I></SUB><img src="../images/wideu.gif">{<I>v<SUB>k</I>+1</SUB>} and <I>E<SUB>k</I>+1</SUB> = <I>E<SUB>k</I></SUB><img src="../images/wideu.gif">{(<I>v</I><SUB>1</SUB>, <I>v<SUB>k</I>+1</SUB>)}. Note that |<I>V<SUB>k</I>+1</SUB>| = |<I>E<SUB>k</I>+1</SUB>|<I> = k</I>+1. If <I>k+</I>1 &lt; <I>n</I>, we can continue, defining G<I><SUB>k</I>+2</SUB> in the same manner, and so forth, until we obtain <I>G<SUB>n</SUB> = </I>(<I>V<SUB>n</SUB>, E<SUB>n</I></SUB>), where <I>n</I> = |<I>V|, </I>V<SUB>n<I></SUB> = </I>V<I>, and |</I>E<SUB>n<I></SUB>|</I> <I>=</I> |V<SUB>n<I></SUB>| = |</I>V|<FONT FACE="Courier New" SIZE=2>.</FONT> Since <I>G<SUB>n</SUB> </I>is a subgraph of<I> G</I>, we have <I>E<SUB>n</I></SUB> <img src="../images/rgtubar.gif"> <I>E</I>, and hence |<I>E| <img src="../images/gteq.gif"> |</I>V|, which contradicts the assumption that |<I>E| = |</I>V<I>| - 1. Thus, </I>G<I> is acyclic.</I><P>
(5) <img src="../images/rtbigar.gif"> (6): Suppose that <I>G</I> is acyclic and that <FONT FACE="Courier New" SIZE=2>|<I>E </I>|</FONT> = <FONT FACE="Courier New" SIZE=2>|<I>V </I>|</FONT> - 1. Let <I>k</I> be the number of connected components of <I>G</I>. Each connected component is a free tree by definition, and since (1) implies (5), the sum of all edges in all connected components of <I>G</I> is |<I>V </I>| - <I>k</I>. Consequently, we must have <I>k</I> = 1, and <I>G </I>is in fact a tree. Since (1) implies (2), any two vertices in <I>G</I> are connected by a unique simple path. Thus, adding any edge to <I>G </I>creates a cycle.<P>
(6) <img src="../images/rtbigar.gif"> (1): Suppose that <I>G</I> is acyclic but that if any edge is added to <I>E</I>, a cycle is created. We must show that <I>G</I> is connected. Let <I>u</I> and <I>v</I> be arbitrary vertices in <I>G</I>. If <I>u</I> and <I>v</I> are not already adjacent, adding the edge (<I>u, v</I>) creates a cycle in which all edges but (<I>u, v</I>) belong to <I>G</I>. Thus, there is a path from <I>u</I> to <I>v</I>, and since <I>u</I> and <I>v</I> were chosen arbitrarily, <I>G </I>is connected.      <P>
<P>







<h2><a name="0735_1288">5.5.2 Rooted and ordered trees<a name="0735_1288"></h2><P>
<a name="0735_1274"><a name="0735