-图的基本概念

《-图的基本概念》由会员分享，可在线阅读，更多相关《-图的基本概念（32页珍藏版）》请在金锄头文库上搜索。

1、,离散数学第七章 图 论,7-1 图的基本概念,7-2 路与回路,7-3 图的矩阵表示,7-4 欧拉图与哈密尔顿图,7-5 平面图,7-6 对偶图与着色,7-7 树与生成树,7-8 根树及其应用,绪论,图论的诞生哥尼斯堡七桥问题,从任意一点出发，经过每座桥恰好一次，再回到原点。,1736年，欧拉（Euler）解决了该问题图论诞生。,几个有名的图论问题,四色猜想 莫比乌斯（ Mbius ）于1840年提出：对地图上的每个国家着色，使得任意相邻的两个国家着不同的颜色，猜想：只需要四种颜。阿佩尔和哈肯（Appel，Haken）于1976借助计算机花费1200小时证明了该猜想。,中国邮递员问题,管梅谷

2、与1960年提出： 一个邮递员，每次送信必须从邮局出发，走遍他所投递的区域内的所有街道，最终回到邮局。问：怎样使他所走的路最短。哥尼斯堡七桥问题：每条边走恰好一次；中国邮递员问题：每条边可以走多次。,哈密尔顿图,戏) 求解 问题 1859年爱尔兰数学家威廉哈密尔顿（Sir William Hamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游抽象为图论问题哈密尔顿给出了肯定回答

3、，该问题的解是存在的,哈密尔顿回路(圈)哈密尔顿图,运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题,旅行售货员问题,给出城市之间的距离，一位售货员从某一城市出发，经过每个城市恰好一次，然后回到出发的城市，要求他所走的路经最短。 美国数学家威特涅与1934年在普林斯顿的一个讨论班上提出。该问题在理论和应用上都很有价值，迄今有很多论文研究该问题。,图论及其在计算机科学中的应用例子,图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用。 在计算机科学领域，如数据结构、语言、算法、数据库、

4、操作系统、人工智能、网络理论、开关理论等方面，图论扮演着重要的角色。如： 数据结构中的图、树 数据库中的网状模型 计算机网络中的环网络、星形网络等 算法设计与分析、人工智能 并行计算机中的多处理器互连网络（Multiprocessor Interconnection Network） 无线传感器网络（Wireless Sensor Network） ,多处理器互连网络,一个多处理器互连网络可用一个图G=（V，E）表示，其中V中的每个顶点v表示一个处理器，E中的每条边表示处理器之间的链路（Hard-link）。 应用：并行计算机中若干个处理器连接的方式。 例：n维超立方体Q_n=(V,E): V

5、中每个顶点表示为一个长度为n的二进制串，E中两个顶点之间有一条边当且仅当它们只有一位不同。顶点个数2n，边数：n2n-1。超立方体性并行机：CM-2，nCUBE，IPSC-860，SGI Origin 2000。,IBM的蓝色基因/L（Bluegene/L）：65536个处理器，Torus网络结构运算速度：2005年IBM的蓝色基因以每秒钟计算280万亿次浮点运算；2007年每秒钟计算一千万亿次浮点运算每秒蝉联冠军宝座(Roadrunner)。 超级计算机的应用：石油勘探、天气、天文、生物等方面。,第七章 图论-绪论,图论起源于智力游戏的难题研究，如哥尼斯堡七桥问题、迷宫问题、匿门博奕问题、四

6、色猜想问题、汉密尔顿（环游世界）、棋盘上马的行走线路问题等。,图论的第一篇论文,1736年欧拉发表的，阐述了解决哥尼斯堡七桥问题的思想。 欧拉享有“图论之父”之称。,1847年克希霍夫利用图论分析电路网络中的电流问题。,图论起源,图论应用于工程技术问题的首篇论文,7-1 图的基本概念,一、图的定义,三、几个基本概念,四、结点度数的 几个基本定理,五、子图与补图,六、图的同构,第七章 图 论,7-1 图的基本概念-定义,图的定义（定义7-1.1）一个图是一个三元组，其中V(G)是一个非空的 结点集合， E(G)是边集合, G 是从边集合E到结点无序偶（或有序偶）集合上的函数。,例1 无向图,例2

7、 有向图,例3 混合图,若把图中的边ei看作总是与两个结点关联，那么一个图亦可 记为G=，其中V是非空结点集，E是连接结点的边集。,7-1 图的基本概念目录,若边ei与结点无序偶(vj,vk)相关联，则称该边为无向边。,若边ei与结点有序偶相关联，则称该边为有向边，其中yj为起点，yk为终点。,例1 G=，其中V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6, G(e1)=(a,b), G(e2)=(a,c), G(e3)=(b,d), G(e4)=(b,c), G(e5)=(d,c), G(e6)=(a,d)。,返回,无向图-图中每一条边为无向边。,7-1 图的基本概

8、念-定义,例2 G=，其中V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6, G(e1)=, G(e2)=,G(e3)=, G(e4)=, G(e5)=, G(e6)=。,返回,有向图-图中每一条边为有向边。 (一般地： ),7-1 图的基本概念-定义,返回,混合图-图中一些边为有向边，一些边为无向边。 例 3,7-1 图的基本概念-定义,7-1 图的基本概念-几个基本概念,边与两个结点关联,邻接点,无向边 有向边 平行边,邻接边,环（或自回路）,简单图 多重图 完全图,孤立结点 零图 平凡图,结点的度数,7-1 图的基本概念,若G(e)=(a,b),或G(e) =,则

9、称边e与两个结点a,b关联。例如，e1关联于结点a，b，e2关联于结点v1，v2。,邻接点-由一条有向（或无向）边关联的结点称为邻接点。如图，a，b互为邻接点，v1与v2邻接。,环或自回路-关联于同一结点的一条边。,孤立结点-在一个图中不与任何结点相邻接的结点。,零图仅由孤立结点组成的图称为零图。 平凡图仅由一个孤立结点构成的图称为平凡图。,几个基本概念,7-1 图的基本概念-几个基本概念,邻接边-关联于同一结点的多条边。例如，e1,e2,e6互为邻接边。,平行边-连接于同一对结点间的多条边称为平行边。如果是有向边要求方向一致。,多重图-含有平行边的图称为多重图。,简单图不含平行边和环的图。,

10、a,b,c,几个基本概念,7-1 图的基本概念-几个基本概念,完全图(无向图)-在简单图中，若每一对不同结点间都有边相连，则称该图为完全图。有n个结点的无向完全图记作Kn 。如果在Kn中，给每条边任意确定一个方向，就称该图 为n个结点的有向完全图。,7-1 图的基本概念-几个基本概念,几个基概念,完全图的性质（定理7-1.4）n个结点的无向完全图Kn的边数为：n(n-1)/2。 定理7-1.4证明：,结点的度数（定义7-1.2 ）在图G=，与结点v关联的边数，称作是该 结点的度数，记作deg(v)。 图G=的最大度(G)=maxdeg(v)|vV(G),图 G=的最小度(G)=mindeg(v

11、)|vV(G)。,有向图中结点的度数（定义7-1.3 ）在有向图中，射入一个结点的边数称为该结点的入度，由一个结点射出的边数称为该结点的出度。结点的出度与入度之和就是该结点的度数。,7-1 图的基本概念-几个基本概念,定理7-1.1 （握手定理） 每个图中，所有结点度数的总和等于边数的两倍，即deg (v) = 2|E| vV 证明：因为每条边必关联两个结点，而一条边给于 关联的每个结点的度数为1。因此在一个图中，结 点度数的度数的总和等于边数的两倍。,返回几个定理,7-1 图的基本概念-几个定理,定理7-1.2 在任何图中，度数为奇数的结点必定为偶数个。 证明：设V1和V2分别是G中奇数和偶

12、数度数的结点集，则由定 理7-1.1，有deg(v) +deg(v) = deg(v) = 2|E| vV1 vV2 vV 由于deg(v) 是偶数之和，必为偶数，而2|E| 是偶数，vV2 故得deg(v)是偶数，即| V1 | 是偶数。vV1,返回几个定理,7-1 图的基本概念-几个定理,定理7-1.3 在任何有向图中，所有结点的入度之和等于所 有结点的出度之和。 证明：因为每一条有向边必对应一个入度和一个出度，若 一个结点具有一个入度或出度，则必关联一条有向边。 所以，有向图中各结点入度之和等于边数，各结点出度 之和也等于边数，因此，任何有向图中，入度之和等于 出度之和。,返回几个定理,

13、7-1 图的基本概念-几个定理,定理7-1.4 n个结点的无向完全图Kn的边数为 n(n-1)/2 。 证明：在Kn中，任意两个结点间都有边相连，n个结点中 任取两点的组合数为：Cn2= n(n-1)/2 故Kn的边数为：|E|= n(n-1)/2 。,返回,7-1 图的基本概念-几个定理,子图 （定义7-1.7 ）设图G=，若有一个图G=满足VV且EE, 则称G为G的子图。 例如: 下图中(b)，(c)都是(a)的子图。,7-1 图的基本概念-子图,返回,图G相对于完全图的补图 （定义7-1.6 ）给定一个图G，由G中所有结点和所有能使G成为完全 图的添加边组成的图，称为G的相对于完全图的补

14、图，或 简称为G的补图，记作G。 例如：,子图G的相对于图G的补图（定义7-1.8 ）设G=是G=的一个子图，若给定另外一个图 G”=使得E”=E-E，且V”中仅包含E”的边所关联的结点，则称G”是子图G的相对于图G的补图。例如：,7-1 图的基本概念-补图,返回7-1,图G相对于完全图的补图 (定义7-1.6 ) 给定一个图G，由G中所有结点和所有能使G称为完全 图的添加边组成的图，称为G的相对于完全图的补图，或 简称为G的补图，记作G。 例如：,7-1 图的基本概念-补图,返回,子图G的相对于图G的补图 （定义7-1.8 ）设G= 是图G=的子 图，若给定另外一个图 G”=使得E”=E-E

15、，且V”中仅包含E”的边所关联的结点，则称G”是子图G的相对于图G的补图。 例如：图(c)是图(b)相对于图(a)的补图。图(b)不是 图(c)相对于图(a)的补图。,7-1 图的基本概念-补图,返回,图的同构（定义7-1.9）设图G=及图G=，如果存在双射 g: vi vi，使得e=(vi,vj)(或)是G的一条边当且仅当 e=(g(vi),g(vj) (或)是G的一条边，则称G与G同构，记作GG。,7-1 图的基本概念-图的同构,G与G同构的充要条件： 两个图的结点和边分别存在一一对应，且保持关联关系。,两个图同构的必要条件： 1、结点数目相同； 2、边数相等； 3、度数相同的结点数相等。,例如：,7-1 图的基本概念,7-1 图的基本概念-图的同构,图(a)与(b)是同构的。图 (c)与(d)是同构的。,同构的定义,导出子图：设G=(V,E)是一个图，E是E的子集。以E为边集，E中的边所关联的结点的全体为结点集所得到的G的子图，称为由E导出的G的子图，记为GE 。 设V是V的子集，以V为结点集，端点均在V中的边的全体为边集所得到的G的子图，称为由V导出的G的子图，记为GV 。,