📄 page522.html
字号:
<HTML><HEAD><TITLE>Terminology</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="tex2html7173" HREF="page523.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7171" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7165" HREF="page521.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7175" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016102000000000000000">Terminology</A></H3><P>Consider a directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > as given by Definition <A HREF="page521.html#defndigraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><UL><LI> Each element of <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" > is called a <em>vertex</em><A NAME=48556> </A> or a <em>node</em><A NAME=48558> </A> of <I>G</I>. Hence, <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" > is the set of <em>vertices</em> (or <em>nodes</em>) of <I>G</I>.<LI> Each element of <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" > is called an <em>edge</em><A NAME=48562> </A> or an <em>arc</em> of <I>G</I>. Hence, <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" > is the set of <em>edges</em> (or <em>arcs</em>) of <I>G</I>.<LI> An edge <IMG WIDTH=67 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70599" SRC="img2174.gif" > can be represented as <IMG WIDTH=44 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline70601" SRC="img2175.gif" >. An arrow that points from <I>v</I> to <I>w</I> is known as a <em>directed arc</em><A NAME=48567> </A><A NAME=48568> </A>. Vertex <I>w</I> is called the <em>head</em> of the arc because it is found at the arrow head. Conversely, <I>v</I> is called the <em>tail</em> of the arc. Finally, vertex <I>w</I> is said to be <em>adjacent</em><A NAME=48572> </A> to vertex <I>v</I>.<LI> An edge <I>e</I>=(<I>v</I>,<I>w</I>) is said to <em>emanate</em><A NAME=48574> </A><A NAME=48575> </A> from vertex <I>v</I>. We use notation <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70619" SRC="img2176.gif" > to denote the set of edges emanating from vertex <I>v</I>. That is, <IMG WIDTH=210 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70623" SRC="img2177.gif" ><LI> The <em>out-degree</em><A NAME=48577> </A><A NAME=48578> </A> of a node is the number of edges emanating from that node. Therefore, the out-degree of <I>v</I> is <IMG WIDTH=44 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70627" SRC="img2178.gif" ><LI> An edge <I>e</I>=(<I>v</I>,<I>w</I>) is said to be <em>incident</em><A NAME=48580> </A><A NAME=48581> </A> on vertex <I>w</I>. We use notation <IMG WIDTH=33 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70633" SRC="img2179.gif" > to denote the set of edges incident on vertex <I>w</I>. That is, <IMG WIDTH=214 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70637" SRC="img2180.gif" ><LI> The <em>in-degree</em><A NAME=48583> </A><A NAME=48584> </A> of a node is the number of edges incident on that node. Therefore, the in-degree of <I>w</I> is <IMG WIDTH=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70641" SRC="img2181.gif" ></UL><P>For example, Table <A HREF="page522.html#tblgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> enumerates the sets ofemanating and incident edgesand the in- and out-degreesfor each of the vertices in graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > shown in Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="48653"> </A><P> <A NAME="tblgraph1"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=5 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> vertex <I>v</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70619" SRC="img2176.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> out-degree </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=30 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70651" SRC="img2183.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> in-degree </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>a</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70655" SRC="img2184.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70657" SRC="img2185.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>b</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70661" SRC="img2186.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70663" SRC="img2187.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>c</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70667" SRC="img2188.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70669" SRC="img2189.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>d</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=50 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70673" SRC="img2190.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70675" SRC="img2191.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Emanating and incident edge sets for graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > in Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><P>There is still more terminology to be introduced,but in order to do that,we need the following definition:<P><BLOCKQUOTE> <b>Definition (Path and Path Length)</b><A NAME="defndigraphpath"> </A><P>A <em>path</em><A NAME=48601> </A> in a directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >is a non-empty sequence of vertices<P> <IMG WIDTH=320 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath70579" SRC="img2192.gif" ><P>where <IMG WIDTH=44 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline70679" SRC="img2193.gif" > for <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62857" SRC="img1057.gif" >such that <IMG WIDTH=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70683" SRC="img2194.gif" > for <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69881" SRC="img2128.gif" >.The <em>length</em> of path <I>P</I> is <I>k</I>-1.</BLOCKQUOTE><P>For example, consider again the graph <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > shown in Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Among the paths contained in <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" > there isthe path of length zero, <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66493" SRC="img1535.gif" >;the path of length one, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70697" SRC="img2195.gif" >;the path of length two, <IMG WIDTH=51 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66503" SRC="img1539.gif" >; and so on.In fact, this graph generates an infinite number of paths!(To see how this is possible,consider that <IMG WIDTH=200 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70701" SRC="img2196.gif" > is a path in <IMG WIDTH=17 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70643" SRC="img2182.gif" >).Notice too the subtle distinction between a path of length zero, say <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70705" SRC="img2197.gif" >,and the path of length one <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70707" SRC="img2198.gif" >.<P><HR><A NAME="tex2html7173" HREF="page523.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7171" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7165" HREF="page521.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7175" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -