📄 content-7-1.htm
字号:
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">路径的定义</font></b>：给定有向图 G 中的任何一个边序列，如果其中的任何一条边的终点都是继之出现的边(如果存在的话)的始点，则称这样的边的序列是图
G 的<b><font color="#0000FF"><a name="content-7-1-3-lujing"></a>路径</font></b>。
<br>
<b>
相关概念：</b>
<ol>
<li>
<p style="line-height: 200%">路径中的边的条数，称为<b><font color="#0000FF">路径的长度</font></b>。</li>
<li>
<p style="line-height: 200%">在有向图中，若路径序列中的各条边全都是互不相同的，称为此路径为<b><font color="#0000FF">简单路径</font></b>。</li>
<li>
<p style="line-height: 200%">在有向图中，穿程路径序列中的每一个结点仅出现一次的路径，称为<a name="content-7-1-3-jibenlujing"></a><b><font color="#0000FF">基本路径</font></b>。</li>
<li>
<p style="line-height: 200%">基本路径一定是简单路径,简单路径不一定是基本路径</li>
<li>
<p style="line-height: 200%"><b>定理</b>,无向图中的路径为基本路径当且仅当该路径中的结点有两个度数为1,其余度数均为2.<br>
</li>
</ol>
</td msimagelist>
</tr>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">回路的定义</font></b>：在有向图 G 中，起始和终止于同一个结点的路径，称为<a name="content-7-1-3-xunhuan"></a><b><font color="#0000FF">循环或回路</font></b>。<br>
相关概念：
<ol>
<li><p style="line-height: 200%">在一个循环中，如果它的每条边在构成循环的路径上都仅出现一次(端点结点除外)，亦即它的路径是简单的，则称此循环为<b><font color="#0000FF">简单循环</font></b>。</li>
<li><p style="line-height: 200%">在一个循环中，如果它的每个结点在构成循环的路径上都仅出现一次，亦即它的路径是基本的，则称此循环为<a name="content-7-1-3-jibenxunhuan"></a><b><font color="#0000FF">基本循环</font></b>。</li>
<li><p style="line-height: 200%">应该说明,在循环中,甚至在基本循环中,从路径的观点看,作为始点的结点至少会出现两次。</li>
</ol>
</td msimagelist>
</tr>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%">
<p style="line-height: 200%">定理1：设 G=<V,E> 是一个简单有向图，并且有
|V|=n，于是应有：<br>
(1) 任何基本路径的长度,都小于或等于 n-1。<br>
(2) 任何基本循环的长度,都不超过 n。<br>
(3) 如果从 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
存在路径,则必定存在一条基本路径.<br>
(4) 如果从 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
存在回路,则必定存在一条基本回路. <br>
</td msimagelist>
</tr>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">可达</font></b>定义：设 G=<V,E>
是一个简单有向图，并且有结点 <img src="IMAGE/vi.gif" width="10" height="11">, <img src="IMAGE/vj.gif" width="12" height="13"><img src="image/shuyu.gif" width="13" height="11">V，从结点
<img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
如果存在任何一条路径的话，则称从结点 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
是<b><font color="#0000FF">可达</font></b>的。</td msimagelist>
</tr>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">距离</font></b>定义：从结点 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
如果是可达的，则从 <img src="IMAGE/vi.gif" width="10" height="11">
到 <img src="IMAGE/vj.gif" width="12" height="13">
的长度为最短的路径通常称为测地线，测地线的长度称为<b><font color="#0000FF">距离</font></b>，并记作 d<<img src="IMAGE/vi.gif" width="10" height="11">,<img src="IMAGE/vj.gif" width="12" height="13">>。<br>
<br>
例:"人鸡狗米"问题的<a href="Image/tu_rjgm.gif" target="_blank">解决</a>.</td msimagelist>
</tr>
</table msimagelist>
<p style="line-height: 200%" align="center">
<p style="line-height: 200%" align="right"><a href="#content-7-1">返回</a> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%" align="center"><b><a name="content-7-1-4"></a>图的连通性</b></p>
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">无向图连通性</font></b>：在无向图G=<V,E>中,如果任何两个结点 <img src="IMAGE/vi.gif" width="10" height="11">, <img src="IMAGE/vj.gif" width="12" height="13"><img src="image/shuyu.gif" width="13" height="11">V
都是相互可达的.则称此无向图 G 是<a name="content-7-1-4-liantong"></a><b><font color="#0000FF">连通的</font></b>。 </td msimagelist>
</tr>
<tr msimagelist>
<td valign="baseline" width="42" msimagelist><img src="Image/gif/bluered.gif" width="12" height="12"></td>
<td valign="top" width="100%"><p style="line-height: 200%"><b><font color="#0000FF">有向图连通性</font></b>：设 G=<V,E> 是一个简单有向图，<br>
(1)
如果把有向图作为无向图来对待时是连通的，则称这个有向图是<a name="content-7-1-4-ruoliantong"></a><b><font color="#0000FF">弱连通的</font></b>。<br>
(2) 在图 G 中的任何结点偶对中，如果至少从一个结点到另一个结点是可达的，则称
G 是<b><font color="#0000FF">单向连通的</font></b>。<br>
(3) 对于图 G 中的任何结点偶对中，如果两个结点都是相互可达的，则称 G
是<b><font color="#0000FF">强连通的</font></b>。</td msimagelist>
</tr>
</table msimagelist>
<div align="center">
<center>
<table border="1" width="86%">
<tr>
<td width="33%" align="center"><img border="0" src="Image/tu22.gif" width="101" height="98"><br>
强连通</td>
<td width="33%" align="center"><img border="0" src="Image/tu20.gif" width="101" height="98"><br>
单侧连通</td>
<td width="34%" align="center"><img border="0" src="Image/tu21.gif" width="101" height="97"><br>
弱连通</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 200%">
<table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>
<li>
<p style="line-height: 200%">定义3：设 G=<V,E> 是一个简单有向图，且 G'是 G 的子图。对于某一种性质来说，如果再没有包含子图
G'的子图具有给定的性质，则称子图 G'是相对于该性质的极大子图。</li>
<li>
<p style="line-height: 200%">定义4：设 G=<V,E> 是一个简单有向图，<br>
(1) G 的极大强连通子图，称为图 G 的<b><font color="#0000FF">强分图</font></b>；<br>
(2) G 的极大单向连通子图，称为图 G 的<b><font color="#0000FF">单向分图</font></b>；<br>
(3) G 的极大弱连通子图，称为图 G 的<b><font color="#0000FF">弱分图</font></b>。.</li>
</table msimagelist>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%" align="right"><a href="#content-7-1">返回</a> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
</td>
</tr>
</table>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 200%"> </p>
<p style="line-height: 150%"> </p><p align="right"><b><a href="contentFrame-mulu.htm"><<back</a></b>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -