1 第三部分 图论 本部分主要内容 l 图的基本概念 l 树 l 欧拉图与哈密顿图 l 二部图与匹配 l 平面图 l 着色2 第九章 图的基本概念 主要内容 l 图 l 通路与回路 l 图的连通性 l 图的矩阵表示 预备知识 l 多重集合元素可以重复出现的集合 l 无序集A B=(x,y) | xA y B14.1 图 定义9.1 无向图G = , 其中 (1) V 为非空有穷集, 称为顶点集，其元素称为顶点 (2) E 为V V 的多重有穷集, 称为边集, 其元素称为无向边, 简 称边 例 无向图G = , 其中 V = v 1 , v 2 , v 3 , v 4 , v 5 , E = (v 1 ,v 1 ), (v 1 ,v 2 ), (v 2 ,v 3 ), (v 2 ,v 3 ), (v 2 ,v 5 ), (v 1 ,v 5 ), (v 4 ,v 5 ) 4 有向图 定义9.2 有向图D=, 其中 (1) V 为非空有穷集, 称为顶点集，其元素称为顶点 (2) E 为V V 的多重有穷集, 称为边集, 其元素称为有向边, 简 称边 例 有向图D=, 其中 V=a,b,c,d
