离散数学 第11章 图的基本概念

《离散数学 第11章 图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论主讲:熊焕亮图论简介图论（graphtheory）是研究节点和边组成的图形的数学理论和方法，为离散数学的一个重要分支。图论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用边表示研究对象之间的某种特定关系。因此，图论可用节点和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题，已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等几乎所有学科领域的有关问题。图论与组合数学、线性规划、群论、矩阵论、概率论、数值分析等数学分支有密切的关系。2图论简介图论中的图是由若干给定的点及连接两点的线所构成

2、的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在瑞士数学家欧拉（LeonhardEular）1736年的论文中，解决了著名的哥尼斯保七桥问题。因此通常认为欧拉是图论的创始人。1845年，德国物理学家基尔霍夫为了解决一类线性联立方程组而创建“树”理论。他把电网络和其中的电阻、电容和电感等抽象化，用一个只有点和边组成的组合结构来代替电网络，而不指明每条边所代表的电器元件种类,这样就可以方便地对方程组

3、进行求解。1852年，格思里在对地图着色时发现,无论多么复杂的地图,只要用四种颜色就能将相邻区域区分开来。这就是所谓“四色猜想”。经过百余年的努力，直到1976年才由阿佩尔和赫肯借助电子计算机证明了四色定理。3图论简介1856年，哈密顿在给格雷夫斯的信中提出一个游戏：用正十二面体上20个顶点表示20个城市，要求游戏者沿着各边行走，走遍每个城市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究如何判断一个图有无这一性质，如果有，则又如何确定这样的路径，即称之为哈密顿图。这是一个至今尚未完全解决的问题。1962年，中国数学家管梅谷提出一个所谓“中国邮路问题”：邮递员带

4、着邮件从邮局出发，走遍他所管辖的每一条街道，最后回到邮局，如何选择路线，使走的路程最短。1967年，埃德蒙兹给出中国邮路问题一个好的解法。图论虽有200年的历史,但受计算机科学发展的刺激,发展极其迅速。上世纪60年代以来图论在各种学科领域中得到了广泛应用。图论在理论上也得到了新的发展，如图特等发展了拟阵理论，贝尔热等发展了超图理论，埃尔德什等发展了极图理论等。本书介绍图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用、二部图、匹配等。各章节主要知识点关联如图4.0.0所示。4图4.0.0第四部分各章节主要知识点关联

5、图图边集顶点集连通性同构性匹配性带权图平面图着色性关联矩阵邻接矩阵可达矩阵平面图的着色通路连通图二部图欧拉图哈密顿图树图的矩阵表示强连通图单向连通图弱连通图哈密顿通路哈密顿回路欧拉通路欧拉回路生成树森林根树有向性最小生成树最优树遍历二叉树中序行遍法前序行遍法后序行遍法Huffman算法简单图多重图边覆盖集无平行边，无环有平行边无向图有向图平凡图完全图正则图相邻可达回路支配集点独立集点覆盖集带权图基图5图的基本概念目录第十一章图的基本概念11.1图的概念11.1.2简单图、多重图和同构图11.1.3完全图和正则图11.1.4几种特殊的图11.1.5子图11.1.6图的操

6、作11.2图的连通性11.2.1通路与回路11.2.2连通图11.2.3二部图11.3图的矩阵表示11.3.1关联矩阵11.3.2邻接矩阵11.3.3可达矩阵11.4图的运算11.5欧拉图11.5.1欧拉通路和回路11.5.2半欧拉图和欧拉图11.5.3哥尼斯堡七桥问题11.6哈密顿图11.6.1哈密顿图11.6.2哈密顿图的充分条件11.7带权图11.8平面图11.8.1平面图的基本概念及性质11.8.2库拉托夫基定理11.8.3平面图着色及应用11.8.4边着色11.9应用举例*11.9.1中国邮路问题11.9.2冰箱分隔问题11.9.3排课表问题6第十一章图的基

7、本概念11.1图的概念现实世界中许多现象都可以用某种图形表示，这些图形由一些点和连接两点间的连线所组成，点表示事物，用点与点之间是否有连线表示事物之间是否有某种联系，这样构成的图形就是图论中的图。711.1图的概念11.1.1无向图和有向图定义11.1.1一个图是一个有序的二元组<>,记作,其中(1)是有限非空集合，称为顶点集,其元素称为顶点或结点。(2)是有限集合，称为边集,E中每个元素都有V中的结点对与之对应，称为边。定义11.1.1中的边e既可以是有向的,也可以是无向的。有向边与有序结点对对应,这时称u为e的起点,v为e的终点。无向边