离散数学—图论[]版.ppt

第8章 图论 8.1 图的基本概念 8.2 路径和回路 8.３ 图的矩阵表示 8.４ 二部图 8.5 平面图 8.6 树 8.7 有向树 8.8 运输网络 8.1 图的基本概念 定义8.1―1 一个图G是一个三重组〈V(G),E(G),ΦG〉,其中V(G)是一个非空的结点(或叫顶点)集合,E(G)是边的集合,ΦG是从边集E到结点偶对集合上的函数。一个图可以用一个图形表示。 例1设G=〈V(G),E(G),ΦG〉,其中V(G)={a,b,c,d }, E(G)={e1,e2,e3,e4,e5,e6,e7}, ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d), ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b)则图G可用图8.1―1表示。 定义中的结点偶对可以是有序的,也可以是无序的。若 边e所对应的偶对〈a,b〉是有序的,则称e是有向边。有 向边简称弧,a叫弧e的始点,b叫弧e的终点,统称为e的端 点。称e是关联于结点a和b的,结点a和结点b是邻接的。 若边e所对应的偶对(a,b)是无序的,则称e是无向边。无 向边简称棱,除无始点和终点的术语外,其它术语与有向 边相同。 每一条边都是有向边的图称为有向图, 第三章中的关系 图都是有向图的例子。每一条边都是无向边的图称为无 向图；如果在图中一些边是有向边,而另一些边是无向 边,则称这个图是混合图。我们仅讨论有向图和无向图, 且V(G)和E(G)限于有限集合。 约定用〈a,b〉表示有向边,(a,b)表示无向边,既表示有向 边又表示无向边时用［a,b］。 有向图和无向图也可互相转化。例如,把无向图中每一条 边都看作两条方向不同的有向边,这时无向图就成为有向 图。又如,把有向图中每条有向边都看作无向边,就得到无 向图。这个无向图习惯上叫做该有向图的底图。 在图中,不与任何结点邻接的结点称为弧立结点；全由孤 立结点构成的图称为零图。关联于同一结点的一条边称为 自回路；自回路的方向不定。自回路的有无不使有关图论 的各个定理发生重大变化,所以有许多场合都略去自回 路。 在有向图中,两结点间(包括结点自身间)若同始点和同 终点的边多于一条,则这几条边称为平行边。在无向图 中,两结点间(包括结点自身间)若多于一条边,则称这 几条边为平行边。两结点a、b间互相平行的边的条数 称为边［a,b］的重数。仅有一条时重数为1,无边时重 数为0。 定义8.1―2含有平行边的图称为多重图。 非多重图称为线图。无自回路的线图称为简单图。 在图8.1―3中,(a)、(b)是多重图,(c)是线图,(d)是简 单图,关系图都是线图。 定义 8.1―3 赋权图G是一个三重组〈V,E,g〉或四重组〈V,E,f,g〉,其中V是结点集合, E是边的集合,f是定义在V上的函数,g是定义在E上的函数。 右图给出一个赋权图。 V={v1,v2,v3}; E={e1,e2}={(v1,v2),(v2,v3)}; f(v1)=5,f(v2)=8,f(v3)=11; g(e1)=4.6,g(e2)=7.5 8.1.2 结点的次数 定义8.1―4在有向图中,对于任何结点v,以v为始点的 边的条数称为结点v的引出次数(或出度),记为deg+(v); 以v为终点的边的条数称为结点v的引入次数(或入度), 记为deg-(v);结点v的引出次数和引入次数之和称为 结点v的次数(或度数),记作deg(v)。在无向图中,结点 v的次数是与结点v相关联的边的条数,也记为deg(v)。 孤立结点的次数为零。 定理8.1―1 设G是一个(n,m)图,它的结点集合为 V={v1,v2,…,vn},则 定理8.1―2在图中,次数为奇数的结点必为偶数个。 证 设次数为偶数的结点有n1个,记为(i=1,2,…,n1)。次数为奇数的结点有n2个,记为(i=1,2,…,n2)。 由上一定理得 定义8.1―5各结点的次数均相同的图称为正则图,各 结点的次数均为k时称为k―正则图。 下图所示的称为彼得森(Petersen)图,是3―正则图。 8.1.3 图的同构 定义8.1.6设G=〈V,E〉和G′=〈V′,E′〉是两个图, 若存在从V到V′的双射函数Φ,使对任意a、b∈V, ［a,b]∈E当且仅当［Φ(a),Φ(b)］∈E′,并且 ［a,b］和［Φ(a),Φ(b)］有相同的重数,则称G和G′ 是同构的。 上述定义说明,两个图的各结点之间,如果存在一一对 应关系,而且这种对应关系保持了结点间的邻接关系 (在有向图时还保持边的方向)和边的重数,则这两个图 是同构的,两个同构的图除了顶点和边的名称不同外实 际上代表同样的组合