content-7-1.htm

实用的离散数学课件

              &nbsp;<img border="0" src="Image/tu_k4_2.gif" width="123" height="138">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;         
              <img border="0" src="Image/tu_k5.gif" width="189" height="180"></li>      
            <li>      
              <p style="line-height: 200%">含有平行边的图，称为<a name="content-7-1-1-duochongbiantu"></a><font color="#0000FF"><b>多重边图</b></font>。</li>      
            <li>      
              <p style="line-height: 200%">在图 G 中，如果没有闭路和平行边，则称图 G 是个<a name="content-7-1-1-jiandantu"></a><font color="#0000FF"><b>简单图</b></font>。</li>        
            <li>      
              <p style="line-height: 200%">给每一条边都指定了权的图，称为<font color="#0000FF"><b>有权图</b></font>。</li>      
            <li>      
              <p style="line-height: 200%">在一个图中，不与任何边相联的结点，称为孤立结点。仅包含孤立结点的图，称为<font color="#0000FF"><b>零图</b></font>，并可说成是个                                                           
        (n,0) 图。</li>         
            <li>       
              <p style="line-height: 200%">在一个图中，如果仅有一个孤立结点，则称它为<font color="#0000FF"><b>平凡图</b></font>，并可表示成(1,0)图。</li>      
            <li>      
              <p style="line-height: 200%">每个结点都具有同样次数 d 的无向图，称为 d         
              次<font color="#0000FF"><b>正则无向图</b></font>。<br>      
              &nbsp; <img border="0" src="Image/tu_k4_2.gif" width="123" height="138">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;   
              <img border="0" src="Image/tu_k5.gif" width="189" height="180"></li>     
          </ol>     
          </td msimagelist>
        </tr>
      </table msimagelist>
      <p style="line-height: 200%">&nbsp;</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%">一个基本性质：</td msimagelist>
        </tr>
      </table msimagelist>
      <blockquote> 
        <ol> 
          <li> 
            <p style="line-height: 200%"><b>定理(握手定理)：<br>
            &nbsp;&nbsp;&nbsp; </b>设                                                           
        G=&lt;V,E&gt; 是一个 (n,m) 无向图，其中的结点集合 V={ <img src="IMAGE/v1.gif" width="11" height="11">, <img src="IMAGE/v2.gif" width="12" height="11">,....<img src="IMAGE/vn.gif" width="12" height="11">}                                                           
        于是应有 <img src="Image/woshou.gif" v:shapes="_x0000_i1025" width="102" height="37">.</li>      
          <li>    
            <p style="line-height: 200%">有向图中所有结点的入度之和等于出度之和.</li>   
          <li>   
            <p style="line-height: 200%">任意图中一定有偶数个度数为奇数的结点.　</li>
        </ol>
      </blockquote>
      <p style="line-height: 200%" align="right"><a href="#content-7-1"  >返回</a></p>                                                  
      <p style="line-height: 200%">&nbsp;</p>                                                  
      <p style="line-height: 200%">　</p>                                                 
      <p style="line-height: 200%">　</p>                                                 
      <p style="line-height: 200%">　</p>                                                 
      <p style="line-height: 200%">&nbsp;</p>                                                 
      <p style="line-height: 200%" align="center"><b><a name="content-7-1-2">图的运算、</a>子图、图的同构</b> </p>                                                 
      <p style="line-height: 200%"  >&nbsp;&nbsp;&nbsp;     
      本部分先介绍图的运算，再引入子图，在此基础上定义补图，最后介绍两个图之间的同构关系。</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">图的运算 <img border="0" src="Image/bing.gif" width="14" height="14">、<img border="0" src="Image/jiao.gif" width="14" height="15">、-、删边、删点</font></b><br>  
          图中的点集、边集都是集合，所以可以在图上定义一些集合的运算。<br>  
          设G1=&lt;V1,E1&gt;,G2=&lt;V2,E2&gt;</td msimagelist>
        </tr>
      </table msimagelist>
      <blockquote>  
      <ol>  
        <li>  
          <p style="line-height: 200%">G3=&lt;V3,E3&gt;=G1<img border="0" src="Image/bing.gif" width="14" height="14">G2,其中     
          V3=V1<img border="0" src="Image/bing.gif" width="14" height="14">V2,E3=E1<img border="0" src="Image/bing.gif" width="14" height="14">E2</li>  
        <li>  
          <p style="line-height: 200%">G3=&lt;V3,E3&gt;=G1<img border="0" src="Image/jiao.gif" width="14" height="15">G2,其中     
          V3=V1<img border="0" src="Image/jiao.gif" width="14" height="15">V2,E3=E1<img border="0" src="Image/jiao.gif" width="14" height="15">E2</li>  
        <li>  
          <p style="line-height: 200%">G3=&lt;V3,E3&gt;=G1-G2,其中     
          E3=E1-E2,V3=(V1-V2)<img border="0" src="Image/bing.gif" width="14" height="14">{E3中所关联的边}</li>  
        <li>  
          <p style="line-height: 200%">删边:直接删除该边即可.</li>  
        <li>  
          <p style="line-height: 200%">删点:删去该点以及与该点所关联的所有的边.</li>  
      </ol>  
      </blockquote>  
      <p style="line-height: 200%">例:设G1=&lt;V1,E1&gt;,G2=&lt;V2,E2&gt;如下图</p>  
      <div align="center">  
        <center>  
        <table border="0" width="83%" cellspacing="0" cellpadding="0" height="53">  
          <tr>  
            <td width="50%" valign="middle" align="center" height="35">  
              <p align="center"><img border="0" src="Image/tu_k2.gif" width="112" height="121"></td>  
            <td width="50%" valign="middle" align="center" height="35">  
              <p align="center"><img border="0" src="Image/tu1.gif" width="151" height="118"></td>  
          </tr>  
          <tr>  
            <td width="50%" valign="middle" align="center" height="18">G1</td>  
            <td width="50%" valign="middle" align="center" height="18">G2</td>  
          </tr>  
        </table>  
        </center>  
      </div>  
      <p>  
        
      则: 
       
      <table border="0" width="100%" cellspacing="0" cellpadding="0"> 
        <tr> 
          <td width="33%" valign="middle" align="center">　<img border="0" src="Image/tu2.gif" width="149" height="129"></td>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu3.gif" width="112" height="121"></td>
          <td width="34%" valign="middle" align="center"><img border="0" src="Image/tu4.gif" width="112" height="121"></td>
        </tr>
        <tr>
          <td width="33%" valign="middle" align="center">G1<img border="0" src="Image/bing.gif" width="14" height="14">G2</td>
          <td width="33%" valign="middle" align="center">G1<img border="0" src="Image/jiao.gif" width="14" height="15">G2</td>
          <td width="34%" valign="middle" align="center">G1-G2</td>
        </tr>
      </table>
            <p style="line-height: 200%">　
            <p style="line-height: 200%">　
      <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=&lt;V,E&gt; 和 G'=&lt;V',E'&gt; 是两个图。    
            <ol>  
              <li><p style="line-height: 200%">如果有 V'<img src="image/baohan.gif" width="11" height="10">                                                           
        V 和 E'<img src="image/baohan.gif" width="11" height="10">                                                           
        E,则称 G'是图 G 的<b><font color="#0000FF">子图</font></b>。</li>   
              <li><p style="line-height: 200%">如果有 V'<img src="image/baohan.gif" width="11" height="10">V                                                           
        和 E'<img src="image/baohan.gif" width="11" height="10">                                                           
        E,并且有 E'<img src="image/budeng.GIF" width="14" height="14">E，则称                                                           
        G' 是图 G 的<b><font color="#0000FF">真子图</font></b>。</li>   
              <li><p style="line-height: 200%">如果有 V'=V 和 E'<img src="image/baohan.gif" width="11" height="10">                                                           
        E，则称 G'是图 G 的<b><font color="#0000FF">生成子图</font></b>。</li>   
              <li><p style="line-height: 200%">如果G'是图 G 的子图,且G'中没有孤立点,G'由E'唯一确定,称G'是<b><font color="#0000FF">由E'导出的子图</font></b>.(即:边集E'及E'中的边所关联的点所构成的图)</li>  
              <li><p style="line-height: 200%">如果有 V'<img src="image/baohan.gif" width="11" height="10">                                                           
        V 和以两端均在V'中的所有的边为E'构成的G的子图称为<b><font color="#0000FF">由V'岛出的子图</font></b>.</li>  
            </ol>
          </td msimagelist>
        </tr>
      </table msimagelist>
            <p style="line-height: 200%">&nbsp; 如:  
      <div align="center">
        <center>
            <table border="1" width="87%">
              <tr>
                <td width="33%" valign="middle" align="center">　<img border="0" src="Image/tu_k5.gif" width="189" height="180"><br>