离散数学：5-1-1 图的基本概念

第三部分图论引例——哥尼斯堡七桥问题转化Euler(欧拉)1736年包含两个要素：对象(陆地)对象间的二元关系(是否有桥连接)转化问题：是否能从任一个顶点开始，通过每条边恰好一次再回到起点？问题：是否能从A、B、C、D中的任一地开始走，通过每座桥恰好一次再回到起点？ABCDABCD图论中讨论的图第三部分图论图论是离散数学的重要组成部分，是近代应用数学的重要分支。

1736年是图论历史元年，瑞士数学家欧拉发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。欧拉是公认的图论创始人。1936年，匈牙利数学家寇尼格出版了图论的第一部专著《有限图与无限图理论》，这是图论发展史上重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。

第三部分图论近50年来，随着计算机科学的发展，图论更以惊人的速度向前发展，真是异军突起，活跃非凡。作为描述事务之间关系的手段或称工具，图论在许多领域都得到广泛的应用，如：计算机科学、物理学、化学、运筹学、信息论、控制论、网络理论、社会科学以及经济管理、军事、国防、工农业生产等方面。第三部分图论第5章图的基本概念第6章特殊的图第7章树

第5章图的基本概念5.1无向图与有向图5.2通路、回路、图的连通性5.3图的矩阵表示5.4最短路径和关键路径5.1无向图及有向图无序对两个体x，y的无序序列称为无序对，记为(x,y)。(x,y)=(y,x)无序积:

AB={(x,y)|xAyB}如A={a,b},B={c,d}

则AB={(a,c),(a,d),(b,c),(b,d)}=BA

AA={(a,a),(a,b),(b,b)}多重集合:元素可以重复出现的集合。无向图无向图G=<V,E>,

其中(1)V是非空有穷集合，其元素称为顶点。(2)E为VV的多重子集，其元素称为无向边，简称边.如G=<V,E>如图所示,

其中V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v1,v5),

(v2,v5),(v2,v3),

(v2,v3),(v4,v5)}

有向图有向图D=<V,E>,

其中(1)V是非空有穷集合,其元素称为顶点。(2)E为VV的多重子集，其元素

称为有向边，简称边.如D=<V,E>如图所示,

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<b,c>,<c,d>,<d,c>}D的基图：用无向边代替所有有向边所得到的图注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的。无向图与有向图的表示通常用G表示无向图，V(G)——G的顶点集E(G)——G的边集.ek表示无向边通常用D表示有向图,V(D)——D的顶点集E(D)——D的边集.ek表示有向边n阶图——

n个顶点的图。有限图——

V,E都是有穷集合的图。零图——

E=（即无边的图）。平凡图——

1阶零图（|V|=1，E=，只有一个顶点的图）空图——

V=（无顶点的图）

常用G泛指无向图和有向图.无向图顶点和边的关联设ek=(vi,vj)是无向图G=<V,E>的一条边,称vi,vj为ek的端点,ek与vi(

vj)关联.若vi

vj,则称ek与vi(

vj)的关联次数为1;若vi=vj,则称ek为环,此时称ek与vi的关联次数为2;若vi不是ek端点,则称ek与vi的关联次数为0.如右图：v2,v5为e4的端点,e4与v2(v5)关联.e1为环,e1与v1

的关联次数为2e7与v4(v5)的关联次数为1、与v2关联次数为0无向图顶点和边的相邻设ek=(vi,vj)是无向图G=<V,E>的一条边,无边关联的顶点称作孤立点.若(vi,vj)E,则称vi,vj相邻;若ek,el至少有一个公共端点,则称ek,el相邻.如右图：孤立点：v6顶点间的相邻：v4,v5相邻;边之间的相邻：e2,e5相邻.有向图顶点和边的相邻设有向图D=<V,E>,设ek=<vi,vj>是有向图的一条边,又称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi.如右图：a是e2的始点，b是e2的终点，a邻接到b,b邻接于a。无向图顶点的度数

设G=<V,E>为无向图,vV,v的度数(度)

d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边

G的最大度(G)=max{d(v)|vV}G的最小度(G)=min{d(v)|vV}如右图

d(v1)=4,d(v4)=1,(G)=4,(G)=1,

v4是悬挂顶点,e7是悬挂边,e1是环

有向图顶点的度数设D=<V,E>为有向图,vV,v的出度d+(v):v作为边的始点次数之和

v的入度d(v):v作为边的终点次数之和

v的度数(度)d(v):v作为边的端点次数之和

d(v)=d+(v)+d-(v)最大出度+(D),最小出度+(D)最大入度(D),最小入度(D)最大度(D),最小度(D)

例如

d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+(D)=4,+(D)=0,(D)=3,(D)=1,

(D)=5,(D)=3.

握手定理

定理

设图G=<V,E>无向图或有向图，|V|=n，|E|=m则图中所有顶点度数之和都等于边数的2倍。有向图的所有顶点入度之和等于出度之和等于边数.证:因为G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.有向图的每条边提供一个入度和一个出度,故所有顶点入度之和等于出度之和，且等于边数.握手定理(续)推论

任何无向图和有向图中奇度顶点的个数必为偶数.证:设G=<V,E>为任意图，令

V1={v|vVd(v)为奇数}

V2={v|vVd(v)为偶数}则V1V2=V,V1V2=，

由握手定理可知

由于2m,均为偶数，所以也为偶数,但因为V1中顶点度数都为奇数，所以|V1|必为偶数.图的度数列

设无向图G的顶点集V={v1,v2,…,vn}G的度数列:d(v1),d(v2),…,d(vn)上图度数列:4,4,2,1,3图的度数列

设有向图D的顶点集V={v1,v2,…,vn}D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d(v1),d(v2),…,d(vn)

D的度数列:d(v1),d(v2),…,d(vn)如右图出度列:4,0,2,1入度列:1,3,1,2度数列:5,3,3,3握手定理的应用1例1：

(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?解：不可能.它们奇度顶点的个数都为奇数.例2:已知图G有10条边,4个3度顶点,其余顶点的度数均不大于2,问G至少有几个顶点?

解：设G有n个顶点.由握手定理,43+2(n-4)210

解得n8握手定理的应用2例3：

证明：不存在具有奇数个面且每个面都具有奇数条棱的多面体。证用反证法.假设存在这样的多面体,

作无向图G=<V,E>,其中V={v|v为多面体的面},E={(u,v)|u,vVu与v有公共的棱uv}.

根据假设,|V|为奇数，且vV,d(v)为奇数.则总度数为奇数，这与握手定理的推论矛盾!多重图与简单图

定义：在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.含平行边的图