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

复习思考题13若无向图G是n阶k-正则图，则G的补图也是正则图。()若两个无向图的度数列相同，则这两个图同构。(

)画出以(1,1,2)为度数列的两个非同构的图.4.对n阶非连通简单图G=<V,E>

G的边数最少是________；

G的边数最多是________。无向图G的结点集V上的连通关系是偏序关系。()无向图连通性的应用证明：2n个城市，如果每个城市至少可以和另外n个城市可以相互直航，那么这2n个城市中任何两个之间可互相通航(有些可能要通过另外的城市中转)即证明:2n个结点，每个结点的度数

n的简单图是连通的。证明

：（反证法）

设有2n个结点的图G不连通（其中每个结点度数d(v)n），则G中至少包含两个连通分支,而且必有一个分支的结点数

n，而即使这个分支是完全图，其每个结点的度数d(v)

n-1，和图G中每个结点度数d(v)

n矛盾。所以，图G只有一个连通分支，即G是连通的。第5章图的基本概念

5.1无向图及有向图5.2通路、回路、图的连通性5.3图的矩阵表示

5.4最短路径及关键路径与点割集有关的概念

Gv——

从G中删除v及关联的边，如v1GV’——从G中删除V’中所有的顶点及关联边如：V’={v1,v4}G-v1G-{v1,v4}点割集

定义：设无向图G=<V,E>,V’V,V’≠

若p(GV’)>p(G)且V”V’,p(GV”)=p(G),

则称V’为G的点割集.若{v}为点割集,则称v为割点.说明：若G连通,删除V’的所有结点，得到的子图是不连通的。删除V’的任何真子集V”，得到的子图是连通的。举例{v2,v4}，{v3}，{v5}都是点割集，v3,v5都是割点。注意：{v1,v3}不是点割集v1与v6不在任何割集中。

点割集例：{v1,v4}是点割集{v6}是点割集,v6是割点.{v2,v5}

不是点割集

若p(GV’)>p(G)

且

V”V’,p(GV”)=p(G)

边割集

Ge——从G中删除e,如e1GE’——从G中删除E’中所有边，如：E’={e2,e5}定义：设无向图G=<V,E>,EE,若p(GE)>p(G)且EE,

p(GE)=p(G)则称E为G的边割集.若{e}为边割集,则称e为割边或桥.说明：若G连通,E为边割集，则p(GE)=2若G连通,V为点割集，则p(GV)2Kn无点割集n阶零图既无点割集，也无边割集.边割集例：{e1,e2}是边割集，{e1,e3,e5,e6}是边割集，{e8}是边割集，e8是桥，{e7,e9,e5,e6}不是边割集若

p(GE)>p(G)

且

EE,

p(GE)=p(G)重连通图重连通图——指一个没有割点的连通图。若在连通图上至少删去k

个顶点才能破坏图的连通性，则称此图的连通度为k。是连通图，但不是重连通图。重连通图Kn无点割集割点和重连通图在实际中的应用一个表示通信网络的图的连通度越高，其系统越可靠，无论是哪一个站点出现故障或遭到外界破坏，都不影响系统的正常工作；一个航空网若是重连通的，则当某条航线因天气等某种原因关闭时，旅客仍可从别的航线绕道而行；若将大规模的集成电路的关键线路设计成重连通的话，则在某些元件失效的情况下，整个片子的功能不受影响；战争中，仅需破坏敌方运输网

中的割点即可摧毁其运输线。。无向图的关联矩阵定义：无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).

e1e2e3e4e5V1V2V3v4无向图关联矩阵的性质

(4)平行边的列相同。e1e2e3e4e5V1V2V3v4(1)每一列恰好有两个1或一个2(5)vi为孤立点当且仅当第i行全为0。有向图的关联矩阵定义：设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

则称(mij)nm为D的关联矩阵，记为M(D).M(D)=e1e2e3e4

e5V1V2V3v4有向图关联矩阵的性质(1)每一列恰好有一个1和一个-1(2)第i

行1的个数等于d+(vi),

-1的个数等于d-(vi)(3)1的总个数等于-1的总个数,且都等于m(4)平行边对应的列相同M(D)=e1e2e3e4

e5V1V2V3v4定义:

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

V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()nn为D的邻接矩阵,记作A(D),

简记为A.

有向图的邻接矩阵

A(D)=V1V2V3v4v1v2v3v4有向图邻接矩阵的性质A(D)=V1V2V3v4v1v2v3v4

D中的通路及回路数定理

设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.通路和回路可以是初级的、简单的、复杂的D中的通路及回路数说明：An=An-1

A

(矩阵代数乘法)推论设Bl=A+A2+…+Al(l1),则Bl中元素为D中长度≤l的通路数，为D中长度≤l的回路数.A(D)=V1V2V3v4v1v2v3v4D中的通路及回路数举例1例有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？D中的通路及回路数举例1D中长度为1,2,3,4的通路各有多少条？即要分别求A,A2,A3,A4,其矩阵中数之和即为结果D中的通路及回路数举例1D中长度为1,2,3,4的通路各有多少条？即要分别求A,A2,A3,A4,其矩阵中数之和即为结果D中的通路及回路数举例1D中长度为1,2,3,4的通路各有多少条？即要分别求A,A2,A3,A4,其矩阵中数之和即为结果D中的通路及回路数举例1D中长度为1,2,3,4的通路各有多少条？即要分别求A,A2,A3,A4,其矩阵中数之和即为结果D中的通路及回路数举例1

合计508181211331414173

长度通路回路D中的通路及回路数举例2三枚钱币处于反、正、反面，每次只许翻动一枚钱币,问连续翻动三次后，能否出现全正面或全反面?解:引入三元组(q0,q1,q2)来描述

状态：正面为0，反面为1，问题：是否可以翻动3次后，

从Q5Q0或Q5Q7？转化：状态转换图中是否存在从Q5Q0

或Q5Q7的长度为3的通路。(q0,q1,q2)Q00，0，0Q10，0，1Q20，1，0Q30，1，1Q41，0，0Q51，0，1Q61，1，0Q71，1，1D中的通路及回路数举例2

用邻接矩阵表示图：Q0

Q1Q2Q3Q4Q5Q6Q7

Q0

Q1Q2Q3Q4Q5

Q6Q7状态转换图Q5(101)Q4(100)Q7(111)Q1(001)Q6(110)Q0(000)Q2(010)Q3(011)D中的通路及回路数举例2求A的3次幂A3

(Q5,Q0)=0,

(Q5,Q7)=7,所以，连续翻动钱币三次，不能出现全正面，可以出现全反面，有7种翻动方法可以出现全反面.即Q5Q0没有长度为3的通路Q5Q7有7条长度为3的通路Q0

Q1Q2Q3Q4Q5Q6Q7

Q0

Q1Q2Q3Q4Q5

Q6Q7Q5(101)Q4(100)Q7(111)Q1(001)Q6(110)Q0(000)Q2(010)Q3(011)5.4

最短路径、关键路径带权图最短路径与Dijkstra标号法项目网络图与关键路径5.4最短路径及关键路径带权图G=<V,E,W>,其中w:ER.eE,w(e)称作e的权.e=(vi,vj),记w(e)=wij.若vi,vj不相邻,记wij=.通路L的权:——L的所有边的权之和,记作w(L).u和v之间的最短路径:——u和v之间权最小的通路.162417235v0v3v1v4v2v5例:L1=v0v1v3v5,w(L1)=10,

L3=v0v2v4v5,w(L3)=11L2=v0v1v4v5,w(L2)=12,

带权图举例用飞机的飞行距离来赋权

求最短路径的算法——标号法设G=<V,E,W>为n阶简单带权图，wij≥0，

vi,vj

V,若vi,vj不相邻，则wij=求v0到其余顶点的最短路径，先给出符号定义：顶点vi的标号：(li,

pi

)li

——

v0到vi的距离，pi

——

v0到vi的最短路径上vi的前一个顶点，临时标号，永久标号设P={v|v已获得永久标号}设T=V-P为仍为临时标号的顶点集。162417235v0v3v1v4v2v5求最短路径的算法——标号法设带权图G=<V,E,w>,其中eE,w(e)0.设V={v1,v2,,vn},求v1到其余各顶点的最短路径1.令l10,p1,lj+,pj,j=2,3,,n,

P={v1},T=V-{v1},k1,t1./表示空2.对vjT且(vk,vj)E

令lmin{lj,

lk

+wkj}

若l=lk+wkj,则修改标号ljl,

pjvk.求li=min{lj|vjTt}./将vi改为永久标号

令PP{vi},TT-{vi},ki.4.令tt+1,

若t<n,则转2.计算结束后，利用pj通过回溯可得到v1

到vi的最短路径Dijkstra标号法实例例

求v0到v5的最短路径

t

v0

v1

v2

v3

v4

v5

1

(0,)*(+,)(+,)(+,)(+,)(+,)

2(1,v0)*(4,v0)(+,)(+,)(+,)

3(3,v1)*(8,v1)(6,v1)