📄 content-7-3.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-3"></a>本节简单介绍在图论发展史上的两个著名的图：</p>
<p style="line-height: 150%" align="center" > <a href="#content-7-3-1">欧拉图</a>、<a href="#content-7-3-2">哈密尔顿图</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-3-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>，且图中无孤立点，于是：<br>
(1)经过图 G 中的每条边一次且仅一次的路径，定义为该图
G 的欧拉路径； <br>
(2)经过图 G 中的每条边一次且仅一次的循环，定义为该图
G 的欧拉循环；<br>
(3)具有欧拉循环的图，称为欧拉图。</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 中的每一个结点都具有偶次数，当且仅当图
G 是个欧拉图。</p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
性质2</b>：在连通 无向图 G 中，只有两个结点 <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/vj.gif" width="12" height="13">
的路径是条欧拉路径。</p>
<p style="line-height: 150%">这两个性质有利于我们进行欧拉图，欧拉路径的判断。</p>
<p style="line-height: 150%">例如：</p>
<table border="1" width="100%">
<tr>
<td width="33%" align="center"><img border="0" src="Image/euler.gif" width="155" height="167"></td>
<td width="33%" align="center"><img border="0" src="Image/tu34.gif" width="124" height="123"></td>
<td width="34%" align="center"><img border="0" src="Image/tu35.gif" width="124" height="123"></td>
</tr>
<tr>
<td width="33%" align="center"><img border="0" src="Image/tu36.gif" width="162" height="161"></td>
<td width="33%" align="center"><img border="0" src="Image/tu37.gif" width="124" height="199"></td>
<td width="34%" align="center"><img border="0" src="Image/tu38.gif" width="124" height="123"></td>
</tr>
</table>
<p style="line-height: 150%" align="right"> </p>
<p style="line-height: 150%"><b><img border="0" src="Image/gif/bluered.gif" width="12" height="12">
性质3：</b>设 G 是个弱连通有向图，于是应有：<br>
(1) G 中的每个结点的入度都等于出度，当且仅当 G 拥有一个欧拉循环；<br>
(2)除了两个结点之外，其他的每个结点的入度都等于出度，当且仅当 G 具有欧拉路径。对于这两个结点而言，一个结点的入度比出度多一，而另一个结点的入度比出度少一。<br>
</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> </b>将旋转鼓的表面分成8块扇形，如图，图中阴影部分表示用导电材料制成，空白区域表示用绝缘材料制成，终端a,b,c接另外一个电极，电路通或不通分别用0、1表示，因此，鼓的位置可以用二进制信号来表示，问如何选取这8个扇区的材料，使没转过一个扇形所得到的二进制信号不通。</p>
<div align="center">
<center>
<table border="1" width="95%">
<tr>
<td width="50%">
<p align="center"><img border="0" src="Image/bruijn.gif" width="197" height="194"></td>
<td width="50%">
<p align="center"><img border="0" src="Image/bruijn_tu.gif" width="195" height="250"></td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%" align="left" >
每装过一个扇形，信号 a1a2a3 变成了
a2a3a4，前者的右两位决定了后者的左两位，因此我们用所有两位二进制数作为结点，从每个定点
a1a2 到 a2a3引一条有向边表示 a1a2a3
这个3为二进制数，作出表示所有可能的变换码的有向图如图所示。</p>
<p style="line-height: 150%" align="left" >
原问题转化为在这个有向图中，求一条欧拉回路，这个有向图有4个顶点的度数都是出度、入度各为2，所以存在这样的欧拉回路。如：000、001、010、101、011、111、110、100、000；省略路径中重复的部分即可得到布鲁英序列：00010111。</p>
<p style="line-height: 150%" align="left" >
类似地，我们可以定义任何n个二进制位构成的<img border="0" src="Image/2den.gif" width="13" height="12">个二进制数的布鲁英序列。</p>
<p style="line-height: 150%" align="right" ><a href="#content-7-3">返回</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%" align="center"><a name="content-7-3-2"><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>给定一个</a>无向图
G=<V,E>，于是：<br>
(1)经过图 G 中的每个结点一次且仅一次的路径，定义为该图
G 的哈密尔顿路径；<br>
(2)经过图 G 中的每个结点一次且仅一次的循环，定义为该图
G 的哈密尔顿循环；<br>
(3)具有哈密尔顿循环的图，称为哈密尔顿图。 </p>
<p style="line-height: 150%">显然，每一个哈密尔顿图都必定是个连通无向图。 </p>
<p style="line-height: 150%">
哈密尔顿图的判断条件较为复杂，而且到目前为止没有一个好判断的充分必要条件。 </p>
<p style="line-height: 150%"> 如： </p>
<table border="1" width="100%">
<tr>
<td width="33%" align="center"><img border="0" src="Image/tu35.gif" width="124" height="123"></td>
<td width="33%" align="center"><img border="0" src="Image/20chenshi.gif" width="195" height="166"></td>
<td width="34%" align="center"><img border="0" src="Image/tu8.gif" width="139" height="138"></td>
</tr>
</table>
<p style="line-height: 150%" > </p>
<p style="line-height: 150%" ><b>应用：</b>五个队进行循环赛，要求每个队不再接连的两场比赛中，问是否可以安排？</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">
Hamilton回路的推广（推销员问题）</b></p>
<p style="line-height: 150%" align="center"><img border="0" src="Image/tu39.gif" width="199" height="179"></p>
<p style="line-height: 150%"> 为了找出权重总和最小的哈密尔顿回路,我们介绍<b>最邻近法</b>,这种方法得到的解不一定是最优解,但是一个比较好的解,而且方法非常简单.</p>
<p style="line-height: 150%"><b>算法:</b></p>
<blockquote>
<p style="line-height: 150%">(1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.<br>
(2)
找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.<br>
(3) 重复(2)直到所有的结点都加入到路径中.<br>
(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.</p>
</blockquote>
<div align="center">
<center>
<table border="1" width="482">
<tr>
<td colspan="2" align="center" width="472"><img border="0" src="Image/tu39.gif" width="199" height="179"></td>
</tr>
<tr>
<td align="center" width="238"><img border="0" src="Image/tu40.gif" width="203" height="168"></td>
<td align="center" width="228"><img border="0" src="Image/tu41.gif" width="221" height="175"></td>
</tr>
</table>
</center>
</div>
<p style="line-height: 150%" > </p>
<p style="line-height: 150%" > </p>
<p style="line-height: 150%" ><a href="#content-7-3" target="_self">返回</a></p>
</td>
</tr>
</table>
<p style="line-height: 150%"> </p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -