📄 page560.html
字号:
<HTML><HEAD><TITLE>Connectedness of a Directed Graph</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="tex2html7597" HREF="page561.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7595" HREF="page558.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7589" HREF="page559.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7599" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0016342000000000000000">Connectedness of a Directed Graph</A></H3><P>When dealing with directed graphs,we define two kinds of connectedness, <em>strong</em> and <em>weak</em>.Strong connectedness of a directed graph is defined as follows:<P><BLOCKQUOTE> <b>Definition (Strong Connectedness of a Directed Graph)</b><A NAME="defngraphsstrongcon"> </A>A directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > is <em>strongly connected</em><A NAME=50937> </A><A NAME=50938> </A>if there is a path in <I>G</I> between every pair of vertices in <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif" >.</BLOCKQUOTE><P>For example, Figure <A HREF="page560.html#figgraph10"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the directed graph <IMG WIDTH=84 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71325" SRC="img2314.gif" > given by<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray50941" SRC="img2315.gif" ><P>Notice that the graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71327" SRC="img2316.gif" > is <em>not</em> connected!For example, there is no path from any of the vertices in <IMG WIDTH=54 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline71329" SRC="img2317.gif" >to any of the vertices in <IMG WIDTH=51 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66503" SRC="img1539.gif" >.Nevertheless, the graph ``looks'' connectedin the sense that it is not made of up of separate partsin the way that the graph <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71301" SRC="img2311.gif" > in Figure <A HREF="page559.html#figgraph9"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is.<P>This idea of ``looking'' connectedis what <em>weak connectedness</em> represents.To define weak connectedness we need to introduce firstthe notion of the undirected graph that underlies a directed graph:Consider a directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" >.The underlying undirected graph is the graph <IMG WIDTH=73 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline71337" SRC="img2318.gif" > where <IMG WIDTH=12 HEIGHT=17 ALIGN=BOTTOM ALT="tex2html_wrap_inline71339" SRC="img2319.gif" > represents the set of undirected edges that is obtainedby removing the arrowheads from the directed edges in <I>G</I>:<P> <IMG WIDTH=382 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath71317" SRC="img2320.gif" ><P><P><P><A NAME="51109"> </A><A NAME="figgraph10"> </A> <IMG WIDTH=575 HEIGHT=294 ALIGN=BOTTOM ALT="figure50950" SRC="img2321.gif" ><BR><STRONG>Figure:</STRONG> An weakly connected directed graph and the underlying undirected graph.<BR><P><P>Weak connectedness of a directed graph is definedwith respect to its underlying, undirected graph:<P><BLOCKQUOTE> <b>Definition (Weak Connectedness of a Directed Graph)</b>A directed graph <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif" > is <em>weakly connected</em><A NAME=51115> </A><A NAME=51116> </A>if the underlying undirected graph <IMG WIDTH=12 HEIGHT=17 ALIGN=BOTTOM ALT="tex2html_wrap_inline71349" SRC="img2322.gif" > is connected.</BLOCKQUOTE><P>For example,since the undirected graph <IMG WIDTH=19 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline71351" SRC="img2323.gif" > in Figure <A HREF="page560.html#figgraph10"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is connected,the directed graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71327" SRC="img2316.gif" > is <em>weakly connected</em>.Consider what happens when we remove the edge (<I>b</I>,<I>e</I>)from the directed graph <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71327" SRC="img2316.gif" >.The underlying undirected graph that we get is <IMG WIDTH=19 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71301" SRC="img2311.gif" > in Figure <A HREF="page559.html#figgraph9"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Therefore,when we remove edge (<I>b</I>,<I>e</I>) from <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline71327" SRC="img2316.gif" >,the graph that remains is neither strongly connected nor weakly connected.<P><HR><A NAME="tex2html7597" HREF="page561.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7595" HREF="page558.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7589" HREF="page559.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7599" 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 + -