content-7-1.htm

实用的离散数学课件

                  G</td>
                <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu5.gif" width="189" height="180"><br>
                  G的生成子图</td>
              </tr>
              <tr>
                <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu6.gif" width="164" height="180"><br>
                  由E'导出的子图</td>
                <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu7.gif" width="115" height="173"><br>
                  由{v1,v2,v4}导出的子图</td>
              </tr>
            </table>
        </center>
      </div>
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp; <b>显然有</b></p>                                                        
      <blockquote>
        <ol>
          <li>
            <p style="line-height: 200%">生成子图的点集与原图相同,只是少了一些边,而V'的导出子图这是在原图中删去了一些点以及这些点所关联的边.</li>
          <li>
            <p style="line-height: 200%">图 G 的生成子图也是 G    
            的子图。</li> 
          <li> 
            <p style="line-height: 200%">如果 V'=V 和 E'=E，亦即 G 的生成子图                                                           
        G' 是图 G 的本身，则 G'也是 G 的子图。</li>   
          <li> 
            <p style="line-height: 200%">如果 V'=V，和 E'=<img src="image/kong.GIF" width="11" height="11">，亦即                                                           
        G' 是个零图，则生成子图 G' 也是 G 的子图。(上述的两种子图，都称作<b><font color="#0000FF">平凡子图</font></b>。)</li>  
        </ol>
      </blockquote>
      <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;                                                           
        的子图，并且给定另外一个图 G&quot;=&lt;V,E&quot;&gt;。如果有 E&quot;=E-E'，则相对于图 G 来说，称图 G&quot; 是子图 G'   
            的<b><font color="#0000FF">补图</font></b>。<br>                                                       
            若给定 G=&lt;V,E&gt;是完全图,这上述定义中称 G&quot;   
            为 G' 相对于完全图的 G 的补图。</td msimagelist> 
        </tr>
      </table msimagelist>
      <table border="1" width="85%">
        <tr>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu8.gif" width="139" height="138"><br>
          </td>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu9.gif" width="139" height="138"><br>
          </td>
          <td width="34%" valign="middle" align="center"><img border="0" src="Image/tu10.gif" width="139" height="138"><br>
          </td>
        </tr>
        <tr>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu_k5.gif" width="189" height="180"><br>
          </td>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu11.gif" width="190" height="180"><br>
          </td>
          <td width="34%" valign="middle" align="center"><img border="0" src="Image/tu12.gif" width="190" height="180"><br>
          </td>
        </tr>
        <tr>
          <td width="33%" valign="middle" align="center">　</td>
          <td width="33%" valign="middle" align="center"><img border="0" src="Image/tu_wujiaoxing.gif" width="169" height="168"></td>
          <td width="34%" valign="middle" align="center"><img border="0" src="Image/tu_wubianxing.gif" width="190" height="180"></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; 是两个无向图。从                                                           
        G 到 G'，如果存在一个从 V 到 V' 的双射g，又e'={g( <img src="IMAGE/vi.gif" width="10" height="11">),g( <img src="IMAGE/vj.gif" width="12" height="13">)}是图                                                           
        G' 中的一条边。当且仅当 e={ <img src="IMAGE/vi.gif" width="10" height="11">, <img src="IMAGE/vj.gif" width="12" height="13">}                                                           
        是图 G 中的一条边，那么就称图 G 同构于图 G'。 显然，如果 G 同构于 G'，则 G'必定同构于 G。因此可以说 G 和                                                           
        G'是互为<a name="content-7-1-3-tonggou"></a><b><font color="#0000FF">同构</font></b>的。<br>
            如上例中的对应关系为:g={&lt;a,v1&gt;,&lt;b,v4&gt;,&lt;c,v3&gt;,&lt;d,v2&gt;,&lt;e,v5&gt;}<br>
            边的对应关系:{a,c}-&gt;{v1,v3}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;   
            {c,e}-&gt;{v3,v5}<br>
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;   
            {e,b}-&gt;{v5,v4}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {b,d}-&gt;{v4,v2}<br>  
            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;   
            {d,a}-&gt;{v2,v1}<p style="line-height: 200%">其他同构图的例子
            <div align="center">
              <center>
              <table border="1" width="91%">
                <tr>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu_k4.gif" width="157" height="148"></td>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu_k4_2.gif" width="123" height="138"></td>
                </tr>
                <tr>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu_k33.gif" width="171" height="152"></td>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu_k33a.gif" width="183" height="192"></td>
                </tr>
                <tr>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu13.gif" width="97" height="118"></td>
                  <td width="50%" valign="middle" align="center"><img border="0" src="Image/tu14.gif" width="94" height="109"></td>
                </tr>
              </table>
              </center>
            </div>
          </td msimagelist>
        </tr>
      </table msimagelist>
      <blockquote>
        <p style="line-height: 200%">　</p>
        <p style="line-height: 200%">对于有向图而言,同构图不仅要点与点对应,边与边对应,而且对应边的方向也应相同,如:</p>
      </blockquote>
      <div align="center">
        <center>
        <table border="1" width="91%" height="128">
          <tr>
            <td width="33%" align="center" height="122"><img border="0" src="Image/tu15.gif" width="87" height="107"><br>
              (一)</td>
            <td width="33%" align="center" height="122"><img border="0" src="Image/tu16.gif" width="90" height="105"><br>
              (二)</td>
            <td width="34%" align="center" height="122"><img border="0" src="Image/tu17.gif" width="88" height="102"><br>
              (三)</td>
          </tr>
        </table>
        </center>
      </div>
      <blockquote>
        <p style="line-height: 200%">判断两个图同构的必要条件:(1)结点数相同,(2)边数相同,(3)同度数结点数相同,但是该条件不是充分条件.如:</p>
        <table border="1" width="90%" height="16">
          <tr>
            <td width="50%" height="10" align="center"><img border="0" src="Image/tu18.gif" width="135" height="176"></td>
            <td width="50%" height="10" align="center"><img border="0" src="Image/tu19.gif" width="135" height="173"></td>
          </tr>
        </table>
      </blockquote>
      <p style="line-height: 200%" align="left"  >　</p>                                                       
      <p style="line-height: 200%" align="left"  ><b><font color="#FF0000">思考题:</font></b></p>                                                       
      <p style="line-height: 200%" align="left"  ><b>&nbsp;&nbsp;&nbsp; </b>1、给一个K6的边涂上红色和蓝色，证明对于任何一种涂法，要么有一个红色的K3，要么有一个蓝色的K3。</p>                                                       
      <p style="line-height: 200%" align="left"  >&nbsp;&nbsp;&nbsp; 2、用（1）的结论证明6个人的人群中，或者有3个人相互认识，或者有3个人互相不认识。</p>                                                         
      <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%">&nbsp;</p>                                                       
      <p style="line-height: 200%">&nbsp;</p>                                                       
      <p style="line-height: 200%" align="center"><a name="content-7-1-3"></a><b>路径和循环</b></p>                                                       
      <p style="line-height: 200%"  >&nbsp;&nbsp;&nbsp; 本部分定义图中的两个重要概念：路径和循环。</p>                                                        
      <table border="0" cellpadding="0" cellspacing="0" width="100%" msimagelist>