19-图的基本概念.pptVIP

图的基本概念 离散数学 第19讲 上一讲内容的回顾 布尔格 布尔代数系统 布尔代数的性质 布尔代数的同态与同构 有限布尔代数的表示定理 有限布尔代数的基数 图的基本概念 图的定义与表示 图中的关系 顶点的度数 子图与图的同构 完全图 正则图 r部图 图模型 K?nigsberg七桥问题 问题的抽象： 用顶点表示对象-“地块” 用边表示对象之间的关系-“有桥相连” 图的定义与表示 无向图的定义 图G是一个三元组：G =〈VG, EG, ?〉 VG和EG是集合，且VG?EG=?, ?:EG?{{vi, vj}| vi, vj?VG} 注意：{vi, vj}={vj, vi} G可以很方便地用图形表示：VG中的元素用空心小圆点表示，EG中的元素用连在两点之间的连线表示。 因此：VG称为顶点集，EG称为边集。 有向图的定义 只需将上述?定义为?:EG?VG?VG 注意：这里的图形不是几何图形，位置、大小、线形均无意义，有意义的只是那些顶点之间有边。 图的定义并不依赖于图形。 图中的关系 图中边与顶点之间的关系 关联关系 图中顶点之间的关系 相邻关系 利用上述关系可以用矩阵表示图。 简单图 多重边与环 如果?不是单射，即存在ei, ej?EG, ei?ej, 但?(ei)=?(ej), 则ei, ej是多重边。 设ei?EG, 若?(ei)={vi, vi}={vi}, 则ei称为环。 简单图 既无环，又无多重边 的图称为简单图。 (简单图中可用uv?E表示边。) 顶点的度数 无向图中顶点的度数 dG(v) = 与v相关联的边的条数。dG(v)是非负整数。 ?(G)和?(G) 有向图中顶点的度数、出度和入度 dG+(v) = 以v为始点的边的条数。 dG-(v) = 以v为终点的边的条数。 顶点度数的数量特征 无向图中顶点度数的和是偶数。 m是图中的边的条数。 奇度顶点的个数是偶数 度数序列 图的度数序列及非负整数序列的可图化 非负整数序列(d1,d2,…,dn)是图的度数序列当且仅当其各项之和为偶数。 必要性显然。 可以用构造法证明充分性 注意：奇数顶点成对出现。构造图如下： 奇数顶点两两相连。度数还小于相应的di的顶点上加上相应数量的环。 子图 设G=V,E, G’=V’,E’, 如果V’?V, E’?E, 则称G’是G的子图。 如果V’?V, 或者E’ ?E, 则称为真子图。 如果V’=V, 则称为生成子图。 诱导(导出)子图：可以由顶点集的子集，或者由边集的子集导出一个子图。 图的同构 图同构的定义 设G1=V1, E1, ?1和G2=V2, E2, ?2是两个无向图。若存在双射f: V1?V2, g: E1?E2, ?e∈E1, ?1(e)={u,v}, 当且仅当 g(e)∈E2, 且?2(g(e))={f(u),f(v)}。 简单图同构的判定 设G1=V1, E1, ?1和G2=V2, E2, ?2是两个无向图。若存在双射f: V1?V2, g: E1?E2, ?e∈E1, ?1(e)={u,v}, 当且仅当 g(e)∈E2, 且?2(g(e))={f(u),f(v)}。 图同构的例子 下面三个图同构(Petersen图) 同颜色的点是同构映射下的对应点 完全图 完全图的顶点度数和边数 若简单图G中任意两点均相邻，则称为完全图。记为Kn, 其中n是图中顶点数。 显然，如果同构的图看作一个，对每个正整数n有且仅有一个完全图。记为Kn, 其中n是图中顶点数。 Kn中每个顶点皆为n-1度，总边数为n(n-1)/2。 ?简单图边数的上限 若图G是简单图，其总边数m?n(n-1)/2 完全图(n=1,2,3,4,5) 图G与其补图G’具有相同的顶点集，其边集不相交，构成相应完全图边集的划分。 正则图 几个典型的正则图 以2进制编码为顶点的正则图 r部图 r部图(下面两个例子中r=2) 完全r部图 图的运算 减边或边集：G-e 减点或点集: G-v 边的收缩: G?e 加新边:G+e 并图、交图、差图、环和、联图、积图 “巧渡河”问题 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。 起始状态是“人狼羊菜”，结束状态是“空”。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 “巧渡河”问题的解 考试时间编排问题 问题：排考试时间，一方面要总时间尽可能短(假设教室没问题)，另一方面一个同学所选的