📄 content-7-4.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF" background="IMAGE/Di.gif">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td>
<p style="line-height: 150%"><a name="content-7-4"></a>本节将介绍几种特殊图，包括：</p>
<p style="line-height: 150%" align="center"><a href="#content-7-4-2">二分图</a>、<a href="#content-7-4-1">平面图</a>、<a href="#五色问题">五色问题</a> </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%"> </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-4-2"></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>，结点集合 V 有两个子集V<sub>1</sub>,V<sub>2</sub>,满足V<sub>1<img border="0" src="image/bing.gif" width="14" height="14"></sub>V<sub>2</sub>=V,V<sub>1<img border="0" src="Image/jiao.gif" width="14" height="15"></sub>V<sub>2</sub>=<img border="0" src="Image/kong.gif" width="11" height="11">,且使
G 中的每一条边e={<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/shuyu.gif" width="13" height="11">V<sub>1
</sub>和 <img src="IMAGE/vj.gif" width="12" height="13"><img src="image/shuyu.gif" width="13" height="11">V<sub>2</sub>,即:同一各自集中的任意两个结点都不邻接,通常称
G 为<font color="#0000FF"><b>偶图或二分图</b></font>,其中,集合
V<sub>1</sub>
和 V<sub>2</sub>，称为图
G 的<b><font color="#0000FF">互补结点子集</font></b>。</p>
<p style="line-height: 150%"> G 也可以记为:G=<V<sub>1</sub>,E,V<sub>2</sub>></p>
<p style="line-height: 150%">显然，二分图 G 的每一条边都连通
V<sub>1</sub> 中的某一个结点与 V<sub>2</sub>
中的某一个结点。</p>
<p style="line-height: 150%">例如:</p>
<table border="1" width="100%">
<tr>
<td width="33%"><img border="0" src="Image/tu28.gif" width="161" height="92"></td>
<td width="33%"><img border="0" src="Image/tu_k33.gif" width="171" height="152"></td>
<td width="34%"><img border="0" src="Image/tu_k33a.gif" width="183" height="192"></td>
</tr>
</table>
<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></p>
<p style="line-height: 150%" > 二分图 G=<V<sub>1</sub>,E,V<sub>2</sub>>
中若 V<sub>1</sub>
的每个结点和 V<sub>2</sub>
的每个结点相邻接,反之亦然,则称 G 为完全二分图.</p>
<p style="line-height: 150%" > 若|V<sub>1</sub>|=m ,|V<sub>2</sub>|=n,则
G 可记为 <b>K</b><sub>mn</sub></p>
<p style="line-height: 150%" > 如:</p>
<table border="1" width="100%" height="25">
<tr>
<td width="50%" height="19">
<p align="center">K<sub>22</sub></p>
<p align="center"><img border="0" src="Image/tu29.gif" width="89" height="99"></td>
<td width="50%" height="19">
<p align="center">K<sub>33</sub></p>
<p align="center"><img border="0" src="Image/tu_k33.gif" width="171" height="152"></td>
</tr>
</table>
<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><a href="#content-7-1-1-wuxiangtu">无向图</a>
G=<V,E> 中的所有<a href="content-6-2-3.htm#content-6-2-3-tonggou">循环</a>的长度都为偶数,当且仅当
G 是一个二分图。</p>
<p style="line-height: 150%" ><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
匹配与最大匹配</b></p>
<p style="line-height: 150%" > 给定一个二分图 G=<V<sub>1</sub>,E,V<sub>2</sub>>
如果 E 的子集 M 中的边无公共端点，则称 M 为二分图 G
的一个<b><font color="#0000FF">匹配</font></b>，含有边数最多的匹配称为
G 的<b><font color="#0000FF">最大匹配</font>。</b></p>
<p style="line-height: 150%"> 如：某单位有7个工作{p1，p2，p3，p4，p5，p6，p7}，由10个人{a1，a2，…，a10}申请这7个工作，他们适合的工作分别是：</p>
<div align="center">
<center>
<table border="1" width="459">
<tr>
<td align="center" width="64">a1</td>
<td align="center" width="64">a2</td>
<td align="center" width="40">a3</td>
<td align="center" width="40">a4</td>
<td align="center" width="40">a5</td>
<td align="center" width="16">a6</td>
<td align="center" width="40">a7</td>
<td align="center" width="40">a8</td>
<td align="center" width="16">a9</td>
<td align="center" width="35">a10</td>
</tr>
<tr>
<td align="center" width="64">p1,p5,p6</td>
<td align="center" width="64">p2,p6,p7</td>
<td align="center" width="40">p3,p4</td>
<td align="center" width="40">p1,p5</td>
<td align="center" width="40">p6,p7</td>
<td align="center" width="16">p3</td>
<td align="center" width="40">p2,p3</td>
<td align="center" width="40">p1,p3</td>
<td align="center" width="16">p1</td>
<td align="center" width="35">p5</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%">如何安排工作使得没有工作的人数最少? </p>
<p style="line-height: 150%">作业:P271(4) </p>
<p style="line-height: 150%"><a href="#content-7-4">返回</a> </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%"> </p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%" align="center"><a name="content-7-4-1"></a><b><font size="5">平面图</font></b></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">
定义</b>：一个无向图 G=<V,E>,如果能把他图示在一平面上,他们的边除了结点以外没有任何交叉，则称图 G 是个平面图；否则，就是个非平面图。 </p>
<p style="line-height: 150%"> 把一个图"图示在一平面上",有时也称为"把平面图嵌入到一个平面" </p>
<p style="line-height: 150%">
例:交通道路、印刷电路等等。 </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">
平面图的判别</b></p>
<p style="line-height: 150%"><b>1、观察法</b></p>
<p style="line-height: 150%"><b>2、Euler公式法</b></p>
<p style="line-height: 150%"> <b><font color="#0000FF">平面图的区域(面)</font></b>四周为边所围成的最小平面块，称为平面图的区域。围成区域的回路称为<b><font color="#0000FF">区域的边界</font></b>，区域中有面积的部分称为<b><font color="#0000FF">有限区域</font></b>，没有面积的称为<b><font color="#0000FF">无限区域</font></b>。</p>
<p style="line-height: 150%">如：</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu30.gif" width="141" height="131"></p>
<p style="line-height: 150%" align="center">1，2，3为有限区域，4为无限区域</p>
<p style="line-height: 150%"> <b><font color="#0000FF">Euler公式</font></b>：若图
G=<V,E> 为一个(m,n)的连通平面图,它的区域数为 r
则必有:n-m+r=2.(可有数学归纳法证明)</p>
<p style="line-height: 150%">如:</p>
<div align="center">
<center>
<table border="1" width="253">
<tr>
<td width="143">
<p align="center"><img border="0" src="Image/tu31.gif" width="102" height="83"></td>
<td width="94">n=3<br>
m=3<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -