1、第五部分 图论本部分主要内容l 图的基本概念l 欧拉图、哈密顿图l 树l 平面图l 支配集、覆盖集、独立集、匹配与着色1第十四章 图的基本概念主要内容l 图l 通路与回路l 图的连通性l 图的矩阵表示l 图的运算2预备知识l 多重集合 元素可以重复出 现 的集合 某元素重复出现的次数称为该元素的 重复度 例如，在多重集合 a,a,b,b,b,c,d中， a,b,c,d的重复度分别为 2,3,1,1. l 无序 积 AB=(x,y) | xAyB 设 A， B为任意的两个集合，称 a,b|a A b B为A与 B的 无序积 ，记作 A&B. 通常，将无序积中的无序对 a,b,记为 (a,b),并
2、且允许a=b. 且无论 a,b是否相等均有 (a,b)=(b,a),因而A&B=B&A. 314.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), (v4,v5) 则 G = 为一无向图4有向图定义 14.2一个 有向图 是一个有序的二元组 ,记作 D,其中（ 1） V同无向图。
3、（ 2） E是 笛卡儿积 VV的多重子集，称为边集，其元素称为有向边，简称为边 。图 2表示的是一个有向图，试写出它的 V 和 E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的V = a,b,c,d, E = , , 5相关概念1. 图 可用 G泛指图（无向的或有向的）， D表示有向图 V(G), E(G), V(D), E(D)， |V(G)| ， |E(G)| n阶图2. n 阶零图 Nn与平凡图 N1（ 1阶零图）3. 空图 4. 标定图与非标定图5. 基图6. 用 ek 表示无向边或有向边7. 顶点与边的关联关系 关联、关联次数 环 孤立点8. 顶点之间的相邻与边之间
4、的相邻、邻接9. 邻域与关联集61 n阶图 在 图 的定 义 中，用 G表示无向 图 ， D表示有向 图 ，但有 时 用 G泛指 图 (无向的或有向的 )，可是 D只能表示有向 图 。另外， 为方便起 见 ，有 时 用 V(G)， E(G)分 别 表示 G的 顶 点集和 边 集，若|V(G)|=n,则 称 G为 n阶图 ， 对 有向 图 可做 类 似 规 定。 2有限 图 若 |V(G)|与 |E(G)|均 为 有限数， 则 称 G为 有限 图 。 3 n阶 零 图 与平凡 图 在 图 G中，若 边 集 E(G)= ,则 称 G为 零 图 ，此 时 ，又若 G为 n阶图 ， 则 称 G为 n阶
5、 零 图 ， 记 作 Nn，特 别 地，称 N1为 平凡 图 。 4空 图 在 图 的定 义 中 规 定 顶 点集 V为 非空集，但在 图 的运算中可能产 生 顶 点集 为 空集的运算 结 果， 为 此 规 定 顶 点集 为 空集的 图为 空 图 ，并将空 图记为 。 相关概念7相关概念5 标 定 图 与非 标 定 图 、基 图 称 顶 点或 边 用字母 标 定 的 图为标 定 图 ，否 则 称 为 非 标 定 图 。将有向 图 各 有向 边 均改成无向 边 后的无向 图 称 为 原来 图 的基 图 。易知 标 定 图 与非 标 定 图 是可以相互 转 化的。 6关 联 与关 联 次数、 环
6、、孤立点 设 G=为 无向 图 ， ek=(vi， vj) E， 则 称 vi， vj为 ek的端点， ek与 vi或 ek与 vj是彼此相关 联 的。若 vivj， 则 称 ek与 vi或 ek与 vj的关 联 次数为 1，若 vi=vj， 则 称 ek与 vi的关 联 次数 为 2，并称 ek为环 。任意的 vl V，若 顶 点 vl 不与 边 ek关 联 ， 则 称 ek与 vl的关 联 次数 为 0。 设 D=为 有向 图 ， ek= E，称 vi， vj为 ek的端点，若vi=vj， 则 称 ek为 D中的 环 。无 论 在无向 图 中 还 是在有向 图 中，无 边 关联 的 顶 点均称孤立点。 7相邻与邻接 设无向图 G=， vi， vj V， ek， el E.若 et E，使得 et=（ vi， vj），则称 vi与 vj是相邻的。若 ek与 el至少有一个公共端点，则称 ek与 el是相邻的。 设有向图 D=， vi， vj V， ek， el E.若 et E，使得 et=，则称 vi为 et的始点， vj为 et的终点，并称 vi邻接到 vj， vj邻接于 vi。若 ek的终点为 el的始点，则称 ek与 el相邻。 88. 邻域与关联集 vV(G) (G为无向图 ) v 的关联集相关概念的关联集98. 邻域与关联集 vV(D) (D为有向图 )相关概念10
