离散数学(第10章)陈瑜.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 期中考试通知 主要内容 图的基本概念 什么是图 图的分类 结点的度数 握手定理 子图与补图 完全图 补图 图的同构 §10.1 图的基本概念 §10.1 图的基本概念 图的定义 图的定义 图的定义 图的分类(按边的方向) 图的分类(按边的方向) 图的分类(按边的方向) 图的分类(按边的方向) 几个概念 几个概念 几个概念 图的分类(按边的重数) 图的分类(按边的重数) 图的分类(按边的重数) 图的分类(按权) 结点的度数 结点的度数 例10.1 例10.1 例10.1 例10.1 例10.1 握手定理（Euler,1736年） 推论10.1.1 推论10.1.1 推论10.1.1 度数序列 度数序列 子图 子图 子图 完全图 完全图 完全图 补图 补图 例10.3 二部图 设图G=V,E，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。 二部图 设图G=V,E，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。 设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。 图的同构 定义10-1.6 定义10-1.6 例10.4 例10.5 两个图同构的必要条件 两个图同构的必要条件 两个图同构的必要条件 例10.6 例10.6 例10.6 习题 期中考试通知 §10.2 道路与回路 §10.2 道路与回路 简单道路与基本道路 简单道路与基本道路 简单道路与基本道路 例10.7 注： 注： 道路图和圈图 若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。 若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。 例10.12 道路图和圈图 若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。 若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。 例10.12 道路图和圈图 若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。 若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。 例10.12 定理10.3 定理10.3 定理10.3 定理10.3 定理10.3 定理10.3 §10.3 图的连通性 无向图的连通性 无向图的连通性 无向图的连通性 连通图 连通图 连通图 例10.10 例10.9 点割集 点割集 点割集 例10.11 边割集 边割集 边割集 例10.12 例10.12 点连通度、边连通度 点连通度、边连通度 点连通度、边连通度 例10.13 例10.13 定理10.4 在非平凡连通图G中，结点v为G的割点的充分必要条件是存在结点u和w，使u到w的每一条道路都以v为内部结点。（P138,定理10.4） 定理10.5 在非平凡连通图G中，边e为G的割边的充分必要条件是e不包含于G的任何圈中。 定理10.4 在非平凡连通图G中，结点v为G的割点的充分必要条件是存在结点u和w，使u到w的每一条道路都以v为内部结点。 定理10.5 在非平凡连通图G中，边e为G的割边的充分必要条件是e不包含于G的任何圈中。 定理10.4 在非平凡连通图G中，结点v为G的割点的充分必要条件是存在结点u和w，使u到w的每一条道路都以v为内部结点。 定理10.5 在非平凡连通图G中，边e为G的割边的充分必要条件是e不包含于G的任何圈中。 （证明略，p139） 有向图的连通性 有向图的连通性 强连通图、单向连通图 强连通图、单向连通图 强连通图、单向连通图 强连通图、单向连通图 强连通图、单向连通图 例10.15 弱分图、单向分图、强分图 弱分图、单向分图、强分图 例10.16 作业 主要内容 图的矩阵表示 图的矩阵表示 图的矩阵表示 例10.17 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的