page573.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 127 行
HTML
127 行
<HTML><HEAD><TITLE>Minimum-Cost Spanning Trees</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7741" HREF="page574.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7739" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7733" HREF="page572.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7743" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0016500000000000000000">Minimum-Cost Spanning Trees</A></H1><P>In this section we consider undirected graphs and their subgraphs.A <em>subgraph</em><A NAME=52193> </A> of a graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >is any graph <IMG WIDTH=86 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72005" SRC="img2402.gif" >such that <IMG WIDTH=48 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline72007" SRC="img2403.gif" > and <IMG WIDTH=44 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline72009" SRC="img2404.gif" >.In particular, we consider <em>connected</em> undirected graphsand their <em>minimal subgraphs</em><A NAME=52196> </A><A NAME=52197> </A>.The minimal subgraph of a connected graph is called a <em>spanning tree</em>:<P><BLOCKQUOTE> <b>Definition (Spanning Tree)</b><A NAME="defngraphsspantree"> </A>Consider a <em>connected</em>, <em>undirected</em> graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >.A <em>spanning tree</em><A NAME=52205> </A> of <I>G</I>is a subgraph of <I>G</I>, say <IMG WIDTH=81 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72017" SRC="img2405.gif" >,with the following properties:<OL><LI> <IMG WIDTH=48 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline72019" SRC="img2406.gif" >.<LI> <I>T</I> is connected.<LI> <I>T</I> is acyclic.</OL></BLOCKQUOTE><P>Figure <A HREF="page573.html#figgraph15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows an undirected graph, <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72025" SRC="img2407.gif" >,together with three of its spanning trees.A spanning tree is called a <em>tree</em>because every <em>acyclic</em> undirected graphcan be viewed as a general, unordered tree.Because the edges are undirected,any vertex may be chosen to serve as the root of the tree.For example, the spanning tree of <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72025" SRC="img2407.gif" >given in Figure <A HREF="page573.html#figgraph15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c)can be viewed as the general, unordered tree<P> <IMG WIDTH=340 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath71999" SRC="img2408.gif" ><P><P><P><A NAME="52460"> </A><A NAME="figgraph15"> </A> <IMG WIDTH=575 HEIGHT=401 ALIGN=BOTTOM ALT="figure52215" SRC="img2409.gif" ><BR><STRONG>Figure:</STRONG> An undirected graph and three spanning trees.<BR><P><P>According to Definition <A HREF="page573.html#defngraphsspantree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,a spanning tree is connected.Therefore, as long as the tree contains more than one vertex,there can be no vertex with degree zero.Furthermore, the following theorem guarantees that there is alwaysat least one vertex with degree one:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremgraphsi"> </A>Consider a connected, undirected graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >, where <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72033" SRC="img2410.gif" >.Let <IMG WIDTH=77 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72035" SRC="img2411.gif" > be a spanning tree of <I>G</I>.The spanning tree <I>T</I> contains at least one vertex of degree one.</BLOCKQUOTE><P> extbfProof (By contradiction).Assume that there is no vertex in <I>T</I> of degree one.That is, all the vertices in <I>T</I> have degree two or greater.Then by following edges into and out of verticeswe can construct a path that is cyclic.But a spanning tree is acyclic--a contradiction.Therefore, a spanning tree always contains at least one vertex of degree one.<P>According to Definition <A HREF="page573.html#defngraphsspantree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the edge set of a spanning treeis a subset of the edges in the spanned graph.How many edges must a spanning tree have?The following theorem answers the question:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremgraphsii"> </A>Consider a connected, undirected graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >.Let <IMG WIDTH=77 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72035" SRC="img2411.gif" > be a spanning tree of <I>G</I>.The number of edges in the spanning tree is given by<P> <IMG WIDTH=297 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath72000" SRC="img2412.gif" ><P></BLOCKQUOTE><P> extbfProof (By induction).We can prove Theorem <A HREF="page573.html#theoremgraphsii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by induction on <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" >,the number of vertices in the graph.<P><b>Base Case</b>Consider a graph that contains only one node, i.e., <IMG WIDTH=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72053" SRC="img2413.gif" >.Clearly, the spanning tree for such a graph contains no edges.Since <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72055" SRC="img2414.gif" >,the theorem is valid.<P><b>Inductive Hypothesis</b>Assume that the number of edges in a spanning tree for a graphwith <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" > has been shown to be <IMG WIDTH=46 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72059" SRC="img2415.gif" >for <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72061" SRC="img2416.gif" >.<P>Consider a graph <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72063" SRC="img2417.gif" > with <I>k</I>+1 verticesand its spanning tree <IMG WIDTH=98 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72067" SRC="img2418.gif" >.According to Theorem <A HREF="page573.html#theoremgraphsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72069" SRC="img2419.gif" > contains at least one vertex of degree one.Let <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71565" SRC="img2351.gif" > be one such vertexand <IMG WIDTH=74 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72073" SRC="img2420.gif" > be the one edge emanating from <I>v</I> in <IMG WIDTH=32 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64043" SRC="img1223.gif" >.<P>Let <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64027" SRC="img1219.gif" > be the graph of <I>k</I> nodes obtained by removing <I>v</I>and its emanating edge from the graph <IMG WIDTH=32 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64043" SRC="img1223.gif" >.That is, <IMG WIDTH=189 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline72087" SRC="img2421.gif" >.<P>Since <IMG WIDTH=32 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64043" SRC="img1223.gif" > is connected, so too is <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64027" SRC="img1219.gif" >.Similarly, since <IMG WIDTH=32 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64043" SRC="img1223.gif" > is acyclic, so too is <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64027" SRC="img1219.gif" >.Therefore <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64027" SRC="img1219.gif" > is a spanning tree with <I>k</I> vertices.By the inductive hypothesis <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64027" SRC="img1219.gif" > has <I>k</I>-1 edges.Thus, <IMG WIDTH=32 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64043" SRC="img1223.gif" > as <I>k</I> edges.<P>Therefore, by induction on <I>k</I>,the spanning tree for a graph with <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif" > verticescontains <IMG WIDTH=46 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72059" SRC="img2415.gif" > edges.<P><BR> <HR><UL> <LI> <A NAME="tex2html7744" HREF="page574.html#SECTION0016501000000000000000">Constructing Spanning Trees</A><LI> <A NAME="tex2html7745" HREF="page575.html#SECTION0016502000000000000000">Minimum-Cost Spanning Trees</A><LI> <A NAME="tex2html7746" HREF="page576.html#SECTION0016510000000000000000">Prim's Algorithm</A><LI> <A NAME="tex2html7747" HREF="page578.html#SECTION0016520000000000000000">Kruskal's Algorithm</A></UL><HR><A NAME="tex2html7741" HREF="page574.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7739" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7733" HREF="page572.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7743" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?