1、图 论图的基本概念七座桥所有的走法一共 有 7！ =5040种。1736年，在经过一年的研究之后， 29岁的欧拉提交了 哥尼斯堡七桥 的论文，圆满解决了这一问题，同时开创了数学 新分支 -图论 。图 论n在 许多应用领域中 ：地图导航、 网络技术研究及程序流程分析都会 遇到由 “ 结点 ”和 “ 边 ” 组成的 图n在 计算机许多学科中如：数据结构、操作系统、网络理论、信息的组织与检索均离不开由这种 “ 结点 ” 和 “ 边 ” 组成的图 以及图的特殊形式 -树 。n图 与树是建立和处理离散对象及其 关系重要 工具。 如地图导航、 周游问题 、图像分割等等 。一、图的 概念1、 无序积 定义：
2、设 A， B为任意的两个集合，称 a， b aAbB 为 A与 B的无序积，记作 A & B其元素 a， b 可简记为 （ a， b） 2、图的定义1）定义 1 一个 无向图 是一个有序的二元组 ，记作 G，其中(1) V 称为顶点集，其元素称为 顶点 或 结点 (2) E称为边集 ，它是 无序积 V V的 多重子集 ，其元素称为 无向边 ，简称为 边 例： 无向图 G = 其中 顶点集合 V v1,v2,v3,v4 边集合 E (v1,v2),(v2,v3),(v3,v2),(v3,v1),(v2,v2),(v2,v2),(v1,v2), 园括号表示无向边 有平行边2） 定义 2 一个 有向
3、图 是一个有序的二元组 ，记作 D，其中(1) V 称为顶点集，其元素称为顶点或结点(2)E为边集， 它是笛卡儿积 V V的有穷多重子集 ，其元素称为 有向边 ，简称 边 (弧 )有向图 D= 其中 V v1,v2,v3 边集合 E , ,（与前面的关系的图表示相当）3、有关图的术语、有关图的术语1）用 G表示无向图， D表示有向图。有时 用 V(G)， E(G)分别表示 G的顶点集和边集。2）用 |V(G)|， |E(G)|分别表示 G的顶点数和边 数若 V(G) n，则称 G为 n阶图 。对 有向图有相同定义。3）在图 G中，若 边集 E(G) ，则称 G为 零图若 G为 n阶图，则称 G
4、为 n阶零图 ，记作 Nn，特别是称 N1为 平凡图4）在用图形表示一个图时，若给每个结点和每一条边均指定一个符号（字母或数字），则称这样的图为 标定 图。5) 常用 ek表示边 (vi， vj)( 或 ) 设 G 为无向图， ek = (vi， vj)E ，则 称 vi， vj为 ek的端点 ，ek与 vi、 vj是彼此 相关联的 起、终点 相同的边称为 环不 与任何边关联的结点称为 孤立点 （包括有向图 )6）邻接：边的相邻 ： ek， elE 若 ek与 el至少有一个公共端点，则称 ek与 el是相邻的顶点的相邻 ：若 etE ，使得 et = ，则称 vi为 et的始点， vj为 e
5、t的终点，并称 vi邻接到 vj， vj邻接于 vi 两个结点为一条边的端点，则称两个结点 互为邻接点 ，也称 边关联于这两个结点 ，或称两个结点邻接于此边 。7）平行边：在无向图中，关联一对顶点的无向边如果多于 1条，则称这些边为 平行边 ，平行边的条数称为 重数 在 有向图中，关联一对顶点的有向边如果多于 1条， 并且它们的 方向 相同 ， 则称这些边为 平行边 8）多重图和简单图： 含平行边的图称为多重图既 不含平行边也不含环的图称为 简单图简单图 （主要讨论简单图 ）4、结点的度1) 定义 4 设 G 为无向图， v V ，称 v作为边的端点的次数之和 为 v的 度数 ，简称为 度 ，
6、记作 dG(v)，简记为 d(v)， 即为：结点 v 所关联的边的总条数关于有向图 D 有： vV ，称 v作为边的 始点的次数之和 为 v的 出度 ，记作 d+(v)，称 v作为边的 终点 的次数之和为 v的 入度 ，记作 d-(v)称 d+(v)+ d-(v)为 v的度数，记作 dD(v).2) 称度数为 1的顶点为 悬挂顶点 ，与它关联的边称为 悬挂边根据结点的度数可将结点分为：度为偶数 (奇数 )的顶点称为 偶度 顶点 (奇度顶点 ).一个环提供的度为 2（有向图的环提供入度 1和出度 1） 3）定义： (G) = maxd(v)|vV(G) 为图 G中结点最大的度 (G) = min
7、d(v)|vV(G) 为图 G中结点最小的度简记为 、 定义： (D) = maxd (v)|vV(D) 为图 D中结点最大 的 入 度 (D) = maxd (v)|vV(D) 为图 D中结点最大的 出 度 -(D) = mind (v)|vV(D) 为图 D中结点最小 的 入 度 (D) = mind (v)|vV(D) 为图 D中结点最小的 出 度5、握手定理（欧拉）1)定理 1 设 G 为任意无向图 ,V v1， v2， ， vn, E = m，则 d(vi) 2m (所有结点的度数值和为边数的 2倍 )证 : G中每条边 (包括环 )均有两个端点，所以在计算 G中各顶点度数之和时，每
8、条边均提供 2度，当然， m条边共提供 2m度2) 定理 2 设 D 为任意有向图 ,V v1， v2， ， vn,|E| = m ，则 d+(vi) = d-(vi) = m 且 d(vi) 2m3) 推论 任何图 (无向的或有向的 )中， 奇度顶点 的 个数 是 偶数个4) 结点的度数序列(1) 设 G 为一个 n阶无向图， V v1， v2， ， vn称 d(v1)， d(v2)， ， d(vn) 为 G的 度数列注：由推论可知，不是任何一个非负整数序列均可作为一个图的度数列。条件： 奇度数 的结点个数应该是 偶数个（ 2）序列的可图化 ：对一个整数 序列 d=(d1,d2,dn),若存在以 n个顶点的 n阶无向图 G，有 d(vi)=di ，称该序列是 可图化的。特别的，如果得到的是简单图，称该序列是 可简单图化的。（ 3）定理 设非负整数列 d (d1， d2， ， dn)，则 d是可图化的 当且仅当 di 是偶数 (序列之和必须是偶数 )（ 4）由于简单图中没有平行边及环定理：设 G为任意 n阶无向 简单图 ，则 (G)d2d n=1 且 di= 偶数d4=（ 3,3,3,1） 分析 d5=（ 4,4,3,3,2,2）
