图的基本概念与握手定理

第三部分图论

第一讲图论的基本概念与握手定理1一、图的概念

二、图的类型三、结点的度数四、握手定理五、同构概念六、邻接矩阵主要内容2图论研究图的逻辑结构与性质.引言

图论最早起源于一些数字游戏的难题研究．图论的最早论文是1736年瑞士数学家欧拉（LeonhardEuler）所写，从而使欧拉成为图论的创始人。

图论是组合数学的一个分支，研究集合上的二元关系的工具，是建立数学模型的一个重要手段。在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展，使得图论成为数学领域里发展最快的分支之一。3引言哥尼斯堡七桥问题

当时哥尼斯堡（Konigsberg）城（现名加里宁格勒,属俄罗斯）的居民有郊游的习惯，在城郊的普雷格尔（Pregel）河畔，河中有两个小岛，七座桥将两个小岛和河岸连接起来，如图所示，问一个人能否从任一小岛出发不重复地走遍七座小桥？

41852年毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？四色问题5Hamilton问题

1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。6图G=<V,E>,其中(1)V

为顶点集，其元素称为结点（顶点）--用来表示事物(2)E为VV的多重集。其元素称为边--表示事物间的二元关系(一)图的定义:一、图的概念7(二)结点与边的关系:

①结点与边(不)相

关联：②结点与结点,边与边(不)相邻接一、图的概念(三)特殊点孤立点:不与任何结点相邻接的结点悬挂点:

只与一条边相关联的结点(四)特殊的边:环:

一条边若与两个相同的结点相关联则称为环。多重边(平行边）:与两个结点相关联的边若多于一条，则称这些边为多重边。8有向图与无向图:简单图与多重图:简单图--不含环与多重边；多重图--含多重边有权图与无权图:b.按边的种类分类：有限图与无限图：V与E为有限集合的图叫有限图，否则叫无限图。(n,m)图：有n个结点与m条边的图。

零图:即(n,0)图;平凡图:即(1,0)图。完全图:任意两个结点都相邻接的图。K-正则图:每个结点都与K条边相关联。c.按结点集与边集的“阶”分类a按边的方向分类二、图的类型9注意：完全图是

n-1

正则图完全图的每个结点都与其它n-1个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。1.完全图：2.正则图：

是3正则图

完全图,不是完全图二、图的类型10子图：

设G=<V,E>,G`=<V`,E`>为两个图，满足V`V且E`E，则称G`为G的子图，G为G`的母图，记作G`G。(1)G`为G的真子图：若G`G且V`V或E`E。

(2)G`为G的生成子图：若G`G且V`=V。(3)V1导出的导出子图：顶点集≠V1V,边集为两端点均在V1中的全体边构成的子图。(4)E1导出的导出子图：≠E1E,以E1中边关联的顶点的全体为顶点集的G的子图。二、图的类型11abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母图真子图V'V或E'E生成子图G'G且V'=V导出子图V'V或E'E二、图的类型12补图

设G=〈V,E〉,对于G1=〈V,E1〉若有G2=〈V,E∪E1〉是完全图,且E∩E1=Φ,则称G1是G的补图。

图G图G1图G2二、图的类型13

在无向图G中，与v相邻的顶点的数目称为v的次或度/degree。记为deg(v)或d(v)。

在有向图G中，以v为终点的边的条数称为v的入次或入度/in-degree。记为deg–(v)或d–(v)。以v为起点的边的条数称为v的出次或出度/out-degree。记为deg+(v)或d+(v)。三、结点的度数14在无向图G中,令

△(G)=max{d(v)|v∈V(G)}(G)=min{d(v)|v∈V(G)}

称△(G)和(G)分别为G的最大度和最小度。在有向图D中,类似定义△(D)、(G)。另外,令

△+(G)=max{d+(v)|v∈V(D)}

+(G)=min{d+(v)|v∈V(D)}△-(G)=max{d-(v)|v∈V(D)}

-(G)=min{d-(v)|v∈V(D)}分别为D的最大出度、最小出度、最大入度、最小入度。简记作△、、△+、+、△-、-。三、结点的度数15定理1

设G=<V,E>为任意无向图，V={v1,v2,…,vn},|E|=m,则四、握手定理定理2

设D=<V,E>为任意有向图，V={v1,v2,…,vn},|E|=m,则

证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.16握手定理推论及应用推论任何图(无向或有向)中，奇度顶点的个数是偶数.例1

无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？解设除3度与4度顶点外，还有x个顶点v1,v2,…,vx，则

d(vi)2，i=1,2,…,x，于是

3224+2x得x4,阶数n4+4+3=11.17五、图的同构定义

设G1=<V1,E1>,G2=<V2,E2>为两个图(有向或无向图)，（1）若存在双射函数f:V1V2,对于vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj))E2

（<vi,vj>E1当且仅当<f(vi),f(vj)>E2)（2）(vi,vj)（<vi,vj>）与(f(vi),f(vj))（<f(vi),f(vj)>）的重数相同。则称G1与G2是同构的，记作G1G2.18图同构的必要条件图之间的同构关系是等价关系.同构的必要条件：①边数相同，顶点数相同;②度数列相同;③度数相同的结点数目相同19图同构的实例(1)(2)(3)(4)图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.