chap05.htm

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

<pre>4  <img src="../images/arrow12.gif">  2 ,</sub></sup></pre><P>
<img src="85_a.gif"><P>
<a name="072f_123e"><a name="072f_123f">The function is injective, since no element of <B>Z</B> is the image of more than one element of <B>N</B>. It is surjective, since every element of <B>Z</B> appears as the image of some element of <B>N</B>. Hence, the function is bijective. A bijection is sometimes called a <I><B>one-to-one correspondence</I></B>, since it pairs elements in the domain and codomain. A bijection from a set <I>A</I> to itself is sometimes called a <I><B>permutation.</B></I><P>
<a name="072f_1240">When a function &acirc; is bijective, its <I><B>inverse</I></B> <I>&acirc;</I><SUP>-1</SUP> is defined as<P>
<pre><I>f</I><SUP>-1</SUP>(<I>b</I>) = <I>a</I> if and only if <I>f</I>(<I>a</I>) = <I>b</I>.</sub></sup></pre><P>
For example, the inverse of the function <I>&acirc;</I>(<I>n</I>) = (-1)<I><SUP>n</I></SUP> <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT> is<P>
<img src="85_b.gif"><P>





<h2><a name="0730_0001">Exercises<a name="0730_0001"></h2><P>
<a name="0730_0002">5.3-1<a name="0730_0002"><P>
Let <I>A </I>and <I>B</I> be finite sets, and let <I>f </I>: <I>A</I> <img src="../images/arrow12.gif"> <I>B</I> be a function. Show that<P>
<I><B>a.</I></B>     if <I>f</I> is injective, then |<I>A</I>| <img src="../images/lteq12.gif"> |<I>B</I>|;<P>
<I><B>b.</I></B>     f <I>f</I> is surjective, then |<I>A</I>| <img src="../images/gteq.gif"> |<I>B</I>|.<P>
<a name="0730_0003">5.3-2<a name="0730_0003"><P>
Is the function <I>f </I>(<I>x</I>) = <I>x </I>+ 1 bijective when the domain and the codomain are <B>N</B>? Is it bijective when the domain and the codomain are <B>Z</B>?<P>
<a name="0730_0004">5.3-3<a name="0730_0004"><P>
Give a natural definition for the inverse of a binary relation such that if a relation is in fact a bijective function, its relational inverse is its functional inverse.<P>
<a name="0730_0005">5.3-4<a name="0730_0005"><P>
Give a bijection from <B>Z</B> to <B>Z</B> <img src="../images/mult.gif"> <B>Z</B>.<P>
<P>


<P>







<h1><a name="0731_126f">5.4 Graphs<a name="0731_126f"></h1><P>
<a name="0731_1241">This section presents two kinds of graphs: directed and undirected. The reader should be aware that certain definitions in the literature differ from those given here, but for the most part, the differences are slight. Section 23.1 shows how graphs can be represented in computer memory.<P>
<a name="0731_1242"><a name="0731_1243"><a name="0731_1244"><a name="0731_1245"><a name="0731_1246"><a name="0731_1247">A <I><B>directed graph</I></B> (or <I><B>digraph</I></B>) <I>G</I> is a pair (<I>V, E</I>), where <I>V</I> is a finite set and <I>E</I> is a binary relation on <I>V</I>. The set <I>V</I> is called the <I><B>vertex set</I></B> of <I>G</I>, and its elements are called <I><B>vertices</I></B> (singular: <I><B>vertex</I></B>). The set <I>E</I> is called the <I><B>edge set</I></B> of <I>G</I>, and its elements are called <I><B>edges.</I></B> Figure 5.2(a) is a pictorial representation of a directed graph on the vertex set {1, 2, 3, 4, 5, 6}. Vertices are represented by circles in the figure, and edges are represented by arrows. Note that <I><B>self-loops</I></B>--edges from a vertex to itself--are possible.<P>
<a name="0731_1248">In an <I><B>undirected graph</I></B> <I>G</I> = (<I>V, E</I>), the edge set <I>E</I> consists of <I>unordered</I> pairs of vertices, rather than ordered pairs. That is, an edge is a set {<I>u, v</I>}, where <I>u,v</I> <img src="../images/memof12.gif"> <I>V</I> and <I>u</I> <img src="../images/noteq.gif"> <I>v</I>. By convention, we use the notation (<I>u, v</I>) for an edge, rather than the set notation {<I>u,v</I>}, and (<I>u,v</I>) and (<I>v, u</I>) are considered to be the same edge. In an undirected graph, self-loops are forbidden, and so every edge consists of exactly two distinct vertices. Figure 5.2(b) is a pictorial representation of an undirected graph on the vertex set {1, 2, 3, 4, 5, 6}.<P>
<a name="0731_1249">Many definitions for directed and undirected graphs are the same, although certain terms have slightly different meanings in the two contexts. If (<I>u, v</I>) is an edge in a directed graph <I>G</I> = (<I>V, E</I>), we say that (<I>u, v</I>) is <I><B>incident from</I></B> or <I><B>leaves</I></B> vertex <I>u</I> and is <I><B>incident to</I></B> or <I><B>enters</I></B> vertex <I>v</I>. For example, the edges leaving vertex 2 in Figure 5.2(a) are (2, 2), (2, 4), and (2, 5). The edges entering vertex 2 are (1, 2) and (2, 2). If (<I>u, v</I>) is an edge in an undirected graph <I>G</I> = (<I>V</I>, <I>E</I>), we say that (<I>u</I>, <I>v</I>) is <I><B>incident on</I></B> vertices <I>u</I> and <I>v</I>. In Figure 5.2(b), the edges incident on vertex 2 are (1, 2) and (2, 5).<P>
<img src="87_a.gif"><P>
<h4><a name="0731_1270">Figure 5.2 Directed and undirected graphs. (a) A directed graph G = (V, E), where V = {1, 2, 3, 4, 5, 6} and E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}. The edge (2, 2) is a self-loop. (b) An undirected graph G = (V, E), where V = {1, 2, 3, 4, 5, 6} and E = {(1, 2), (1, 5), (2, 5), (3, 6)}. The vertex 4 is isolated. (c) The subgraph of the graph in part (a) induced by the vertex set {1, 2, 3, 6}.<a name="0731_1270"></sub></sup></h4><P>
<a name="0731_124a"><a name="0731_124b">If (<I>u, v</I>) is an edge in a graph <I>G</I> = (<I>V, E</I>), we say that vertex <I>v</I> is <I><B>adjacent</I></B> to vertex <I>u</I>. When the graph is undirected, the adjacency relation is symmetric. When the graph is directed, the adjacency relation is not necessarily symmetric. If <I>v</I> is adjacent to <I>u</I> in a directed graph, we sometimes write <I>u</I> <img src="../images/arrow12.gif"> <I>v</I>. In parts (a) and (b) of Figure 5.2, vertex 2 is adjacent to vertex 1, since the edge (1, 2) belongs to both graphs. Vertex 1 is <I>not</I> adjacent to vertex 2 in Figure 5.2(a), since the edge (2, 1) does not belong to the graph.<P>
<a name="0731_124c"><a name="0731_124d"><a name="0731_124e">The <I><B>degree</I></B> of a vertex in an undirected graph is the number of edges incident on it. For example, vertex 2 in Figure 5.2(b) has degree 2. In a directed graph, the <I><B>out-degree</I></B> of a vertex is the number of edges leaving it, and the <I><B>in-degree</I></B> of a vertex is the number of edges entering it. The <I><B>degree</I></B> of a vertex in a directed graph is its in-degree plus its out-degree. Vertex 2 in Figure 5.2(a) has in-degree 2, out-degree 3, and degree 5.<P>
<a name="0731_124f"><a name="0731_1250"><a name="0731_1251"><a name="0731_1252"><a name="0731_1253">A <I><B>path</I></B> of <I><B>length</I></B> <I>k</I> from a vertex <I>u</I> to a vertex <I>u' </I>in a graph<I> G</I> = (<I>V, E</I>) is a sequence <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . , <I>v<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> of vertices such that <I>u = v</I><SUB>0</SUB><I>, u' = v<SUB>k</I></SUB>, and (<I>v<SUB>i - </I>1</SUB>,<I> v<SUB>i</I></SUB>) <img src="../images/memof12.gif"> <I>E</I> for <I>i</I> = 1, 2, . . . , <I>k</I>. The length of the path is the number of edges in the path. The path <I><B>contains</I></B> the vertices <I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB> , . . . , <I>v<SUB>k</I></SUB> and the edges (<I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB>), (<I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>), . . . , (<I>v<SUB>k</I> - 1</SUB>, <I>v<SUB>k</I></SUB>). If there is a path <I>p</I> from <I>u</I> to <I>u</I>', we say that <I>u</I>' is <I><B>reachable</I></B> from <I>u</I> via <I>p</I>, which we sometimes write as <img src="87_b.gif"> if <I>G</I> is directed. A path is <I><B>simple</I></B> if all vertices in the path are distinct. In Figure 5.2(a), the path <img src="../images/lftwdchv.gif">1, 2, 5, 4<img src="../images/wdrtchv.gif"> is a simple path of length 3. The path <img src="../images/lftwdchv.gif">2, 5, 4, 5<img src="../images/wdrtchv.gif"> is not simple.<P>
<a name="0731_1254">A <I><B>subpath</I></B> of path <I>p</I> = <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB>, . . . , <I>v<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> is a contiguous subsequence of its vertices. That is, for any 0 <img src="../images/lteq12.gif"> i <I><img src="../images/lteq12.gif"> j </I><img src="../images/lteq12.gif"> k<I>, the subsequence of vertices <img src="../images/lftwdchv.gif">v<SUB>i</SUB>, v<SUB>i + </I>1</SUB>, . . . <I>,v<SUB>j</I></SUB><img src="../images/wdrtchv.gif"> is a subpath of <I>p</I>.<P>
<a name="0731_1255"><a name="0731_1256"><a name="0731_1257"><a name="0731_1258">In a directed graph, a path <img src="../images/lftwdchv.gif"><I>v</I><SUB>0<I>, </SUB>v</I><SUB>1</SUB>, . . . , <I>v<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> forms a <I><B>cycle</I></B> if <I>v</I><SUB>0</SUB> = <I>v<SUB>k</I></SUB> and the path contains at least one edge. The cycle is <I><B>simple</I></B> if, in addition, <I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . , <I>v<SUB>k</I></SUB> are distinct. A self-loop is a cycle of length 1. Two paths <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB>, <I>v</I><SUB>1</SUB>, <I>v</I><SUB>2</SUB>, . . . , <I>v<SUB>k - </I>1</SUB>, <I>v</I><SUB>0</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif"><I>v</I>'<SUB>0</SUB>, <I>v</I>'<I><SUB>1</SUB>, </I>v<I>'</I><SUB>2</SUB>, . . . , <I>v</I>'<I><SUB>k - 1</SUB>,</I>v<I>'</I><SUB>0</SUB><img src="../images/wdrtchv.gif"> form the same cycle if there exists an integer <I>j</I> such that <I>v</I><I>'<SUB>i</I></SUB> = <I>v</I><SUB>(<I>i </I>+ <I>j</I>) mod<I>k</I></SUB> for <I>i</I> = 0, 1, . . . , <I>k</I> - 1<I><B>.</I></B> In Figure 5.2(a), the path <img src="../images/lftwdchv.gif">1, 2, 4, 1<img src="../images/wdrtchv.gif"> forms the same cycle as the paths <img src="../images/lftwdchv.gif">2, 4, 1, 2<img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif">4, 1, 2, 4<img src="../images/wdrtchv.gif">. This cycle is simple, but the cycle <img src="../images/lftwdchv.gif">1, 2, 4, 5, 4, 1<img src="../images/wdrtchv.gif"> is not. The cycle <img src="../images/lftwdchv.gif">2, 2<img src="../images/wdrtchv.gif"> formed by the edge (2, 2) is a self-loop. A directed graph with no self-loops is <I><B>simple</I></B>. In an undirected graph, a path <img src="../images/lftwdchv.gif"><I>v</I><SUB>0</SUB><I>, v</I><SUB>l</SUB><I>, . . . , v<SUB>k</I></SUB><img src="../images/wdrtchv.gif"><I> </I>forms a<I> <B>cycle</I></B> if <I>v</I><SUB>0</SUB><I> = v<SUB>k</I></SUB> and <I>v</I><SUB>1</SUB><I>, v</I><SUB>2</SUB><I>, . . . , v<SUB>k</I></SUB> are distinct. For example, in Figure 5.2(b), the path <img src="../images/lftwdchv.gif">1, 2, 5, 1<img src="../images/wdrtchv.gif"> is a cycle. A graph with no cycles is <I><B>acyclic</I></B>.<P>
<a name="0731_1259"><a name="0731_125a"><a name="0731_125b">An undirected graph is <I><B>connected</I></B> if every pair of vertices is connected by a path. The <I><B>connected components</I></B> of a graph are the equivalence classes of vertices under the "is reachable from" relation. The graph in Figure 5.2(b) has three connected components: {1, 2, 5}, {3, 6}, and {4}. Every vertex in {1,2,5} is reachable from every other vertex in {1, 2, 5}. An undirected graph is connected if it has exactly one connected component, that is, if every vertex is reachable from every other vertex.<P>
<a name="0731_125c"><a name="0731_125d"><a name="0731_125e">A directed graph is <I><B>strongly connected</I></B> if every two vertices are reachable from each other. The <I><B>strongly connected components</I></B> of a graph are the equivalence classes of vertices under the "are mutually reachable" relation. A directed graph is strongly connected if it has only one strongly connected component. The graph in Figure 5.2(a) has three strongly connected components: {1, 2, 4, 5}, {3}, and {6}. All pairs of vertices in {1, 2, 4, 5} are mutually reachable. The vertices {3, 6} do not form a strongly connected component, since vertex 6 cannot be reached from vertex 3.<P>
<a name="0731_125f">Two graphs <I>G</I> = (<I>V</I>, <I>E</I>) and <I>G</I><I>'</I> = (<I>V</I>'<I>, </I>E<I>'</I>) are <I><B>isomorphic</I></B> if there exists a bijection <I>f </I>: <I>V</I> <img src="../images/arrow12.gif"> <I>V</I><I>'</I> such that <I>(u, v)</I> <img src="../images/memof12.gif"> <I>E</I> if and only if (<I>f</I>(<I>u</I>), <I>f</I>(<I>v</I>)) <img src="../images/memof12.gif"> <I>E</I><I>'</I>. In other words, we can relabel the vertices of <I>G</I> to be vertices of <I>G</I><I>'</I>, maintaining the corresponding edges in <I>G</I> and <I>G</I><I>'</I>. Figure 5.3(a) shows a pair of isomorphic graphs <I>G</I> and <I>G</I><I>'</I> with respective vertex sets <I>V</I> = {1, 2, 3, 4, 5, 6} and <I>V</I>'<I> = {</I>u, v, w, x, y, z<I>}. The mapping from </I>V<I> to </I>V<I>'</I> given by <I>f</I>(1) = <I>u, f</I>(2) = <I>v, f</I>(3) = <I>w, f</I>(4) = <I>x, f</I>(5) = <I>y, f</I>(6) = <I>z</I> is the required bijective function. The graphs in Figure 5.3(b) are not isomorphic. Although both graphs have 5 vertices and 7 edges, the top graph has a vertex of degree 4 and the bottom graph does not.<P>
<a name="0731_1260"><a name="0731_1261">We say that a graph <I>G</I><I>' = </I>(<I>V</I>', E<I>'</I>) is a <I><B>subgraph</I></B> of <I>G = </I>(<I>V,E</I>) if <I>V</I><I>' </I><img src="../images/rgtubar.gif"><I> V</I> and <I>E</I>' <I><img src="../images/rgtubar.gif"> E</I>. Given a set <I>V</I>' <I><img src="../images/rgtubar.gif"> V</I>, the subgraph of <I>G</I> <I><B>induced</I></B> by <I>V</I><I>'</I> is the graph <I>G</I><I>' = </I>(<I>V</I>', E<I>'</I>), where<P>
<pre><I>E</I>'<I> = {(</I>u, v<I>) <img src="../images/memof12.gif"> </I>E<I>: </I>u, v<I> <img src="../images/memof12.gif"> </I>V<I>'</I>} .</sub></sup></pre><P>
<img src="89_a.gif"><P>
<h4><a name="0731_1271">Figure 5.3 (a) A pair of isomorphic graphs. The vertices of the top graph are mapped to the vertices of the bottom graph by f(1) = u, f(2) = v, f(3) = w, f(4) = x, f(5) = y, f(6) = z. (b) Two graphs that are not isomorphic, since the top graph has a vertex of degree 4 and the bottom graph does not.<a name="0731_1271"></sub></sup></h4><P>
The subgraph induced by the vertex set {1, 2, 3, 6} in Figure 5.2(a) appears in Figure 5.2(c) and has the edge set {(1, 2), (2, 2), (6, 3)}.<P>
<a name="0731_1262"><a name="0731_1263"><a name="0731_1264">Given an undirected graph <I>G</I> = (<I>V, E</I>), the <I><B>directed version</I></B> of <I>G</I> is the directed graph <I>G</I>' = (V, E<I>'</I>), where (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"> E<I>'</I> if and only if (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"><I> E. </I>That is, each undirected edge (<I>u, v</I>) in <I>G</I> is replaced in the directed version by the two directed edges (<I>u, v</I>) and (<I>v, u</I>). Given a directed graph <I>G</I> =(<I>V, E</I>), the <I><B>undirected version</I></B> of <I>G</I> is the undirected graph <I>G</I><I>' = </I>(<I>V, E</I>'), where (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"> E<I>'</I> if and only if <I>u</I> <img src="../images/noteq.gif"> <I>v</I> and (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"><I> E.</I> That is, the undirected version contains the edges of <I>G</I> "with their directions removed" and with self-loops eliminated. (Since (<I>u, v</I>) and (<I>v</I>,<I> u</I>) are the same edge in an undirected graph, the undirected version of a directed graph contains it only once, even if the directed graph contains both edges (<I>u, v</I>) and (<I>v</I>,<I> u</I>). In a directed graph <I>G =</I> (<I>V, E</I>), a <I><B>neighbor</I></B> of a vertex <I>u</I> is any vertex that is adjacent to <I>u</I> in the undirected version of <I>G.</I> That is, <I>v</I> is a neighbor of <I>u</I> if either (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I> or (<I>v</I>,<I> u</I>)<I> </I><img src="../images/memof12.gif"><I> E.</I> In an undirected graph, <I>u</I> and <I>v</I> are neighbors if they are adjacent.<P>
<a name="0731_1265"><a name="0731_1266"><a name="0731_1267"><a name="0731_1268"><a name="0731_1269"><a name="0731_126a"><a name="0731_126b">Several kinds of graphs are given special names. A <I><B>complete graph</I></B> is an undirected graph in which every pair of vertices is adjacent. A <I><B>bipartite graph</I></B> is an undirected graph <I>G = (V, E</I>) in which <I>V</I> can be partitioned into two sets <I>V</I><SUB>1</SUB> and <I>V</I><SUB>2</SUB> such that (<I>u, v</I>)<I> </I><img src="../images/memof12.gif"><I> E</I> implies either <I>u </I><img src="../images/memof12.gif"> V<I><SUB>1</SUB> and </I>v <I><img src="../images/memof12.gif"> V</I><SUB>2</SUB> or <I>u </I><img src="../images/memof12.gif"> V<I><SUB>2</SUB> and </I>v <I><img src="../images/memof12.gif"> V</I><SUB>1</SUB>. That is, all edges go between the two sets <I>V</I><SUB>1</SUB>and <I>V</I><SUB>2</SUB>. An acyclic, undirected graph is a <I><B>forest</I></B>, and a connected, acyclic, undirected graph is a (<I><B>free)</I></B> <I><B>tree</I></B> (see Section 5.5). We often take the first letters of "directed acyclic graph" and call such a graph a <I><B>dag.</I></B><P>
<a name="0731_126c"><a name="0731_126d"><a name="0731_126e">There are two variants of graphs that you may occasionally encounter. A <I><B>multigraph</I></B> is like an undirected graph, but it can have both multiple edges between vertices and self-loops. A <I><B>hypergraph</I></B> is like an undirected graph, but each <I><B>hyperedge</I></B>, rather than connecting two vertices, connects an arbitrary subset of vertices. Many algorithms written for ordinary directed and undirected graphs can be adapted to run on these graphlike structures.<P>





<h2><a name="0732_1270">Exercises<a name="0732_1270"></h2><P>
<a name="0732_1271">5.4-1<a name="0732_1271"><P>
<a name="0732_126f">Attendees of a faculty party shake hands to greet each other, and each professor remembers how many times he or she shook hands. At the end of the party, the department head sums up the number of times that each professor shook hands. Show that the result is even by proving the<I><B> handshaking lemma</I></B>: if <I>G = (V, E</I>) is an undirected graph, then<P>