📄 content-7-2.htm
字号:
<!-- saved from url=(0022)http://internet.e-mail -->
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<style type="text/css">
<!--
.unnamed1 { font-size: 9pt; line-height: 17pt}
.unnamed2 { font-size: 10pt; font-weight: bold}
-->
</style>
</head>
<body bgcolor="#FFFFFF" background="IMAGE/Di.gif">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="100%">
<p style="line-height: 150%" align="center" ><a name="content-7-2"><br>
</a><b><font size="5">图的矩阵表示</font></b> </p>
<p style="line-height: 150%" > 任给一个图G,G中的结点<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">的一条路径?有怎样找出一条最短路径?</p>
<p style="line-height: 150%" >
要解决这些问题我们第一个想法就是将图形画出来,再在图形中找,但是当图形比较复杂时,就难免有疏漏,所以我们希望用计算机来帮助我们查找,这就要将图形存储到计算机中,也就要用到图形的矩阵表示.</p>
<p style="line-height: 150%" > 本节介绍图的两种矩表示方法，它们分别是：</p>
<p style="line-height: 150%" align="center" ><a href="#关联矩阵">关联矩阵</a>、<a href="#content-7-2-1">邻接矩阵</a></p>
<p style="line-height: 150%" >两种表示方法具有内在的联系，可以互相转化。</p>
<p style="line-height: 150%" >在此基础上介绍图的<a href="#content-7-2-2">可达性矩阵</a>及图的<font color="#0000FF"><a href="#最短路径问题">最短路径问题</a></font>.</p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%" align="center"><a name="关联矩阵"><b><font size="5">关联矩阵</font></b></a></p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定义:</b>设 G=<V,E> 是一个简单无向图,且为(n,m)图,A=<img border="0" src="Image/aij_nm.gif" width="44" height="17">为G的关联矩阵,其中:</p>
<div align="center">
<center>
<table border="0" width="46%" cellspacing="0" cellpadding="0" height="47">
<tr>
<td width="21%" rowspan="2" valign="middle" align="center" height="47"><img border="0" src="Image/aij.gif" width="15" height="13">=<font size="6"><b>{</b></font></td>
<td width="79%" height="23">0, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="Image/ej.gif" width="12" height="13">不关联</td>
</tr>
<tr>
<td width="79%" height="24">1, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="Image/ej.gif" width="12" height="13">关联</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%">如:构造下图的关联矩阵</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu23.gif" width="198" height="153"></p>
<p style="line-height: 150%">则:</p>
<div align="center">
<table border="0" width="61%">
<tr>
<td width="18%" align="center">
<p align="right">A=</td>
<td width="82%" align="center">
<p align="left"><textarea rows="8" name="S1" cols="38"></textarea></td>
</tr>
</table>
</div>
<p style="line-height: 150%" align="left"> 在该矩阵中有: , </p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs1.gif" width="98" height="39">
<b>即,矩阵中第i行元素的和=第i个结点的度数.</b></p>
<p style="line-height: 150%" align="center"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定义:</b>设 G=<V,E> 是一个简单有向图,且为(n,m)图,A=<img border="0" src="Image/aij_nm.gif" width="44" height="17">为G的关联矩阵,其中:</p>
<div align="center">
<center>
<table border="0" width="46%" cellspacing="0" cellpadding="0" height="20">
<tr>
<td width="21%" rowspan="3" valign="middle" align="center" height="67"><img border="0" src="Image/aij.gif" width="15" height="13">=<b><font size="7">{</font></b></td>
<td width="79%" height="23">-1, 若<img src="IMAGE/vi.gif" width="10" height="11">为<img border="0" src="Image/ej.gif" width="12" height="13">的终点</td>
</tr>
<tr>
<td width="79%" height="22">0, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="Image/ej.gif" width="12" height="13">不关联</td>
</tr>
<tr>
<td width="79%" height="1">1, 若<img src="IMAGE/vi.gif" width="10" height="11">为<img border="0" src="Image/ej.gif" width="12" height="13">的起点</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%">如:构造下图的关联矩阵</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu24.gif" width="206" height="161"></p>
<p style="line-height: 150%">则:</p>
<div align="center">
<table border="0" width="61%">
<tr>
<td width="18%" align="center">
<p align="right">A=</td>
<td width="82%" align="center">
<p align="left"><textarea rows="8" name="S1" cols="38"></textarea></td>
</tr>
</table>
</div>
<p style="line-height: 150%">在该矩阵中有: , </p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs2.gif" width="59" height="37">
即,<b>矩阵中第i行中"1"的个数=第i个结点的出度.</b></p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs3.gif" width="79" height="39">
即,<b>矩阵中第i行中"-1"的个数=第i个结点的入度.</b></p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%" align="center" ><a name="content-7-2-1"></a><b><font size="5">邻接矩阵</font></b></p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
定义:</b>设图 G=<V,E>为(n,m)图,A=<img border="0" src="Image/aij_nn.gif" width="42" height="17">为G的邻接矩阵,其中:</p>
<div align="center">
<center>
<table border="0" width="46%" cellspacing="0" cellpadding="0" height="47">
<tr>
<td width="21%" rowspan="2" valign="middle" align="center" height="47"><img border="0" src="Image/aij.gif" width="15" height="13">=<font size="6"><b>{</b></font></td>
<td width="79%" height="23">0, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="IMAGE/vj.gif" width="12" height="13">不相邻</td>
</tr>
<tr>
<td width="79%" height="24">1, 若<img src="IMAGE/vi.gif" width="10" height="11">与<img border="0" src="IMAGE/vj.gif" width="12" height="13">相邻</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%">如:构造下图的邻接矩阵</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu25.gif" width="198" height="158"></p>
<p style="line-height: 150%">则:</p>
<div align="center">
<table border="0" width="61%">
<tr>
<td width="18%" align="center">
<p align="right">A=</td>
<td width="82%" align="center">
<p align="left"><textarea rows="8" name="S1" cols="38"></textarea></td>
</tr>
</table>
</div>
<p style="line-height: 150%">在该矩阵中有: </p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs4.gif" width="83" height="39">
<b>即:矩阵中所有"1"的个数=图的边数 m </b></p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs6.gif" width="98" height="39">
<b>即:矩阵中第i行中"1"的个数=第i个结点的出度.</b></p>
<p style="line-height: 150%" align="left"> <img border="0" src="Image/gs5.gif" width="101" height="37">
<b>即:矩阵中第i列中"1"的个数=第i个结点的入度.</b></p>
<p style="line-height: 150%" align="left"><b> 对角元素等于"1",表示在该点上有自回路.</b></p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%">
对于上述矩阵我们做矩阵的乘法,设 </p>
<blockquote>
<div align="left">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -