第10节图的基本概念.pptVIP

例如：G=(V, E)如图所示, 其中 V={v1, v2, …,v5} E={{v1,v2}, {v1,v5}, {v2,v3},{v2,v5}, {v4,v5}} 例如： G=(V, E)如图所示, 其中 V={v1, v2, …,v5} E={{v1,v1}, {v1,v2}, {v2,v3}, {v2,v3}, {v2,v5}, {v1,v5}, {v4,v5}} 相关概念 相关概念 例如： D=(V, A)如图所示, 其中：V={a, b, c, d} A={(a,b), (a,d), (c,c), (c,d), (d,c) } (1),(2),(3)是(1)的子图; (2),(3)是真子图; (1),(3)是(1)的生成子图. 图(2)是{d,e,f }的导出子图, 也是{e5, e6, e7}导出子图. k-正则图: 每个顶点的度数均为k的无向(简单)图. 顶点数n, 边数m=kn/2. 无向完全图: 每对顶点之间都有一条边的无向(简单)图. n阶无向完全图记作Kn. 顶点数n, 边数m=n(n-1)/2, ?=?=n-1. 有向完全图: 每对顶点之间均有两条方向相反的边的有 向(简单)图. 顶点数n, 边数m=n(n-1), ?=?=2(n-1). * 集合与图论 引 言 图论是数学的一个分支，它以图为研究对象。图是由若干给定的点和连接两点的线所构成。其中，用点代表事物，用连接两点的线表示相应两个事物间具有的特定关系。 图论起源于18世纪，文字记载最早出现于瑞士数学家欧拉(L.Euler)1736年的论著中，关于解决哥尼斯堡七桥问题。 图论的产生与发展 哥尼斯堡七桥问题: 一个出发者能否从一块陆地出发走遍七座桥，而且每座桥恰好走一次，最后回到出发点? 陆地用点来表示,桥用连接两个点的一条线段来表示。 图论的产生与发展 1736年瑞士数学家欧拉（Euler）发表了图论的首篇论文——《哥尼斯堡七桥问题无解》，所以人们普遍认为欧拉是图论的创始人，称1736年是图论历史元年. 1936年匈牙利数学家 D. K?nig出版了图论的第一部专著《有限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。 图论的产生与发展 在20世纪100年间，图论不仅在许多领域，如运筹学、计算机科学等得到了广泛的应用，而且学科本身也获得长足发展，形成了拟阵理论、超图理论以及代数图论、拓朴图论等新分支。 本篇只讨论图论的最基本概念和基本理论及其典型应用，为大家在今后学习和工作中能够运用这一有力工具打下良好的基础。 主要内容： 图的基本概念（8学时） 树与割集（2学时） 连通度与匹配（2学时） 平面图与图的着色（4学时） 有向图 图 论 第10节 图的基本概念 主要内容： 图的基本定义 子图 顶点的度数与握手定理 图的同构 设V是一个非空集合，V的一切二元子集之集合 记为P2(V)，即 P2(V)={A?A?V,?A?=2} }(={{x, y}| x, y ?V}). 定义1 设V是一个非空集合，E?P2(V)，二元组 (V, E)称为一个无向图. V称为顶点集， V中元素称为无向图的顶点； E称为边集，E的元素称为无向图的边. 如果{u,v}?E，则称u与v相邻(邻接). 图的基本定义 图的基本定义 以V为顶点集，E为边集的无向图(V, E)常用字母 G表示，即G=(V, E). 如果?V?=p，?E?=q，则称G为一个(p, q)图，即G是 一个具有p个顶点q条边的图. 常用小写的英文字母u, v, w表示图的顶点(带下标); 常用小写的英文字母x, y, z表示图的边(带下标). (1) 顶点与边的表示方法 说明： 如果x={u, v}是图G的一条边，则x为这条边的名， u和v称为边x的端点，这时称顶点u和v与边x互相关 联，还说x是联接顶点u和v的边，且记为x=uv或x=vu. 若x与y是图G的两条边，并且仅有一个公共端点， 即?x∩y?=1，则称边x与y相邻(邻接). (2) 顶点与边的关联、边与边相邻(邻接) 图的基本定义 由定义可知，一个无向图G就是一个非空有限 集合V上定义的一个反自反且对称的二元关系E和V 构成的关系系统. (3) 图的关系表示 将图的每个顶点在平面上用一个点或一个