离散数学之4-图的基本概念.ppt

《离散数学之4-图的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论部分主要内容图的基本概念路与回路图的矩阵表示欧拉图与汉密尔顿图*平面图*对偶图与着色*树与生成树*根树及其应用图的基本概念图的定义图的一些概念和规定结点的度数与握手定理简单图和多重图完全图与正则图子图与补图图的同构学习要点与基本要求实例分析图的定义定义7-1.1一个图是一个三元组，其中V(G)是一个非空的结点集合，E(G)是边集合，G是从边集合到结点无序偶（有序偶）集合上的函数。例如：下图所示的图e1e2e3e4e5e6abcdV(G)={a,b,c,d}E(G)={e1,e2,e3,e4,e5,e6}：E(G)→V

2、＆V(e1)=(a,b),(e2)=(a,c)(e3)=(b,d),(e4)=(b,c)(e5)=(c,d),(e6)=(a,d)关于图的说明一个图由若干个结点和边所组成，与边的长短及结点的位置无关。图可简记为G=，其中V是非空结点集，E是边集。e1e2e3e4e5e6abcde1e2e3e4e5e6abcd图的一些概念和规定集合的无序积：设A，B为任意的两个集合，称{{a,b}

3、a∈A∧b∈B}为A与B的无序积，记作A&B。可将无序积中的无序对{a,b}记为(a,b)，并且允许a＝b无论a,b是否相等，均有(a,b)＝(b,a)

4、，因而A&B＝B&A。多重集合：元素可以重复出现的集合，某元素重复出现的次数称为该元素的重复度。无向图：E(G)是V(G)&V(G)的多重子集。e∈E(G)称为无向边。有向图：E(G)是V(G)×V(G)的多重子集。e∈E(G)称为有向边。图的一些概念和规定如果在图中一些边是有向边，一些边是无向边，则称这个图是混合图。若有向边ei=，其中vj称为ei的起始结点，vk称为ei的终止结点。在一个图中，若两个结点由一条有向边或无向边关联，则这两个结点称为邻接点。在一个图中不与任何结点相邻的结点，称为孤立结点。仅由孤立结点组成的图称为零图，含有n

5、个结点的零图记为Nn。N1称为平凡图。图的一些概念和规定规定顶点集为空集的图为空图，并将空图记为。关联于同一结点的一条边称为环或自回路。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。举例例如下面的四个图。v1v2v3v4结点的度定义7-1.2在图G=中，与结点v（v∈V）关联的边数，称作是该结点的度数，记作deg(v)。G的最大度(G)=max{deg(v)

6、vV}

7、G的最小度(G)=min{deg(v)

8、vV}悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边注意：环对于结点度的贡献是2。图的度数举例d(v1)＝4(注意，环提供2度)，△＝4，δ＝1，v4是悬挂顶点，e7是悬挂边。握手定理定理7-1.1每个图中，结点度数的总和等于边数的两倍。证明因为每条边都关联两个结点，而一条边对其关联的每个结点的度数贡献为1，所以在计算G中各顶点度数之和时，每条边均提供2度，

9、E

10、条边共提供2

11、E

12、度.握手定理的推论推论在任何图中，度数为奇数的结点必定是偶数个。证明设G=为任意图，令V1={v

13、vV∧d(v)为

14、奇数}V2={v

15、vV∧d(v)为偶数}则V1∪V2=V,V1∩V2=，由握手定理可知由于V1中顶点度数都为奇数，显然是偶数，而2m也是偶数，所以也为偶数，所以

16、V1

17、必为偶数.问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的

18、关系。有向图中结点的度定义7-1.3在有向图中，射入一个结点的边数称为该结点的入度d-(v)，由一个结点射出的边数称为该结点的出度d+(v)。结点的出度与入度之和是该结点的度deg(v)。d+(a)＝4，d-(a)＝1(环e1提供出度1，提供入度1)，d(a)＝4+1＝5。△＝5，δ＝3，△+＝4(在a点达到)δ+＝0(在b点达到)△-＝3(在b点达到)δ-＝1(在a和c点达到)有向图的握手定理定理7-1.3在任何有向图中，所有结点的入度之和等于所有结点的出度之和。证明因为每一条有向边对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条

19、有向边，所以，有向图中个结点入度之和等于边数，各结点的出度之和也等于边数，故任何有向图中，入度