📄 content-7-4.htm
字号:
r=2<br>
n-m+r=2</td>
</tr>
<tr>
<td width="143">
<p align="center"><img border="0" src="Image/tu32.gif" width="82" height="102"></td>
<td width="94">n=8<br>
m=11<br>
r=5<br>
n-m+r=2</td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%"> <b><font color="#0000FF">判别条件(必要条件)</font></b>:设图
G 是一个(n,m)简单连通平面图(n>2),则必有:m <img border="0" src="Image/xiaodeng.gif" width="9" height="10">
3n-6 .<br>
证明(略)</p>
<p style="line-height: 150%">如:K<sub>5</sub>:n=5,m=10,
3n-6=15-6=9<10,所以 K<sub>5</sub> 不是平面图.</p>
<p style="line-height: 150%"> K<sub>33</sub>:n=6,m=9,3n-6=12>9,满足条件,但不可确定.</p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> <b><font color="#0000FF">推论</font></b>:若每个面有至少4条边围成的任何连通平面图中,必有
2n-4 <img border="0" src="Image/dadeng.gif" width="9" height="10"> m.</p>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"><b>3、库拉托夫斯基定理</b></p>
<p style="line-height: 150%"> <b><font color="#0000FF">库拉托夫斯基图</font></b>：K<sub>5</sub><sub>，</sub>K<sub>33</sub>为库拉托夫斯基图（不是平面图）。</p>
<p style="line-height: 150%"> <b><font color="#0000FF">二度结点内同构</font></b>：设 G1
和
G2
是两个无向图。如果 G1
和
G2
是同构的，或者是通过反复插入和(或)删除次数为二的结点，能够把
G1
和
G2
转化成同构的图，则称 G1
和 G2 在二度结点内同构，也称<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/tu31.gif" width="102" height="83">
<img border="0" src="Image/TU33.gif" width="82" height="102"></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> 对偶图求法：（D过程）</b></p>
<blockquote>
<p style="line-height: 150%">
(1) 将平面图 G 嵌入平面；<br>
(2) 对 G 的每一个面 D<sub>i</sub> 内部做一个点,作为对偶图的结点
v'<sub>i</sub>;<br>
(3) 若两个面 D<sub>i</sub> 和 D<sub>j</sub> 有一条公共边界
ek,则一条边 e'<sub>k</sub>={v'<sub>i</sub>,v'<sub>j</sub>}与e<sub>k</sub>相交;<br>
(4) 若 e<sub>k</sub> 是 D<sub>i</sub> 唯一的边界,则在v'<sub>i</sub>上存在一条自回路.</p>
</blockquote>
<p style="line-height: 150%"><b>例:</b>画出下图的对偶图</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu42.gif" width="240" height="139"></p>
<p style="line-height: 150%">显然,原图中的每条边与对偶图中的每条边相对应;<br>
原图中的每个面与对偶图中的每个点相对应.<br>
G'是G的对偶图当且仅当G是G'的对偶图.</p>
<p style="line-height: 150%">注意:原图的位置不同所得到的对偶图不一定相同.<br>
</p>
<table border="1" width="100%">
<tr>
<td width="50%" align="center"><img border="0" src="Image/tu43.gif" width="125" height="87"></td>
<td width="50%" align="center"><img border="0" src="Image/tu44.gif" width="157" height="126"></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">
割集</b></p>
<p style="line-height: 150%"> G为无向图,满足下列条件的边的集合称为G的<b><font color="#0000FF">割集:</font></b></p>
<blockquote>
<p style="line-height: 150%">(1) 把这个集合中的所有的边删去,将增加连通分图的个数;<br>
(2)
把这个集合中的任何真子集从G中删去则不会由此效果.</p>
</blockquote>
<p style="line-height: 150%">如:</p>
<div align="center">
<center>
<table border="1" width="89%">
<tr>
<td width="50%" align="center"><img border="0" src="Image/tu42.gif" width="240" height="139"></td>
<td width="50%" align="center"><img border="0" src="Image/tu44.gif" width="157" height="126"></td>
</tr>
</table>
</center>
</div>
<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">
<a name="五色问题">五色问题</a></b></p>
<p style="line-height: 150%"> 四色问题:在画地图时,只用4种颜色就可以把任意复杂的地图划分成不同的区域,而且任意两个相邻的区域颜色不同.</p>
<p style="line-height: 150%"> 利用对偶图,可以把地图着色问题转化为对其<b><font color="#0000FF">对偶图的结点的着色问题</font></b>.如果没有两个邻接的结点的颜色相同,就成为给地图<b><font color="#0000FF">正常着色</font></b>.</p>
<p style="line-height: 150%">
四色问题比较难证明,而且没有一般的简单方法,而对于五色问题,证明起来相当简单.</p>
<p style="line-height: 150%"> <b>引理:</b>在平面连通的简单图中至少有一个顶点v<sub>0</sub>的度数deg(v<sub>0</sub>)<img border="0" src="Image/xiaodeng.gif" width="9" height="10">5.</p>
<p style="line-height: 150%">证明:(反证法证明)设每个结点的度数都不小于6,且G为(n,m)图,<br>
G为平面图,所以 3n-6 <img border="0" src="Image/dadeng.gif" width="9" height="10">
m 成立.<br>
而,<img border="0" src="Image/woshou.gif" width="102" height="37">,<br>
所以:6n-12 <img border="0" src="Image/dadeng.gif" width="9" height="10">
2m <img border="0" src="Image/dadeng.gif" width="9" height="10"> 6n<br>
矛盾.</p>
<p style="line-height: 150%"> <b>定理:</b>用5种颜色可以给任意一个平面简单连通图
G=<V,E> 正常着色</p>
<p style="line-height: 150%">证明:对结点作归纳法</p>
<p style="line-height: 150%"> 1、当n <img border="0" src="Image/xiaodeng.gif" width="9" height="10">
5 结论显然成立. </p>
<p style="line-height: 150%"> 2、假设 n-1
个结点时成立,现证明 n 个结点时,</p>
<p style="line-height: 150%"> 有引理知,G
中至少有一个顶点v<sub>0</sub>的度数deg(v<sub>0</sub>)<img border="0" src="Image/xiaodeng.gif" width="9" height="10">5,在图中删去
v<sub>0 </sub>得图G',此时G'中有n-1个结点,有假设,可以正常着色.然后将v<sub>0</sub>加到图中,有两种情况:<br>
(1) deg(v<sub>0</sub>)<5,或者deg(v<sub>0</sub>)=5,但是和v<sub>0</sub>邻接的结点的颜色数小于5,则v<sub>0</sub>极易着色,只要与周围结点着不同颜色即可.<br>
(2) deg(v<sub>0</sub>)=5,且和v<sub>0</sub>邻接的结点的颜色数等于5,如图,设称图中所有着色为红色和黄色的结点为<b>红黄集,</b>所有着色为黑色和白色的结点为<b>黑白集</b>;又有两种情况:</p>
<p style="line-height: 150%" align="center"> <img border="0" src="Image/tu45.gif" width="204" height="185"></p>
<p style="line-height: 150%"> (a) v1 和 v4
属于红黄集导出子图的两个不同的分图中,如图,将v1所在的分图中的所有点的红色和黄色对调一下,并不改变该分图的正常着色,在给v0着红色,即可得到
G 的正常着色.</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu46.gif" width="468" height="216"></p>
<p style="line-height: 150%"><br>
(b) v1 和 v4
属于红黄集导出子图的同一个分图中,如图,则必然存在一条由红黄集中的结点加上
v0 构成的回路 C ,该回路把黑白集分成两个子集,一个在C
中,一个在C 外,所以又回到(a)情况,用(a)的方法处理,即可正常着色.</p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu47.gif" width="275" height="233"></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%"><a href="#content-7-4">返回</a> </p>
</td>
</tr>
<tr>
<td> </td>
</tr>
</table>
<p style="line-height: 150%"> </p>
<p style="line-height: 150%"> </p><p align="right"><b><a href="contentFrame-mulu.htm"><<back</a></b>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -