page583.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 164 行
HTML
164 行
<HTML><HEAD><TITLE>Exercises</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="tex2html7849" HREF="page584.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7847" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7841" HREF="page582.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7851" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0016700000000000000000">Exercises</A></H1><P><OL><LI> <A NAME="exercisegraphsi"> </A> Consider the <em>undirected graph</em> <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72433" SRC="img2475.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. List the elements of <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" > and <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" >. Then, for each vertex <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71565" SRC="img2351.gif" > do the following: <OL><LI> Compute the in-degree of <I>v</I>.<LI> Compute the out-degree of <I>v</I>.<LI> List the elements of <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70619" SRC="img2176.gif" >.<LI> List the elements of <IMG WIDTH=30 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70651" SRC="img2183.gif" >. </OL><P><P><A NAME="56156"> </A><A NAME="figgraph19"> </A> <IMG WIDTH=575 HEIGHT=222 ALIGN=BOTTOM ALT="figure55872" SRC="img2476.gif" ><BR><STRONG>Figure:</STRONG> Sample graphs.<BR><P><LI> <A NAME="exercisegraphsii"> </A> Consider the directed graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72433" SRC="img2475.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. <OL><LI> Show how the graph is represented using an adjacency matrix.<LI> Show how the graph is represented using adjacency lists. </OL><LI> Repeat Exercises <A HREF="page583.html#exercisegraphsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page583.html#exercisegraphsii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the <em>directed graph</em> <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72455" SRC="img2477.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> <A NAME="exercisegraphsiv"> </A> Consider a <em>depth-first traversal</em> of the undirected graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72433" SRC="img2475.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> starting from vertex <I>a</I>. <OL><LI> List the order in which the nodes are visited in a preorder traversal.<LI> List the order in which the nodes are visited in a postorder traversal. </OL> Repeat this exercise for a depth-first traversal starting from vertex <I>d</I>.<LI> <A NAME="exercisegraphsv"> </A> List the order in which the nodes of the undirected graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72433" SRC="img2475.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> are visited by a <em>breadth-first traversal</em> that starts from vertex <I>a</I>. Repeat this exercise for a breadth-first traversal starting from vertex <I>d</I>.<LI> Repeat Exercises <A HREF="page583.html#exercisegraphsiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page583.html#exercisegraphsv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> for the <em>directed graph</em> <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72455" SRC="img2477.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<LI> List the order in which the nodes of the directed graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72455" SRC="img2477.gif" > shown in Figure <A HREF="page583.html#figgraph19"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> are visited by a <em>topological order traversal</em> that starts from vertex <I>a</I>.<LI> Consider an undirected graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >. If we use a <IMG WIDTH=57 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71089" SRC="img2274.gif" > adjacency matrix <I>A</I> to represent the graph, we end up using twice as much space as we need because <I>A</I> contains redundant information. That is, <I>A</I> is symmetric about the diagonal and all the diagonal entries are zero. Show how a one-dimensional array of length <IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72485" SRC="img2478.gif" > can be used to represent <I>G</I>. Hint: consider just the part of <I>A</I> above the diagonal.<LI> What is the relationship between the sum of the degrees of the vertices of a graph and the number of edges in the graph.<LI> A graph with the maximum number of edges is called a <em>fully connected graph</em><A NAME=56182> </A>. Draw fully connected, undirected graphs that contain 2, 3, 4, and 5 vertices.<LI> Prove that an undirected graph with <I>n</I> vertices contains at most <I>n</I>(<I>n</I>-1)/2 edges.<LI> Every tree is a directed, acyclic graph (DAG), but there exist DAGs that are not trees. <OL><LI> How can we tell whether a given DAG is a tree?<LI> Devise an algorithm to test whether a given DAG is a tree. </OL><LI> Consider an acyclic, connected, undirected graph <I>G</I> that has <I>n</I> vertices. How many edges does <I>G</I> have?<LI> In general, an undirected graph contains one or more <em>connected components</em><A NAME=56186> </A>. A connected component of a graph <I>G</I> is a subgraph of <I>G</I> that is <em>connected</em> and contains the largest possible number of vertices. Each vertex of <I>G</I> is a member of exactly one connected component of <I>G</I>. <OL><LI> Devise an algorithm to count the number of connected components in a graph.<LI> Devise an algorithm that labels the vertices of a graph in such a way that all the vertices in a given connected component get the same label and vertices in different connected components get different labels. </OL><LI> A <em>source</em><A NAME=56191> </A> in an directed graph is a vertex with zero in-degree. Prove that every DAG has at least one source.<LI> What kind of DAG has a unique topological sort?<LI> Under what conditions does a <em>postorder</em> depth-first traversal of a DAG visit the vertices in <em>reverse</em> topological order.<LI> Consider a pair of vertices, <I>v</I> and <I>w</I>, in a directed graph. Vertex <I>w</I> is said to be <em>reachable</em> from vertex <I>v</I> if there exists a path in <I>G</I> from <I>v</I> to <I>w</I>. Devise an algorithm that takes as input a graph, <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >, and a pair of vertices, <IMG WIDTH=58 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72525" SRC="img2479.gif" >, and determines whether <I>w</I> is reachable from <I>v</I>.<LI> An <em>Eulerian walk</em><A NAME=56196> </A> is a path in an undirected graph that starts and ends at the same vertex <em>and traverses every edge</em> in the graph. Prove that in order for such a path to exist, all the nodes must have even degree.<LI> Consider the binary relation <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61249" SRC="img788.gif" > defined for the elements of the set <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66495" SRC="img1536.gif" > as follows: <P> <IMG WIDTH=386 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath72431" SRC="img2480.gif" ><P> How can we determine whether <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61249" SRC="img788.gif" > is a <em>total order</em>?<LI> Show how the <em>single-source shortest path</em> problem can be solved on a DAG using a topological-order traversal. What is the running time of your algorithm?<LI> Consider the directed graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72537" SRC="img2481.gif" > shown in Figure <A HREF="page583.html#figgraph20"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Trace the execution of <em>Dijkstra's algorithm</em> as it solves the single-source shortest path problem starting from vertex <I>a</I>. Give your answer in a form similar to Table <A HREF="page565.html#tblgraphsdijkstra"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="56547"> </A><A NAME="figgraph20"> </A> <IMG WIDTH=575 HEIGHT=204 ALIGN=BOTTOM ALT="figure56203" SRC="img2482.gif" ><BR><STRONG>Figure:</STRONG> Sample weighted graphs.<BR><P><LI> Dijkstra's algorithm works as long as there are no negative edge weights. Given a graph that contains negative edge weights, we might be tempted to eliminate the negative weights by adding a constant weight to all of the edge weights to make them all positive. Explain why this does not work.<LI> Dijkstra's algorithm can be modified to deal with negative edge weights (but not negative cost cycles) by eliminating the <em>known</em> flag <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71551" SRC="img2347.gif" > and by inserting a vertex back into the queue every time its <em>tentative distance</em> <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline71553" SRC="img2348.gif" > decreases. Explain why the modified algorithm works correctly. What is the running time of the modified algorithm?<LI> Consider the directed graph <IMG WIDTH=22 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72537" SRC="img2481.gif" > shown in Figure <A HREF="page583.html#figgraph20"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Trace the execution of <em>Floyd's algorithm</em> as it solves the <em>all-pairs shortest path problem</em>.<LI> Prove that if the edge weights on an undirected graph are <em>distinct</em>, there is only one minimum-cost spanning tree.<LI> <A NAME="exercisegraphsprim"> </A> Consider the undirected graph <IMG WIDTH=23 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72551" SRC="img2483.gif" > shown in Figure <A HREF="page583.html#figgraph20"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. Trace the execution of <em>Prim's algorithm</em> as it finds the <em>minimum-cost spanning tree</em> starting from vertex <I>a</I>.<LI> Repeat Exercise <A HREF="page583.html#exercisegraphsprim"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> using <em>Kruskal's algorithm</em>.<LI> Do Exercise <A HREF="page476.html#exercisealgsgraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</OL><HR><A NAME="tex2html7849" HREF="page584.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7847" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7841" HREF="page582.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7851" 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 + -
显示快捷键?