离散数学教程-王元元-第9章 图与树.pptVIP

离散数学 第9章 图与树 引 例 第9章 图与树 9.1.1 图的基本概念 9.1.1 图的基本概念 定义9.2： （1）边e = u, v时：称边e关联结点u、v，或u，v为e 的端点， 并称u为e 的起点， v为e 的终点。 （2）边e = {u, v}时： 称边e关联结点u、v，并称u、v为e 的端点， 这时u、v为相邻(接)的结点。 （3）当e = u,v或{u,v}， u = v时，u, v和{u, v}均称为环。 9.1.1 图的基本概念 例9.1： (1) 哥尼斯堡七桥图，可表示为： {A,B,C,D},{ { A,C },{ A,C }, { A,D }, { A,D },{ A,B }, { C,B },{ D,B }} 9.1.1 图的基本概念 9.1.1 图的基本概念 9.1.1 图的基本概念 9.1.1 图的基本概念 例9.2： 9.1.2 结点的度 定义9.4 在无向图中，结点v的度d(v)是结点v作为边的端点的次数。 在有向图中，结点v的出度是v作为有向边起点的次数，v的入度 是v作为有向边终点的次数。结点v的度d(v)是v的出度d+(v) 与入 度d-(v) 的和。 9.1.2 结点的度 9.1.2 结点的度 9.1.2 结点的度 9.1.2 结点的度 定义9.5 （1）一度的顶点称为悬挂点。 （2）各顶点的度均相同的图称为正则图。 各顶点度均为k的正则图称为k-正则图。 完全图都是正则图。 9.1.3 子图、补图及图同构 定义9.6 设图G1＝V1，E1，G2＝V2，E2， 如果V1?V2，E1?E2 且?E1?≤?E2?，则称G1为G2的子图。 如果G1是G2的子图，且G1不同于G2，则称G1为G2的真子图。 如果G1是G2的子图，且V1 = V2，则称G1为G2的生成子图。 定义9.7 设简单无向图G1＝V1，E1，G2＝V2，E2，称G1与G2 互为补图，如果V1=V2，E1?E2 = ?，且V1(或V2), E1∪E2是 简单完全图。 9.1.3 子图、补图及图同构 9.1.3 子图、补图及图同构 定义9.8 设G1＝V1，E1，G2＝V2，E2为两个简单图，称G1与G2 同构，如果存在一个双射h：V1?V2，使得对任意vi，vj? V1 vi ,vj? E1?h(vi),h(vj)?E2或{vi,vj}?E1?{h(vi),h(vj)}?E2 9.1.3 子图、补图及图同构 G1，G2不是同构的。 9.1.4 图的应用 例9.6 某人m带一条狗d，一只猫c和一只兔子r过河。m每次游过河时 只能带一只动物，而没人管理时，狗与兔子不能共处，猫和兔子 也不能共处。问m怎样才能把三个动物带过河去？ 9.1.4 图的应用 例9.7 用有向图描述识别符号串010?10的状态转换系统。 9.1.4 图的应用 例9.8 甲乙两人进行乒乓球赛，规定一方连胜两局或胜局首先 达到3局者为胜方。问甲乙至少、至多要进行多少局比赛。 9.2.1 路径、通路与回路 定义9.9：图G的顶点v1到顶点vl的拟路径是指如下顶点与边的序列： v1 ,e1 ,v2 ,e2 ,v3 ,…,vl-1 ,el-1 ,vl 其中v1 ,v2 ,v3 ,… ,vl-1 ,vl 为G的顶点，e1 ,e2 ,… ,el-1 为G的边， 且ei ( i= 1,2, … ,l-1 ) 以vi及vi+1为端点，(对有向图G，ei以vi为 起点，以vi+1为终点)。拟路径的边数l-1称为该拟路径的长度。 当ei ( i=1,2, …, l-1) 各不相同时，该拟路径称为路径，又当vi ( i=1,2, … ,l ) 各不相同时( 除v1与vl )，则称此路径为通路。 v1=vl 的路径称为闭