content-7-2.htm

实用的离散数学课件

      <table border="0" cellspacing="0" cellpadding="0" height="91">     
        <tr>     
          <td rowspan="4" height="91">     
            <p align="right"><b>A<sup>2</sup>=A<img border="0" src="Image/cheng.gif" width="13" height="14">A=</b></td>     
          <td rowspan="4" height="91">     
            <p align="center"><b><img border="0" src="Image/kuohao_l.gif" width="10" height="113"></b></p>    
          </td>    
          <td height="28" align="center"><b>0</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>0</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img src="Image/kuohao_r.gif" width="11" height="113"></b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img border="0" src="Image/cheng.gif" width="13" height="14"></b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img border="0" src="Image/kuohao_l.gif" width="10" height="113"></b></td>    
          <td height="28" align="center"><b>0</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>0</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img src="Image/kuohao_r.gif" width="11" height="113"></b></p>    
          </td>    
          <td rowspan="4" height="91">    
            <p align="center"><b>=</b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img border="0" src="Image/kuohao_l.gif" width="11" height="113"></b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>0</b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img src="Image/kuohao_r.gif"  width="12" height="113"></b></p>    
          </td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
        </tr>    
      </table>    
      </div>   
      <div align="left">   
      <table border="0" cellspacing="0" cellpadding="0" height="91">     
        <tr>     
          <td rowspan="4" height="91">     
            <p align="right"><b>A<sup>3</sup>=A</b><b><sup>2</sup></b><b><img border="0" src="Image/cheng.gif" width="13" height="14">A=</b></td>     
          <td rowspan="4" height="91">    
            <p align="center"><b><img border="0" src="Image/kuohao_l.gif" width="11" height="113"></b></td>    
          <td height="28" align="center"><b>0</b></td>    
          <td height="28" align="center"><b>2</b></td>    
          <td height="28" align="center"><b>1</b></td>    
          <td height="28" align="center"><b>2</b></td>    
          <td rowspan="4" height="91">    
            <p align="center"><b><img src="Image/kuohao_r.gif"  width="12" height="113"></b></p>    
          </td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
          <td height="29" align="center"><b>1</b></td>    
        </tr>    
        <tr>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>1</b></td>    
          <td height="29" align="center"><b>0</b></td>    
        </tr>    
      </table>    
      </div>   
      </blockquote>   
      <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>                                           
      <p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">     
      定理1</b>：设 G=&lt;V,E&gt; 是一个简单有向图，并且 A 是 G 的邻接矩阵，对于                                               
        m=1,2,3,...来说，矩阵 A<sup>m</sup>中的第i行第j列的元素的值，等于从  <img src="IMAGE/vi.gif" width="10" height="11">                                               
        到  <img src="IMAGE/vj.gif" width="12" height="13">                                               
        长度为 m 的路径数目。</p>                                              
      <p style="line-height: 150%"  ><a href="#content-7-2">返回</a></p>                                            
      <p style="line-height: 150%">&nbsp;</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"><font size="5"><a name="#content-7-2-2"></a><b>可达性矩阵</b></font></p>                                        
      <p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12"> 
      定义</b> 若设 B=A+A<sup>2</sup>+…+A<sup>m</sup>，其中元素 <img border="0" src="Image/bij.gif" width="14" height="17">      
      表示 <img src="IMAGE/vi.gif" width="10" height="11"> 到 <img border="0" src="IMAGE/vj.gif" width="12" height="13">      
      所有长度不超过m的路径的条数。令R=<img border="0" src="Image/rij_nn.gif" width="38" height="17">,其中 </p>                                             
      <div align="center">      
        <center>      
        <table border="0" width="40%" cellspacing="0" cellpadding="0" height="47">      
          <tr>      
            <td width="21%" rowspan="2" valign="middle" align="center" height="47"><img border="0" src="Image/rij.gif" width="12" height="13">=<font size="6"><b>{</b></font></td>      
            <td width="79%" height="23">0, <img border="0" src="Image/bij.gif" width="14" height="17">=0</td>      
          </tr>      
          <tr>      
            <td width="79%" height="24">1, <img border="0" src="Image/bij.gif" width="14" height="17"><img border="0" src="Image/buden.gif" width="8" height="8">0</td>      
          </tr>      
        </table>      
        </center>      
      </div>      
      <p style="line-height: 150%">则,若<img border="0" src="Image/rij.gif" width="12" height="13"><img border="0" src="Image/buden.gif" width="8" height="8">0表示      
      <img src="IMAGE/vi.gif" width="10" height="11"> 到 <img border="0" src="IMAGE/vj.gif" width="12" height="13">      
      可达,反之表示 <img src="IMAGE/vi.gif" width="10" height="11"> 到 <img border="0" src="IMAGE/vj.gif" width="12" height="13">