1、第五部分 图论本部分主要内容l 图的基本概念l 欧拉图、哈密顿图l 树l 平面图l 支配集、覆盖集、独立集、匹配与着色1第十四章 图的基本概念主要内容l 图l 通路与回路l 图的连通性l 图的矩阵表示l 图的运算预备知识l 多重集合 元素可以重复出现的集合l 无序集 AB=(x,y) | xAyB214.1 图定义 14.1 无向图 G = , 其中(1) V 为顶点集，元素称为 顶点(2) E为 VV 的多重集，其元素称为无向边，简称 边实例 设 V = v1, v2, , v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5
2、), (v4,v5) 则 G = 为一无向图3有向图定义 14.2 有向图 D=, 只需注意 E是 VV 的多重子集图 2表示的是一个有向图，试写出它的 V 和 E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的4相关概念1. 图 可用 G泛指图（无向的或有向的） V(G), E(G), V(D), E(D) n阶图2. 有限图3. n 阶零图与平凡图4. 空图 5. 用 ek 表示无向边或有向边6. 顶点与边的关联关系 关联、关联次数 环 孤立点7. 顶点之间的相邻与邻接关系58. 邻域与关联集 vV(G) (G为无向图 ) v 的关联集 vV(D) (D为有向图 )9. 标
3、定图与非标定图10. 基图相关概念6多重图与简单图定义 14.3 (1) 无向图中的平行边及重数(2) 有向图中的平行边及重数（注意方向性）(3) 多重图(4) 简单图在定义 14.3中定义的简单图是极其重要的概念 7顶点的度数定义 14.4(1) 设 G=为无向图 , vV, d(v) v的度数 , 简称度(2) 设 D=为有向图 , vV,d+(v) v的出度d(v) v的入度d(v) v的度或度数(3) (G), (G)(4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点8定理 14.1 设 G=为任意无向图， V=v1,v2, vn, |E|=m, 则证 G中每条 边 (包括 环 ) 均有两个端点，所以在 计 算 G中各 顶点度数之和 时 ，每条 边 均提供 2度， m 条 边 共提供 2m 度 .本定理的证明类似于定理 14.1握手定理定理 14.2 设 D=为任意有向图， V=v1,v2, vn, |E|=m, 则9握手定理推论推论 任何图 (无向或有向 ) 中，奇度顶点的个数是偶数 .证 设 G=为任意图，令V1=v | vV d(v)为奇数 V2=v | vV d(v)为偶数 则 V1V2=V, V1V2=，由握手定理可知由于 2m, 均为偶数，所以 为偶数，但因为 V1中顶点度数为奇数，所以 |V1|必为偶数 . 10
