基图

1/13

图论部分

第七章、图的基本概念

7.1无向图及有向图

无向图与有向图

多重集合：元素可以重复出现的集合

无序积：{(x,y)|

定义无向图Q,其中

(1)顶点集$0,元素称为顶点

(2)边集F为k&f的多重子集，其元素称为无向边，简称边.

例如，如图所示，其中心⑷，…，心，&{(旳，匕)，(匕，匕),

(迫，方)，(乃，方)，(迫，％),(s,%),(必，％)}定艾有向图E>,其中

(1)$同无向图的顶点集，元素也称为顶点

(2)边集F为的多重子集，其元素称为有向边，简称边.

用无向边代替0的所有有向边所得到的无向图称作Q的基图，右图是有向图,试写出它

的！/和F

注意：图的数学定艾与图形表示，在同构(待叙)的意狡下是一一对应的

通常用G表示无向图，0表示有向图，也常用G泛指

无向图和有向图，用6表示无向边或有向边.

K6),E(G,EgG和D的顶点、集,边集.

77阶图：”个顶点的图

有限图：KF都是有穷集合的图

零图：吕0

平凡图：1阶零图

空图：^=0

顶点和边的关联与相邻：定狡设e*,v)是无向图G^的一条边，称v„匕为e*的端

点，©与v,(16)关联.若ViHV”则称故与Vi(v)的关联次数为1;若匕=匕，则称6为

环，此时称◎与匕的关联次数为2;若匕不是鸟端点,则称鼓与匕的关联次数为0.无边关联

的顶点称作孤立点.

定义设无向图=,vifKe“e《E,若©，匕)e£；则称乙匕相邻；若％&至少有一个

2/13

公共端点，则称6,8/相邻.

对有向图有类似定义.设6二〈乙匕〉是有向图的一条边，又称匕是牧的始点，V」是6

的终点，K邻接到Vj.匕邻接于Vi.

邻域和关联集

邻域和关联集

设无向图^veV(G)

”的邻域谑克匕(6A3"(G)A亦}

1的闪邻域2V(V)=MV)U{V)

丫的关联集7(v)=fej族要(G>e与咲联}

设有向图空厲蚀)

1的后绅元集石(护{边煖玖刀人今炉訪⑹付妙

、的先驱元集纭(忙甸頰匕(D)人Y细>“(C)人T

1的邻域E(v)=“e)u巧(巧

'的丙邻域jvD(v)=1V23(v)U{v}

顶点的度数

设G=为无向图，keK

y的度数(度)〃3):#作为边的端点次数之和

悬挂顶点：度数为1的顶点

悬挂边：与悬挂顶点关联的边

G的最大度zl(Q二max{〃(“)|i/eH

G的最小度&Q=min{d(访|keH

例如〃(％)二3,〃(乃)二4,6/(I/.)=4,zl(6)=4,J(6)=1,r

4

是悬挂顶点，g是悬挂边,

设^=为有向图，reK

i/的出度dW:y作为边的始点次数之和1/的入度力

3)：#作为边的终点次数之和

1/的度数(度)〃3)：#作为边的端点次数之和d(v)~/(#)+d(v)

。的最大出度zf(0,最小出度$(勿最大入度zT(Q,最小入度夕(勿最大度4(0,最小度

例如/(a)二4,d(a)=1,〃(m)二5,

d(d)=0,d®二3,〃(6)二3,

3/13

二4,5(0二0,zT⑵二3,芳⑵二1,4(Q二5,测二3.

握手定理

定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍，并且有向图的所有顶

点入度之和等于出度之和等于边数.

证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提

供2度，刃条边共提供2刃度.有向图的每条边提供一个入度和一个出度，故所有顶点入

度之和等于出度之和等于边数.

推论在任何无向图和有向图中，奇度顶点的个数必为偶数•

证设G=eQ为任意團，令

金何痣支MW)为讖fe

^IveFA^)为儀^

则v^yv^v^v^z,由握手走理可知

2加=£d(v)=£J(v)+工火)yt

t

由于2加,送心)均为朗，所以送心)也为1黝,但因为

图的度数列

设无向图G的顶点集乃，…，山G的度数列：d(s),dg…，div》如右图度数列:4,4,

2,1,3

设有向图。的顶点集V^[v,v2,…，％｝。的度数列：d(Q,d(Q,…，dg0的出度

列:d(s),d(v),…，d(i/J。的入度列：/(“)，d~lv｝、…，d~｛v^如右图度数列:5,3,

3,3

出度列:4,0,2,1

入度列：1,3,1,2

“中顶騒讎防奇数，所以质畝为

4/13

例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗？

解不可能.它们都有奇数个奇数.

例2已知图G有10条边，4个3度顶点，其余顶点的度数均小于等于2,问G至少有多少

个顶点？

解设G有”个顶点.由握手定理，

4x3+2x(rr4)>2x10

解得n>Q

例3证明不存在具有奇数个而且每个而都具有奇数条棱的多而体.

证用反证法.假设存在这样的多面体，

作无向图其中^{v|iz为多而体的面},

v)|u,v已Vu与#有公共的棱人停诃.

根据假设，为奇数且d(“)为奇数.这与握手定理的推论矛盾.

多重图与简单图

定义(1)在无向图中，如果有2条或2条以上的边关联同一对顶点，则称这些边为平行

边，平行边的条数称为重数.

(2)在有向图中，如果有2条或2条以上的边具有相同的始点和终点，则称这些边为有

向平行边，简称平行边，平行边的条数称为重数.

(3)含平行边的图称为多重图.

(4)既无平行边也无环的图称为简单图.

注意：简单图是极其重要的概念

图的同构

色和e6是平行边

重数为2不是简

单图

e?和e3是平行边蓮数为2

和巧不是平行边

不是简单图

5/13

定艾设GNK,E>,为两个无向图(有

6/13

向图)，若存在双射函数f：使得对于任意的

匕，匕已

(片，V》wE、(<匕，当且仅当

(f(V》,f(k/))e6(e6),并且，(为，v){

匕〉)与(f(y),f(v))()的重数相同，则称G与G是同构的，记作6三G.

几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，

但它们都不是充分条件：

①边数相同，顶点数相同

②度数列相同(不计度数的顺序)

③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构

至今没有找到判断两个图同构的多项式时间算法例1试画岀4阶3条边的所有^同构的无向

简单图匚尺7

完全图：”阶无向完全图每个顶点都与其余顶点相邻的〃阶无向简单图.简单性质：边数

/7FA7(

n阶有向完全图：每对顶点之间均有两条方向相反的有向边的n阶有向简单图.

简单性质：边数/7Fn(n-1),4=决2(rH),

二zf二5二

00不同构

入(岀)度列不同

例2判断下述每一对图是否同构:

度数列不同

不同构

度数列相同

但不同构为

什么？

7/13

（1）为5阶完全图鸟⑵为3阶有向完全图⑶称为彼得森图

(1)⑵子图：定爻设Q,G'f是两个图

（1）若V^V且FU£则称"为G的子图，G为"的

母图，记作G0

（2）若G0且f匕乞则称为G的生成子图

（3）若V^V或FUF,称G%G的真子图

（4）设l/yi/且XH0,以*为顶点集，以两端点都在

V，中的所有边为边集的G的子图称作”的导出子图，记作G[V^

（5）设E7且F*0,以为边集，以F冲边关联的

所亓顶点为顶点集的G的子图称作E，的导出子图,记作G[EJ

补图：定艾设*<%£>为”阶无向简单图，以1/为顶点集，所有使G成为完全图/C的添加

边组成的集合为边集的图，称为G的补图，记作G若血G,则称G是自补图.

例对上一页人的所有非同构子图，指出互为补图的每一对子图，并指出哪些是自补图.

7.2通路、回路、图的连通性

简单通（回）路，初级通（回）路，复杂通（回）路

定义给定图（无向或有向的），G中顶点与边的交替序列心…刃/,

（1）若V/（1

则称厂为通路，比是通路的起点，力是通路的终点，/为通路的长度.又若%二匕，则称/

为回路.

（2）若通路（回路）中所有顶点（对于回路，除比二“）各异，则称为初级通路（初

级回路）.初级通路又称作路径，初级回路又称作圈.

（3）若通路（回路）中所有边各异，则称为简单通路（简单回路），否则称为复杂通路

（复杂回路）.

说明：

表示方法

①用顶点和边的交替序列（定艾），如八:比厲“心…©#/

②用边的序列，如Ue©…c

③简单图中，用顶点的序列，如

④非简单图中，可用混合表示法，如厂=%匕6的色旳必岭

环是长度为1的圈，两条平行边构成长度为2的圈.

在无向简单图中，所有圈的长度》3；在有向简单图中，所有圈的长度=2.在两种意义下

计算的圈个数

①定义意义下

在无向图中，一个长度为/(/>3)的圈看作2/个不同的圏.如

VV

2

VQV,V

2

VQVVi,VQV2VVQ,VV^V2V,乃16%迫看作6个不同的圈.

在有向图中，一个长度为/(/>3)的圈看作/个不同的圈.

8/13

②同构意艾下

所有长度相同的圈都是同构的，因而是1个圈.

定理在〃阶图G中，若从顶点匕到VjSv)存在通路，则从匕到匕存在长度小于等于的通

路.

推论在”阶图G中，若从顶点匕到w(匕工匕)存在通路，则从匕到匕存在长度小于等

于的初级通路.定理在一个〃阶图G中，若存在匕到自身的回路，则一定存在匕到自身

长度小于等于”的回路.

推论在一个门阶图G中，若存在匕到自身的简单回路，则一定存在长度小于等于〃的初

级回路.

无向图的连通性

设无向图Q,

〃与卜连通：若"与#之间有通路.规定〃与自身总连通.

连通关系住u.v且"“}是f上的等价关系

连通图：任意两点都连通的图.平凡图是连通图.连通分支：$关于连通关系/?的等价类的

导出子图

设〃/?={%,%,・•・，％},G[K|,G[%],…,GM是G的连通分支，其个数记作p(©二

k.

G是连通图oq(Q二1

短程线与距离

"与1/之间的短程线："与y之间长度最短的通路

("与y连通)

"与#之间的距离dlu,S："与#之间短程线的长度

若"与y不连通，规定dlu,k)=°°.

性质：

d(u,u)>0,且dlu,K)=0Ou=v

dlu,0=

d(u,S+d(v,w)>d{u,w)

点割集与割点

记G-v:从G中删除“及关联的边

G-V':从G中删除X中所有的顶点及关联的边

G-e:从G中删除e

G-E:从G中删除F中所有边

定狡设无向图G=〈V,E>,VrcK若p｛G-V9>p（6）且"ul/p｛G-V“）二q（Q,则称V，

幷G的点割集.若｛诃为点割集，则称#为割点.

例仙如，｛*｝杲点割集,％是割点.

｛%%｝是点割集吗?

9/13

边割集与割边（桥）

定义设无向图XV,E>,E0,若p（G-EJ〉p©且VF〃uF，,Q（GF〃）二q（Q,则称

E，为G的边割集.若｛e｝为边割集，则称e为割边或桥.

在上一页的图中，4,勾，｛①，6,6,①｝,｛©｝等是边割集，

6是桥，｛%C,6,©｝是边割集吗？

几点说明：

您无点割集

〃阶零图既无点割集，也无边割集.

若G连通，「为边割集,则p｛G-E9=2

若G连通，X为点割集,则p｛G-V'）>2

有向图的连通性

设有向图［^

"可达x〃到y有通路.规定"到自身总是可达的.

可达具有自反性和传递性

0弱连通（连通）：基图为无向连通图

0单向连通：Vu,i^eK"可达y或#可达"

0强连通：Vuyi/eK"与#相互可达

强连通=■单向连通=>弱连通

定理（强连通判别法）。强连通当且仅当。中存在经过每个顶点至少一次的回路定理

（单向连通判别法）。单向连通当且仅当。中存在经过每个顶点至少一次的通路

例下图（1）强连通（2）单连通，⑶弱连通0口口

（1）（2）⑶

有向图的短程线与距离

"到卜的短程线：〃到y长度最短的通路（"可达3

〃与1/之间的距离d."到1/的短程线的长度

若〃不可达V,规定d=oo・性质：

d>0,且du=vd<〈v.w>>d注意：没有对称性

7.3图的矩阵表示

无向图的关联矩阵

定义设无向图^=<1<£>,V^{v,Vz,…，KJ,Q{C,G,…，ej,令刃，丿为匕

与①的关联次数，称(％)沁为G的关联矩阵，记为"(0.

性质

10

/13

(1)每一列恰好有两个1或一个2

(2)环叫=也)(/=U,...,«)

⑶£%=2讥

(4)平行边的列相同

有向图的关联矩阵

定艾设无环有向图XV,E>,1^={匕，迤，…，山，日久6,…，令

1,耳为勺的始点

m严0,叫与弓不关联

［一1,叫为勺的终点则称(鸚淙訥D的关

联矩阵，记为M(D).

性质

(1)每一列恰好有一个1和一个-1

(2)第，行1的个数等于dS,-1的个数等于”3,)

(3)1的总个数等于T的总个数，且都等于刃

(4)平行边对应的列相同有向图的邻接矩阵

定义设有向EZ)=,心何七，…,bJ,E={ei，勺,…，邛，令甥为顶点气邻幽顶点专或的条数,

称(a叽朋D的邻接矩阵，记作坦巧,简记为4性质

⑴硝>=/(从

(2)乞甥灯(吩/=哦,..丿

(3)gf=机一一一。中长度为1的通路数

(4)乞即一一一Q中长度为1的回路数

11

/13

Z)中的通路及回路数

定理设/为"阶有向图Z)的邻接矩阵,则川(凶沖元素

硝为D中谬馬长度为/的通路数，皤为＜倒自身长度触的回路数，

ZX40为皿长度为2的通路总数，

Z-lJ-1

£當)为Q中长度为z的回路总数•

Z-1

推电字吊"+/耳...七4@1),则〃冲元素『为Q中长度小于或等于Z的通蹄数，士曙为Q中长度

小于或等于喲回臓•

i-l

有向图的可达矩阵

定义设D=＜卩戶为有向图,山｛叫,七,…，切，令

f0,片可达｝为=仏否则称如如为Q的可达矩阵,记作卩

(巧简记为P性质：

F(Q)主对角线上的元素全为1.

。强连通当且仅当兀0)的元素全为L

例有向翻如銅示，求£42显彳

并回答诸喝乜卜一____4

(1)。中长皮为1,2,3・4的通路苦有多

少条2武中回路分别多少条2、

(2)Q中长劇吁或等于4的通路为多V_

少条？武中有多少条回略？

1

10000

01

10

011

rio

0

0

0

0

1

0_

o'

0

1

0

20

1000'

5001

4010

4001

1

S

1

211

3

314

1

4173

合计

508

长度通路回路

12

/13

例右图所示的有向图刀的可达矩阵为

7.4最短路径及关键路径带权图G^,其中炉:—R.

“(e)称作£的权.(K,v),记w{e)-wfJ・若为，匕不相邻，记

Wij=oo.

设厶是G中的一条路径，Z.的所有边的权之和称作Z.的权，记作

w{L).

〃和1/之间的最短路径：〃和“之间权最小的通路.

£尸啊即5严(Z沪12,vV

£3二卩0涉評5用03)=11・也1*

标号法(ra,1959)

设带杈图(^勺遏炉,其中*亦H'(^0.

设心仙胳…心},求小到其余各顶点的髓路径

P标号(永久性标号仟第吵获得的耳到叮最短路径的权

标号(临时性标号)炉:第涉获得的竹经遙标号顶点到达片的路径的最”收

‘是*倒气的號路径的权的上界

第涉通过集PR,I，在第涉已获得永久性标号}第妙未通迥集炉并片

算法；

1.H获A标号：少・=o,Po={H}97b=7{vi}，H(/=23,…间获了标号：

罗=输.令厂<-1.

2.设必宀「劉鵜T},I；茯亀标号:上汁=4小)•令Pr=Pr-l^{vA，

7>7；-l-b'i}.

若7>0,如垮束.

3.样耳令罗=min矽-),『)•”?}

令d,转2.

nooon

1011

0

13

/13

例1（续）求口到比的號跻g

V1V2v5

001

4OD□DQD

11/Vo

3

86

0D

2

3/vi

8

4

374/V2

10

4

7他9

5

9/伽

w013749

厂二5*'1巧*4屿吨，n（Z>=9

PERT图与关键路径

PERT图（计划评审技术图）

设有向图=3,E>,v^V

卜的后继元集厂（K）={x|xeKe£）

卜的先3区元集厂「（“）二K>e£）

PERT图：满足下述条件的"阶有向带权图卅>,

（1）。是简单图，

（2）。中无回路，

（3）有一个入度为0的顶点，称作始点；有一个出度为0

的顶点，称作终点.

通常边的权表示时间，始点记作厶终点记作仏

关键路径

关键路径：PETR图中从始点到终点的最长路径

匕的最早完成时间TES:从始点“沿最长路径到匕所需的时间

TE{切）=0

TEI匕）二max{TE{v）+巧,|匕已厂'（匕）},7=2,

3,...»n匕的最晚完成时间TLS:在保证终点仏的最早完成时间不增

加的条件下，从始点匕最迟到达匕的吋间

TLS二TEW）

7Z（匕）二min{7Z.（K>）-w,jv^T'（匕）},i-n~,

n~2,...»1

匕的缓冲时间TSS二TLW）-TES,/=1,2,..„/7

匕在关键路径上o75（匕）二0

例2求PERT图中各顶点的最早完成时间，最晩完成

时间，缓冲时间及关键路径.解最早完成时间

血(巧)=0

TE*(卩2)=ma£{0+l}=l

TE(v3)=max{0+2?l+0}=2

TE*(U4)=max{0+32+2}=4

TE*(V5)=max{l+3?4+4}=8

TE(v6)=max{2+4,8+l}=9

T£，(v7)=max{l+4?2+4}=6

TE(v8)=max{9+l,6+6}=12

最晚完成时间

14

/13

几仏)二12

7Z.(1/7)=min{12-6}=6

715)=min{12-1}=117Z.(^)=min{11-1}=10

TLM=min{10-4)=6

7Z(Q二min{6-2,11—4,6-4]=2TLM=min{2-0,10-3,6-4)=2

7Z(ki)=min{2-1,2-2,6-3j=0缓冲时间

TSM=0-0=0

r5(i/2)=2-1=1

TSli/

3

)=2-2=0

75(ui)=6-4=2

TSl^=10-8=2

7^(i4)=11-9=2

75(v7)=6-6=0

75(1^)=12-12=0

关键路径：l/iKJV?