图的基本概念无向图及有向图

关于图的基本概念无向图及有向图第一页，共六十一页，2022年，8月28日

图论的起源图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的“哥尼斯堡七桥问题”，从而使欧拉成为图论的创始人。第二页，共六十一页，2022年，8月28日1.哥尼斯堡七桥问题

哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？第三页，共六十一页，2022年，8月28日哥尼斯堡七桥问题解决方式莱昂哈德·欧拉（LeonhardEuler）在1735年圆满地解决了这一问题，证明这种方法并不存在，也顺带解决了一笔画问题。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。

/wiki/File:Konigsberg_bridges.png→

第四页，共六十一页，2022年，8月28日5图论的起源欧拉最后给出任意一种河──桥图能否全部走一次的判定法则。如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。第五页，共六十一页，2022年，8月28日

欧拉图定义

一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图

欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。第六页，共六十一页，2022年，8月28日

从这个问题可以看出：图：图用点代表各个事物,用边代表各个事物间的二元关系。所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。第七页，共六十一页，2022年，8月28日

2、一百多年以后

“七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用

“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和“四色猜想”问题。第八页，共六十一页，2022年，8月28日3.哈密尔顿回路问题

1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。第九页，共六十一页，2022年，8月28日哈密尔顿回路图

此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。第十页，共六十一页，2022年，8月28日4、“四色猜想”问题

人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色

四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。第十一页，共六十一页，2022年，8月28日

5、又过了半个世纪

四色猜想问题出现后，图论的研究又停滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。第十二页，共六十一页，2022年，8月28日

学好图论十分重要

图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。第十三页，共六十一页，2022年，8月28日14第7章图的概念本章学习：1.

无向图及有向图2.

通路、回路、图的连通性3.

图的矩阵表示4.

最短路径及关键路径

第十四页，共六十一页，2022年，8月28日15今日内容无向图及有向图图的一些相关概念度握手定理子图相关概念图同构第十五页，共六十一页，2022年，8月28日16预备知识有序积:A×B={<x,y>|x∈A∧y∈B}有序对:<x,y>≠<y,x>无序积:A&B={(x,y)|x∈A∧y∈B}无序对:(x,y)=(y,x)多重集:{a,a,a,b,b,c}≠{a,b,c}重复度:a的重复度为3,b的为2,c的为1第十六页，共六十一页，2022年，8月28日171、无序积：A&B设A、B为两集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B。为方便起见，将无序对{a,b}记作

(a,b)。

(a,b)＝(b,a)例：设A={a,b},B={c,d},则A&B＝？A&A＝？

A&B={(a,c),(a,d),(b,c),(b,d)}A&A={(a,a),(a,b),(b,b)}第十七页，共六十一页，2022年，8月28日182、无向图一个无向图G是一个二元组<V,E>,即G=<V,E>,其中:①.

V是一个非空集合,称为G的顶点集,V中元素称为顶点或结点;②.

E是无序积V&V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边。•用小圆圈表示V中顶点,若(a,b)∈E,就在a,b之间连线段表示边(a,b),其中顶点的位置、连线的曲直及是否相交都无关紧要。第十八页，共六十一页，2022年，8月28日无向图示例

给定无向图G＝<V,E>，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.

第十九页，共六十一页，2022年，8月28日203、有向图

一个有向图D是一个二元组<V,E>,

即D=<V,E>,其中：①.V同无向图中的顶点集;②.E是笛卡儿积的多重子集,其元素称为有向边,也简称边.第二十页，共六十一页，2022年，8月28日有向图示例给定有向图D=<V,E>，其中V＝{a,b,c,d}，E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。

第二十一页，共六十一页，2022年，8月28日图的一些概念和规定G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。V(G)，E(G)分别表示G的顶点集和边集。若|V(G)|＝n，则称G为n阶图。若|V(G)|与|E(G)|均为有限数，则称G为有限图。若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图

在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。第二十二页，共六十一页，2022年，8月28日标定图与非标定图、基图将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边<vi,vj>），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。第二十三页，共六十一页，2022年，8月28日关联与关联次数、环、孤立点设G＝<V,E>为无向图，ek＝(vi,vj)∈E， 称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。 若vi≠vj，则称ek与vi或ek与vj的关联次数为1。 若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。 任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。第二十四页，共六十一页，2022年，8月28日关联与关联次数、环、孤立点设D＝<V,E>为有向图，ek＝<vi,vj>∈E， 称vi,vj为ek的端点。 若vi＝vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。第二十五页，共六十一页，2022年，8月28日相邻与邻接设无向图G＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝(vi，vj)，则称vi与vj是彼此相邻的 若ek与el至少有一个公共端点，则称ek与el是彼此相邻的。设有向图D＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝<vi，vj>，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。 若ek的终点为el的始点，则称ek与el相邻。第二十六页，共六十一页，2022年，8月28日27例：点边之间的关联次数第二十七页，共六十一页，2022年，8月28日28例：点点、边边之间的相邻关系第二十八页，共六十一页，2022年，8月28日顶点的度数定义设G＝<V,E>为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做dG(v)。 在不发生混淆时，简记为d(v)。 设D＝<V，E>为有向图，v∈V， 称v作为边的始点次数之和为v的出度，记做d+D(v)，简记作d+(v)。 称v作为边的终点次数之和为v的入度，记做d-D(v)，简记作d-(v)。 称d+(v)+d-(v)为v的度数，记做d(v)。第二十九页，共六十一页，2022年，8月28日30d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=0第三十页，共六十一页，2022年，8月28日31d+(v1)=2d+

(v2)=1d+

(v3)=3d+

(v4)=1d+

(v5)=1d-(v1)=1d-

(v2)=3d-

(v3)=0d-

(v4)=3d-

(v5)=1d(v1)=3d

(v2)=4d

(v3)=3d

(v4)=4d

(v5)=2第三十一页，共六十一页，2022年，8月28日32最大(出/入)度,最小(出/入)度在无向图G中，最大度:Δ(G)=max{dG(v)|v∈V(G)}最小度:δ(G)=min{dG(v)|v∈V(G)}在有向图D中，最大出度:Δ+(D)=max{dD+(v)|v∈V(D)}最小出度:δ+(D)=min{dD+(v)|v∈V(D)}最大入度:Δ-(D)=max{dD-(v)|v∈V(D)}最小入度:δ-(D)=min{dD-(v)|v∈V(D)}简记为Δ,δ,Δ+,δ+,Δ-,δ-第三十二页，共六十一页，2022年，8月28日33握手定理（图论基本定理）定理7.1设图G=<V,E>为无向图或有向图，

V={v1,v2,…,vn},,|E|=m，则说明

任何无向图中，各顶点度数之和等于边数的两倍。证明

G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。

推论：任何图中，度为奇数的顶点个数为偶数。

第三十三页，共六十一页，2022年，8月28日问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明： (1)很多离散问题可以用图模型求解。 (2)为了建立一个图模型，需要决定顶点和边分别代表什么。 (3)在一个图模型中，边经常代表两个顶点之间的关系。第三十四页，共六十一页，2022年，8月28日35握手定理定理7.2设有向图D=<V,E>，

V={v1,v2,…,vn},,|E|=m，则

第三十五页，共六十一页，2022年，8月28日度数列设G＝<V,E>为一个n阶无向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}为顶点集的n阶无向图G，使得d(vi)＝di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。类似地，设D＝<V,E>为一个n阶有向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为D的度数列，另外称d+(v1)，d+(v2)，…，d+(vn)与d-(v1)，d-(v2)，…，d-(vn)分别为D的出度列和入度列。第三十六页，共六十一页，2022年，8月28日度数列举例按顶点的标定顺序，度数列为 4,4,2,1,3。第三十七页，共六十一页，2022年，8月28日度数列举例按字母顺序，度数列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2第三十八页，共六十一页，2022年，8月28日39(4，4，3，1，0)(3，4，3，4，2)练习：第三十九页，共六十一页，2022年，8月28日可图化的充要条件定理

设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当且仅当证明 必要性。由握手定理显然得证。

充分性。由已知条件可知，d中有偶数个奇数度点。 奇数度点两两之间连一边，剩余度用环来实现。5331第四十页，共六十一页，2022年，8月28日41例7.1：(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？解：1.由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数序列。2.显然，图G中的其余顶点度数均为2时G图的顶点数最少.设G图至少有x个顶点.由握手定理可知，

3×4+2×(x-4)=2×10

解得:x=8

所以G至少有8个顶点。第四十一页，共六十一页，2022年，8月28日简单图与多重图定义在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。第四十二页，共六十一页，2022年，8月28日43简单图与多重图示例第四十三页，共六十一页，2022年，8月28日完全图定义7.7

设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记做Kn(n≥1)。

设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图。

设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。第四十四页，共六十一页，2022年，8月28日完全图举例n阶无向完全图的边数为： n(n-1)/2n阶有向完全图的边数为： n(n-1)n阶竞赛图的边数为： n(n-1)/2K53阶有向完全图4阶竞赛图第四十五页，共六十一页，2022年，8月28日正则图定义设G为n阶无向简单图，若v∈V(G)，均有d(v)＝k，则称G为k-正则图。举例

n阶零图是0-正则图

n阶无向完全图是(n-1)-正则图 彼得森图是3-正则图说明

n阶k-正则图中，边数m＝kn/2。 当k为奇数时，n必为偶数。第四十六页，共六十一页，2022年，8月28日子图定义设G＝<V,E>，G＝<V,E>为两个图(同为无向图或同为有向图)，若VV且EE，则称G是G的子图，G为G的母图，记作GG。 若VV或EE，则称G为G的真子图。 若V＝V，则称G为G的生成子图。 设G＝<V,E>为一图，V1V且V1≠，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作G[V1]。 设E1E且E1≠，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图，记作G[E1]。第四十七页，共六十一页，2022年，8月28日48在上图中，(2)，(3)均为(1)的子图；(3)是生成子图；(5)，(6)均为(4)的子图；(5)是生成子图；第四十八页，共六十一页，2022年，8月28日导出子图举例在上图中，设G为(1)中图所表示，取V1＝{a,b,c}，则V1的导出子图G[V1]为(2)中图所示。取E1＝{e1,e3}，则E1的导出子图G[E1]为(3)中图所示。第四十九页，共六十一页，2022年，8月28日补图定义7.9设G＝<V,E>为n阶无向简单图，以V为顶点集，以所有为边集使G成为完全图Kn的添加边组成的集合的图，称为G的补图，记作G。

若图G≌G，则称为G是自补图。(1)为自补图(2)和(3)互为补图第五十页，共六十一页，2022年，8月28日51在下图中，(1)是(2)的补图，当然(2)也是(1)的补图，就是说，(1)，(2)互为补图。同样，(3)，(4)互为补图。第五十一页，共六十一页，2022年，8月28日52图的同构在图论的研究中，我们更关心的是图的结构,而这种结构与顶点与边的具体元素或与图的图形的画法无关.对此,我们引进同构的概念.第五十二页，共六十一页，2022年，8月28日53图同构(graphisomorphism)定义7.10:设两个无向（有向）图G1=<V1,E1>,G2=<V2,E2>,若存在双射f:V1→V2,满足∀u∈V1,∀v∈V1