离散数学之4_图的基本概念.pptVIP

图 论 部 分 主要内容 图的基本概念 路与回路 图的矩阵表示 欧拉图与汉密尔顿图 *平面图 *对偶图与着色 *树与生成树 *根树及其应用 图的基本概念 图的定义 图的一些概念和规定 结点的度数与握手定理 简单图和多重图 完全图与正则图 子图与补图 图的同构 学习要点与基本要求 实例分析 图的定义 定义7-1.1 一个图是一个三元组V(G),E(G),?G，其中V(G)是一个非空的结点集合， E(G)是边集合， ?G是从边集合到结点无序偶（有序偶）集合上的函数。 例如：下图所示的图 关于图的说明 一个图由若干个结点和边所组成，与边的长短及结点的位置无关。 图可简记为G=V,E，其中V是非空结点集，E是边集 。 图的一些概念和规定 集合的无序积：设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作AB。 可将无序积中的无序对{a,b}记为(a,b)，并且允许a＝b 无论a,b是否相等，均有(a,b)＝(b,a)，因而 AB＝BA。 多重集合：元素可以重复出现的集合，某元素重复出现的次数称为该元素的重复度。 无向图：E(G)是V(G)V(G)的多重子集。e∈E(G)称为无向边。 有向图： E(G)是V(G) ×V(G)的多重子集。 e∈E(G)称为有向边。 图的一些概念和规定 如果在图中一些边是有向边，一些边是无向边，则称这个图是混合图。 若有向边ei=vj,vk，其中vj称为ei的起始结点， vk称为ei的终止结点。 在一个图中，若两个结点由一条有向边或无向边关联，则这两个结点称为邻接点。 在一个图中不与任何结点相邻的结点，称为孤立结点。 仅由孤立结点组成的图称为零图，含有n个结点的零图记为Nn。N1称为平凡图。 图的一些概念和规定 规定顶点集为空集的图为空图，并将空图记为?。 关联于同一结点的一条边称为环或自回路。 将有向图各有向边均改成无向边后的无向图称为原来图的基图。 易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。 G表示无向图，但有时用G泛指图(无向的或有向的)。 D只能表示有向图。 举例 例如 下面的四个图。 结点的度 定义7-1.2 在图G=V,E中，与结点v（v∈V）关联的边数，称作是该结点的度数，记作deg(v)。 G的最大度?(G)=max{deg(v)| v?V} G的最小度?(G)=min{deg(v)| v?V} 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 注意：环对于结点度的贡献是2。 图的度数举例 d(v1)＝4(注意，环提供2度)， △＝4，δ＝1， v4是悬挂顶点，e7是悬挂边。 握手定理 定理7-1.1 每个图中，结点度数的总和等于边数的两倍。 握手定理的推论 推论 在任何图中，度数为奇数的结点必定是偶数个。 证明 设G=V,E为任意图，令 V1={v | v?V∧d(v)为奇数} V2={v | v?V∧d(v)为偶数} 则V1∪V2=V, V1∩V2=?，由握手定理可知 问题研究 问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？ 解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。 说明： (1)很多离散问题可以用图模型求解。 (2)为了建立一个图模型，需要决定顶点和边分别代表什么。 (3)在一个图模型中，边经常代表两个顶点之间的关系。 有向图中结点的度 定义7-1.3 在有向图中，射入一个结点的边数称为该结点的入度d-(v)，由一个结点射出的边数称为该结点的出度d+(v)。结点的出度与入度之和是该结点的度deg(v)。 有向图的握手定理 定理7-1.3 在任何有向图中，所有结点的入度之和等于所有结点的出度之和。 证明 因为每一条有向边对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中个结点入度之和等于边数，各结点的出度之和也等于边数，故任何有向图中，入度之和等于出度之和。 握手定理的应用 例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗? 解 不可能. 它们都有奇数个奇数. 例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均不大于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 4?3+2?(n-4)?2?10 解得 n?8 多重图与简单图 平行边—— 连接于同一对结点之间的多条边称为平行边。 多重图——含有平行边的图称为多重图。 简