page525.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 60 行
HTML
60 行
<HTML><HEAD><TITLE>Undirected 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="tex2html7206" HREF="page526.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7204" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7198" HREF="page524.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7208" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016105000000000000000">Undirected Graphs</A></H3><P>An undirected graph is a graph in which the nodes are connected by<em>undirected arcs</em><A NAME=48779> </A><A NAME=48780> </A>.An undirected arc is an edge that has no arrow.Both ends of an undirected arc are equivalent--there is no head or tail.Therefore, we represent an edge in an undirected graphas a set rather than an ordered pair:<P><BLOCKQUOTE> <b>Definition (Undirected Graph)</b><A NAME="defngraph"> </A>An <em>undirected graph</em><A NAME=48785> </A><A NAME=48786> </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 sets. Each element of <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif" > is a set that is comprised of exactly two (distinct) vertices. 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 undirected graph <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70795" SRC="img2216.gif" >comprised of four vertices and four edges:<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray48792" SRC="img2217.gif" ><P>The graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70797" SRC="img2218.gif" > can be represented<em>graphically</em> as shown in Figure <A HREF="page525.html#figgraph3"><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 linesthat connect associated vertices.<P><P><A NAME="48921"> </A><A NAME="figgraph3"> </A> <IMG WIDTH=575 HEIGHT=136 ALIGN=BOTTOM ALT="figure48796" SRC="img2219.gif" ><BR><STRONG>Figure:</STRONG> An undirected graph.<BR><P><P>Notice that because an edge in an undirected graph is a set, <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70801" SRC="img2220.gif" >,and since <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline70803" SRC="img2221.gif" > is also a set,it cannot contain more than one instance of a given edge.Another consequence of Definition <A HREF="page525.html#defngraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is that there cannot be anedge from a node to itself in an undirected graphbecause an edge is a set of size twoand a set cannot contain duplicates.<P><HR><A NAME="tex2html7206" HREF="page526.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7204" HREF="page520.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7198" HREF="page524.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7208" 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 + -
显示快捷键?