离散数学邱晓红电子教案 第11章.pptVIP

图 论 主讲:熊焕亮 图论简介 图论（graph theory）是研究节点和边组成的图形的数学理论和方法，为离散数学的一个重要分支。图论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用边表示研究对象之间的某种特定关系。因此，图论可用节点和边组成的图形及其有关的理论和方法来描述、分析和解决各种实际问题，已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等几乎所有学科领域的有关问题。图论与组合数学、线性规划、群论、矩阵论、概率论、数值分析等数学分支有密切的关系。 图论简介 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在瑞士数学家欧拉（Leonhard Eular）1736年的论文中，解决了著名的哥尼斯保七桥问题。因此通常认为欧拉是图论的创始人。 1845年，德国物理学家基尔霍夫为了解决一类线性联立方程组而创建“树”理论。他把电网络和其中的电阻、电容和电感等抽象化，用一个只有点和边组成的组合结构来代替电网络，而不指明每条边所代表的电器元件种类,这样就可以方便地对方程组进行求解。 1852年，格思里在对地图着色时发现,无论多么复杂的地图,只要用四种颜色就能将相邻区域区分开来。这就是所谓“四色猜想”。经过百余年的努力，直到1976年才由阿佩尔和赫肯借助电子计算机证明了四色定理。 图论简介 1856年，哈密顿在给格雷夫斯的信中提出一个游戏：用正十二面体上20个顶点表示20个城市，要求游戏者沿着各边行走，走遍每个城市一次且仅一次，最后回到原出发城市。这个游戏促使人们研究如何判断一个图有无这一性质，如果有，则又如何确定这样的路径，即称之为哈密顿图。这是一个至今尚未完全解决的问题。 1962年，中国数学家管梅谷提出一个所谓“中国邮路问题”：邮递员带着邮件从邮局出发，走遍他所管辖的每一条街道，最后回到邮局，如何选择路线，使走的路程最短。1967年，埃德蒙兹给出中国邮路问题一个好的解法。 图论虽有200年的历史,但受计算机科学发展的刺激,发展极其迅速。上世纪60年代以来图论在各种学科领域中得到了广泛应用。图论在理论上也得到了新的发展，如图特等发展了拟阵理论，贝尔热等发展了超图理论，埃尔德什等发展了极图理论等。 本书介绍图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用、二部图、匹配等。各章节主要知识点关联如图4.0.0所示。 图4.0.0第四部分各章节主要知识点关联图 图的基本概念目录 第十一章 图的基本概念 11.1 图的概念 11.1.2 简单图、多重图和同构图 11.1.3 完全图和正则图 11.1.4 几种特殊的图 11.1.5 子图 11.1.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.1 图的概念 现实世界中许多现象都可以用某种图形表示，这些图形由一些点和连接两点间的连线所组成，点表示事物，用点与点之间是否有连线表示事物之间是否有某种联系，这样构成的图形就是图论中的图。 11.1 图的概念 11.1.1 无向图和有向图 定义11.1.1 一个图是一个有序的二元组 ,记作 ,其中 (1) 是有限非空集合，称为顶点集,其元素称为顶点或结点。 (2) 是有限集合，称为边集,E中每个元素都有 V中的结点对与之对应，称为边。 定义11.1.1中的边 e既可以是有向的,也可以是无向的。有向边与有序结点对 u,v对应,这时称 u为e的起点, v为e的终点。无向边与无序结点对(u,v)对应, u,v称为 e的两个端点。 (3)将图的集合定义转化成图形表示之后，常用 表示图的边 ， 称顶点或边用字母标定的图为标定图，否则称为非标定图。 (4)将有向图各有向边均改成无向边后的无向图称为原有向图的基图。 (5)若一条边连接同一个点，称其为圈。 11.1 图的概念 (6)若 ， ,则通常称它为（p,q）图。p称为图G的阶,（1，0）图称为平凡图