《1图的基本概念与握手定理》由会员分享，可在线阅读，更多相关《1图的基本概念与握手定理（22页珍藏版）》请在金锄头文库上搜索。
1、第三部分第三部分 图图 论论 第一讲 图论的基本概念与握手定理1一、一、 图的概念图的概念 二、二、 图的类型图的类型三、三、 结点的度数结点的度数四、四、 握手定理握手定理五、五、 同构概念同构概念六、六、 邻接矩阵邻接矩阵主要内容主要内容2图论研究图论研究图的逻辑结构与性质图的逻辑结构与性质.引引 言言 图论最早起源于一些数字游戏的难题研究图论的最早论文是1736年瑞士数学家欧拉（Leonhard Euler）所写，从而使欧拉成为图论的创始人。 图图论论是是组组合合数数学学的的一一个个分分支支，研研究究集集合合上上的的二二元元关关系系的的工工具具，是是建建立立数数学学模模型型的的一一个个重
2、重要要手手段段。在在物物理理、化化学学、信信息息学学、运运筹筹学学等等各各方方面面都都取取得得了了丰丰硕硕的的成成果果。计计算算机机的的迅迅速速发发展展，使使得得图图论论成成为数学领域里发展最快的分支之一。为数学领域里发展最快的分支之一。3引引 言言哥尼斯堡七桥问题哥尼斯堡七桥问题 当时哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄 罗斯） 的 居民 有郊游 的习惯 ，在 城郊 的普 雷 格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，问一个人能否从任一小岛出发不重复地走遍七座小桥？ 41852年年毕毕业业于于伦伦敦敦大大学学的的弗弗南南西西斯斯格
3、格思思里里发发现现了了一一种种有有趣趣的的现现象象：“看看来来，每每幅幅地地图图都都可可以以用用四四种种颜颜色色着着色色，使使得得有有共共同同边边界界的的国国家家都都被被着着上上不不同同的的颜颜色色。”这这个个现现象象能能不不能能从从数数学学上上加加以以严严格格证明呢？证明呢？四色问题四色问题5Hamilton问题问题 1856年年，英英国国数数学学家家Hamilton设设计计了了一一个个名名为为周周游游世世界界的的游游戏戏：他他用用一一个个正正十十二二面面体体的的二二十十个个端端点点表表示示世世界界上上的的二二十十座座大大城城市市（见见图图），提提出出的的问问题题是是要要求求游游戏戏者者找找
4、一一条条沿沿着十二面体的棱通过每个端点恰好一次的行走路线。着十二面体的棱通过每个端点恰好一次的行走路线。此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路， 而此图称为：而此图称为：哈密尔顿图哈密尔顿图。6图图G = , 其中其中(1) V 为顶点集，为顶点集，其元素称为其元素称为结点（顶点）结点（顶点）-用来表示事物用来表示事物(2) E为为V V 的多重集。的多重集。其元素称为其元素称为边边-表示事物表示事物间的二元关系间的二元关系( (一一) ) 图的定义图的定义: :一、图的概念一、图的概念7( (二二) ) 结点与边的关系结点与边的关系: : 结点与边结点与边(不不)相相 关联关联：
5、结点与结点结点与结点, ,边与边边与边( (不不) )相相邻接邻接一、图的概念一、图的概念( (三三) ) 特殊点特殊点孤立点: 不与任何结点相邻接的结点悬挂点: 只与一条边相关联的结点 ( (四四) ) 特殊的边特殊的边: :环: 一条边若与两个相同的结点相关联则称为环。多重边(平行边）:与两个结点相关联的边若多于一条，则称这些边为多重边。 8有向图与无向图:简单图与多重图:简单图-不含环与多重边；多重图-含多重边有权图与无权图:b.按边的种类分类：按边的种类分类：有限图与无限图：V与E为有限集合的图叫有限图，否则叫无限图。(n,m)图：有 n 个结点与 m 条边的图。 零图: 即(n,0)
6、图; 平凡图: 即(1,0)图。完全图:任意两个结点都相邻接的图。K-正则图:每个结点都与K条边相关联。c. c. 按结点集与边集的按结点集与边集的“阶阶”分类分类a a 按边的方向分类按边的方向分类二、二、 图的类型图的类型9注意注意：完全图是完全图是 n n- -1 1 正则图正则图完全图的每个结点都与其它 n-1 个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。1.完全图： 2.正则图： 是3正则图 完全图, 不是完全图二、二、 图的类型图的类型10子图：子图： 设设G=, G=为为两两个个图图，满满足足V V且且E E，则则称称G为为G的的子子图图，
7、G为为G的的母母图图，记记作作G G。(1)(1)GG为为G G的的真子图：真子图：若若GG G G且且VV V V或或EE E E。 (2)G为为G的的生成子图：生成子图：若若GG G G且且VV = = V V。(3)V(3)V1 1导导出出的的导导出出子子图图：顶顶点点集集V V1 1 V V, ,边边集集为为两两端点均在端点均在V V1 1中的全体边构成的子图。中的全体边构成的子图。(4) E E1 1导导出出的的导导出出子子图图：E E1 1 E,E,以以E E1 1中中边边关关联联的的顶点的全体为顶点集的顶点的全体为顶点集的G G的子图。的子图。二、二、 图的类型图的类型11abc
8、da1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母母图图真子图真子图V V或或E E生成子图生成子图G G且且V=V导出子图导出子图V V或或E E二、二、 图的类型图的类型12补补 图图 设G =V, E, 对于 G1 =V, E1 若有 G2 =V, EE1是完全图, 且 EE1 = , 则称G1 是 G 的补图。 图G 图G1 图G2二、二、 图的类型图的类型13 在在无无向向图图G中中，与与v相相邻邻的的顶顶点点的的数数目目称称为为v的的次或度次或度/degree。记为记为deg(v)或或d(v)。 在在有有向向图图G中中，以以v为为终终点点的的边边的的条条数
9、数称称为为v的的入入次次或或入入度度/in-degree。记记为为deg(v)或或d (v)。以以v为为起起点点的的边边的的条条数数称称为为v的的出出次次或或出出度度/out-degree。记为记为deg+(v)或或d +(v)。三、三、 结点的度数结点的度数14在无向图在无向图G G中中, ,令令 (G)=(G)=maxd(v)|vV(Gmaxd(v)|vV(G) (G)= (G)= mind(vmind(v)| )| vV(GvV(G) ) 称称(G)(G)和和 (G)(G)分别为分别为G G的最大度和最小度。的最大度和最小度。在有向图在有向图D D中中, ,类似定义类似定义(D)(D)、
10、 (G)(G)。另外另外, ,令令 + +(G) = (G) = maxdmaxd+ +(v(v)| )| vV(DvV(D) ) + +(G) = (G) = mindmind+ +(v(v)| )| vV(DvV(D) ) - -(G) = (G) = maxdmaxd- -(v(v)| )| vV(DvV(D) ) - -(G) = (G) = mindmind- -(v(v)| )| vV(DvV(D) ) 分别为分别为D D的最大出度、最小出度、最大入度、最小入的最大出度、最小出度、最大入度、最小入度。简记作度。简记作、 、 + +、 + + 、 - - 、 - - 。三、三、 结点
11、的度数结点的度数15定理定理1 设设G=为为任意无向图任意无向图，V=v1,v2,vn, |E|=m, 则则四、握手定理四、握手定理定理定理2 设设D=为为任意有向图任意有向图，V=v1,v2,vn, |E|=m, 则则证 G中每条中每条边 (包括包括环) 均有两个端点，所以在均有两个端点，所以在计算算G中各中各顶点点度数之和度数之和时，每条，每条边均提供均提供2度，度，m 条条边共提供共提供 2m 度度.16握手定理推论及应用握手定理推论及应用推论推论 任何图任何图 (无向或有向无向或有向) 中，奇度顶点的个数是中，奇度顶点的个数是偶数偶数.例例1 无无向向图图G有有16条条边边，3个个4度
12、度顶顶点点，4个个3度度顶顶点点，其余顶点度数均小于，其余顶点度数均小于3，问，问G的阶数的阶数n为几？为几？解解 设除设除3度与度与4度顶点外，还有度顶点外，还有x个顶点个顶点v1, v2, , vx， 则则 d(vi) 2，i =1, 2, , x，于是于是 32 24+2x得得 x 4, 阶数阶数 n 4+4+3=11. 17五、图的同构五、图的同构定定义义 设设G1=, G2=为为两两个个图图(有有向向或无向图或无向图)，（1）若存在双射函数）若存在双射函数f:V1V2, 对于对于vi,vj V1, (vi,vj) E1 当且仅当当且仅当 (f(vi),f(vj) E2 （ E1 当且
13、仅当当且仅当 E2 )（ 2） (vi,vj)（ ） 与与 (f(vi),f(vj)（ ）的重数相同。）的重数相同。则称则称G1与与G2是是同构同构的，记作的，记作G1 G2. 18图同构的必要条件图同构的必要条件l图之间的同构关系是等价关系图之间的同构关系是等价关系.l同构的必要条件：同构的必要条件： 边数相同，顶点数相同边数相同，顶点数相同; 度数列相同度数列相同; 度数相同的结点数目相同度数相同的结点数目相同19图同构的实例图同构的实例 (1) (2) (3) (4) 图中，图中，(1)与与(2)不同构（度数列不同），不同构（度数列不同），(3)与与(4)也不同构也不同构.20六、图的表
14、示六、图的表示邻接矩阵邻接矩阵21同构判定算法（用邻接矩阵）同构判定算法（用邻接矩阵）1、根据图确定其邻接矩阵、根据图确定其邻接矩阵2、计计算算行行次次（矩矩阵阵每每行行的的个个数数-对对应应于于出出次次） 和列次：（对应于入次）和列次：（对应于入次）3、不不考考虑虑出出现现的的次次序序不不同同，若若行行次次与与列列次次不不同同，则必不同构，否则继续则必不同构，否则继续 4、同时交换其一矩阵的行和行，列和列。、同时交换其一矩阵的行和行，列和列。 若此矩阵能变成与另一矩阵一样，则同构。对所若此矩阵能变成与另一矩阵一样，则同构。对所有顶点的排列都试过，仍不相同，则不同构。有顶点的排列都试过，仍不相同，则不同构。邻接矩阵的应用邻接矩阵的应用22
