page526.html

wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq

<P>
    <A NAME="tblgraph1">&#160;</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_inline71425" SRC="img2292.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2292.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> out-degree </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71457" SRC="img2299.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2299.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=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71461" SRC="img2300.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2300.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71463" SRC="img2301.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2301.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=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71467" SRC="img2302.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2302.gif"  >       </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71469" SRC="img2303.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2303.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=89 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71473" SRC="img2304.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2304.gif"  > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=88 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71475" SRC="img2305.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2305.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=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71479" SRC="img2306.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2306.gif"  >       </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71481" SRC="img2307.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2307.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=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif"  > in Figure&nbsp;<A HREF="page525.html#figgraph1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html#figgraph1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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">&#160;</A>
<P>
A <em>path</em><A NAME=48834>&#160;</A> in a directed graph  <IMG WIDTH=72 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71355" SRC="img2282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2282.gif"  >
is a non-empty sequence of vertices
<P> <IMG WIDTH=321 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath71385" SRC="img2308.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2308.gif"  ><P>
where  <IMG WIDTH=43 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71485" SRC="img2309.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2309.gif"  > for  <IMG WIDTH=63 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63494" SRC="img1105.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1105.gif"  >
such that  <IMG WIDTH=89 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline71489" SRC="img2310.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2310.gif"  > for  <IMG WIDTH=63 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline70677" SRC="img2244.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2244.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=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif"  > shown in Figure&nbsp;<A HREF="page525.html#figgraph1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html#figgraph1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Among the paths contained in  <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif"  > there is
the path of length zero,  <IMG WIDTH=21 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67118" SRC="img1587.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1587.gif"  >;
the path of length one,  <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71503" SRC="img2311.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2311.gif"  >;
the path of length two,  <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67128" SRC="img1591.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1591.gif"  >; and so on.
In fact, this graph generates an infinite number of paths!
(To see how this is possible,
consider that  <IMG WIDTH=198 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71507" SRC="img2312.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2312.gif"  > is a path in  <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71449" SRC="img2298.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2298.gif"  >).
Notice too the subtle distinction between a path of length zero, say  <IMG WIDTH=21 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71511" SRC="img2313.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2313.gif"  >,
and the path of length one  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71513" SRC="img2314.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2314.gif"  >.
<P>
<HR><A NAME="tex2html8419" HREF="page527.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page527.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8417" HREF="page524.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page524.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8411" HREF="page525.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page525.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8421" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8422" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>