📄 page521.html
字号:
<HTML><HEAD><TITLE>Directed Graphs</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="tex2html7162" HREF="page522.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7160" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7154" HREF="page520.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7164" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016101000000000000000">Directed Graphs</A></H3><P>We begin with the definition of a directed graph:<P><BLOCKQUOTE> <b>Definition (Directed Graph)</b><A NAME="defndigraph"> </A>A <em>directed graph</em><A NAME=48129> </A><A NAME=48130> </A>,or <em>digraph</em><A NAME=48253> </A>,is an ordered pair <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > with the following properties:<OL><LI> The first component, <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" >, is a finite, non-empty set. The elements of <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" > are called the <em>vertices</em> of <I>G</I>.<LI> The second component, <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" >, is a finite set of ordered pairs of vertices. That is, <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline70559" SRC="img2169.gif" >. The elements of <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" > are called the <em>edges</em> of <I>G</I>.</OL></BLOCKQUOTE><P>For example, consider the directed graph <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70565" SRC="img2170.gif" >comprised of four vertices and six edges:<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray48138" SRC="img2171.gif" ><P>The graph <I>G</I> can be represented<em>graphically</em> as shown in Figure <A HREF="page521.html#figgraph1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The vertices are represented by appropriately labeled circles,and the edges are represented by arrowsthat connect associated vertices.<P><P><A NAME="48548"> </A><A NAME="figgraph1"> </A> <IMG WIDTH=575 HEIGHT=136 ALIGN=BOTTOM ALT="figure48142" SRC="img2172.gif" ><BR><STRONG>Figure:</STRONG> A directed graph.<BR><P><P>Notice that because the pairs that represent edges are <em>ordered</em>,the two edges (<I>a</I>,<I>c</I>) and (<I>c</I>,<I>a</I>) are distinct.Furthermore, since <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70575" SRC="img2173.gif" > is a mathematical set,it cannot contain more than one instance of a given edge.And finally, an edge such as (<I>d</I>,<I>d</I>) may connect a node to itself.<P><HR><A NAME="tex2html7162" HREF="page522.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7160" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7154" HREF="page520.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7164" 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 + -