📄 content-7-0.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<style type="text/css">
</head>
<body bgcolor="#FFFFFF" background="IMAGE/di.gif">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td>
<p style="line-height: 150%" align="center"><b><font size="4">第四章 引言</font></b></p>
<p style="line-height: 150%"><font>图论具有十分广泛的应用，其内容也十分丰富。本章首先介绍一些图论的基本概念，然后介绍两种图的矩阵表示方法。最后介绍了一些比较重要的特殊图，包括欧拉图、哈密顿图以及平面图、树等等。</font></p>
</td>
</tr>
</table>
<p style="line-height: 150%"> </p>
</body>
<p style="line-height: 150%"> </p><p align="right"><b><a href="contentFrame-mulu.htm"><<back</a></b></body></html>
</head>
</style>
</head>
<body background="IMAGE/di.gif">
<p align="center" style="line-height: 200%"><font size="5"><b>图论</b></font></p>
<p style="line-height: 200%">
图论是数学的一个分支,近年来得到迅速的发展,已广泛地应用于计算机科学的各个领域中,成为重要的工具.</p>
<p style="line-height: 200%"><b>图论的例子</b></p>
<ul>
<li>
<p style="line-height: 200%"><b>哥尼斯堡七桥问题</b></li>
</ul>
<p style="line-height: 200%">
十八世纪东普鲁士的哥尼斯堡城位于普雷格尔河畔,有一处如下图的地形:</p>
<p align="center" style="line-height: 200%"> <img src="Image/7qiaotu.gif" width="274" height="127"></p>
<p align="left" style="line-height: 200%">
当地的居民茶余饭后可以到小岛上散散步,有一天城中一位居民提出了这样的一个问题,若有人从4块陆地总的任一块出发,按怎么样的路线才能够做到每座桥通过一次而且仅一次,最后回到原地,问题看起来不难但却没有人能做得到.</p>
<p align="left" style="line-height: 200%"> 著名数学家Euler在研究这个问题时将这个问题抽象成一个数学问题,将4块陆地抽象成4个点,陆地与陆地之间的桥梁变成点与点之间的连线,于是7桥问题变成图论中的一个图的遍历问题,</p>
<p align="center" style="line-height: 200%"><img border="0" src="Image/7qiao1.gif" width="146" height="167"><br>
(Euler图)</p>
<p align="left" style="line-height: 200%">
从任意一个点出发,经过每一条边一次而且仅一次,最后回到出发点的路径是否存在.</p>
<p align="left" style="line-height: 200%"> </p>
<ul>
<li>
<p align="left" style="line-height: 200%"><b>哈密尔顿问题</b></li>
</ul>
<p align="left" style="line-height: 200%">
一个正十二面体,有20个顶点,面与面之间的交界线就是顶点的连线,设想这20个顶点代表世界上的20个城市,顶点间的连线就是城市间的交通线路,问旅游者从某个城市出发,到其余19个城市旅游一次而且仅一次,返回到原地的路线是怎样的?</p>
<p align="left" style="line-height: 200%">
这个问题就称为哈密尔顿问题,即:从一个点出发经过所有的点一次而且仅一次,最后回到起点的路径是否存在.</p>
<p align="center" style="line-height: 200%"><img src="Image/20chenshi.gif" width="195" height="166"></p>
<ul>
<li>
<p style="line-height: 200%"><b>计算机网络问题</b></li>
<li>
<p style="line-height: 200%"><b>地图四色问题</b></li>
</ul>
<p style="line-height: 200%"> </p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -