图论与网络基本知识

1、1图论与网络基本内容2授课提纲v几个有意思的例子v图与网络的基本定义v图的连通性v图的矩阵表示v几种特殊的图3几个有意思的例子v哥德堡七桥问题哥德堡七桥问题v四色猜想四色猜想vHamilton周游世界游戏周游世界游戏vRamsey 问题问题4哥德堡七桥问题 问题问题 能否从某一块陆地出发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。5四色猜想四色猜想 问题问题 在任何平面或球面上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。6Hamilton 环游世界问题 问题问题 能否从某一顶点出发，走遍每一个顶点一次且仅仅一次，最后回到出发点。7Ramsey Ramsey 问题问题v任何

2、六个人中，或有三个人互相认识，或有三个人互任何六个人中，或有三个人互相认识，或有三个人互不认识，二者必居其一。不认识，二者必居其一。v更一般性的问题：若一群人中或有更一般性的问题：若一群人中或有m m个人互相认识，或个人互相认识，或有有n n个人互不认识，则这群人最少得有多少人？记为个人互不认识，则这群人最少得有多少人？记为Ramsey(m,n) 例例 Ramsey(3,3)=68图与网络的基本定义v无向图v有向图v图中的元素及关系v网络v顶点的度数9无向图定义：无向图定义：无向图G=, 其中其中V称为称为顶点集顶点集, 其元素称其元素称为为顶点顶点或或结点结点; E是是V V的多重子集的多重

3、子集, 称为称为边集边集, 其其元素元素称为称为无向边无向边，简称，简称边边. 有时用有时用V(G)和和E(G)分别表示分别表示V和和E。e1e2e3e4e5e6e7v5v1v2v3v4例如例如, G=如图所示如图所示, 其中其中V=v1, v2, ,v5 E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 10有向图定义：有向图定义：有向图D=, 其中其中V称为称为顶点集顶点集, 其元素称其元素称为为顶点顶点或或结点结点; E是是V V的多重子集的多重子集, 称为称为边集边集, 其其元元素称为素称为无向边无向边，简称

4、，简称边边. 有时用有时用V(D)和和E(D)分别表示分别表示V和和E。e1e2e3e4e5e6e7dabc11图中的元素及关系端点：端点： ek=(vi, vj) E, 称称vi, vj为为ek的的端点；端点；关联：关联： ek与与vi ( vj)关联；关联；相邻：相邻：具有公共端点的两条边；或者与同一条边关联的两个点称为具有公共端点的两条边；或者与同一条边关联的两个点称为 相邻；相邻；平行边：平行边：具有相同端点的两条边具有相同端点的两条边环：环：两个端点为同一个点的边两个端点为同一个点的边简单图：简单图：无平行边无环的图无平行边无环的图e1e2e3e4e5e6e7v5v1v2v3v4e1

5、e2e3e4e5e6e7dabc12带权图（网络）图图G的每一条边的每一条边e附加一个实数附加一个实数w(e), 称作边称作边e的的权权. 图图G连连同附加在边上的权称作同附加在边上的权称作带权图（网络）带权图（网络）, 记作记作G=.13无向图顶点的度数设设G=为无向图为无向图, v V,v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边G的最大度的最大度 (G)=maxd(v)| v VG的最小度的最小度 (G)=mind(v)| v V例如例如 d(v5)=3,

6、 d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶点是悬挂顶点, e7是悬挂边是悬挂边, e1是环是环e1e2e3e4e5e6e7v5v1v2v3v414有向图顶点的度数设设D=为有向图为有向图, v V,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+(

7、a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3e1e2e3e4e5e6e7dabc15握手定理定理定理 任何图任何图(无向图和有向图无向图和有向图)的所有顶点度数之和都的所有顶点度数之和都等于边数的等于边数的2倍。倍。证证 图中每条边图中每条边(包括环包括环)均有两个端点均有两个端点, 所以在计算各顶点所以在计算各顶点度数之和时度数之和时, 每条边均提供每条边均提供2度度, m条边共提供条边共提供2m度。度。推论推论 任何图任何图(无向图和有向图无向图和有向图)都有偶数个奇度顶点。都有偶数个奇度

8、顶点。定理定理 有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数证证 每条边恰好提供每条边恰好提供1个入度和个入度和1个出度。个出度。16图的连通性v路与圈v无向图的连通性与连通分支v无向图中的最短路与距离v点割集与边割集v点连通度与边连通度v有向图的连通性及其分类v有向图中的最短路与距离17路与圈定义：定义：给定图给定图G=, G中顶点与边的交替序列中顶点与边的交替序列 =v0e1v1e2elvl.若若 i(1 i l), ei=(vi 1,vi), 则称则称 为为v0到到vl的的通路通路, v0和和vl分别为通路的分别为通路的起点起点和和终点终点,

9、l为为路的长路的长度度. 又若又若v0=vl, 则称则称 为为回路回路. 若通路若通路(回路回路)中所有顶点中所有顶点(对于回路对于回路, 除除v0=vl)各异各异, 则称则称为为初级通路初级通路或或路路(初级回路初级回路或或圈圈). 长度为奇数的圈称作长度为奇数的圈称作奇圈奇圈,长度为偶数的圈称作长度为偶数的圈称作偶圈。偶圈。18表示方法表示方法 按 定 义 用 顶 点 和 边 的 交 替 序 列按 定 义 用 顶 点 和 边 的 交 替 序 列 , =v0e1v1e2elvl 用边序列用边序列, =e1e2el 简单图中简单图中, 用顶点序列用顶点序列, =v0v1vl19实例非初级的简单

10、通路非初级的简单通路初级通路初级通路初级回路初级回路非初级的非初级的简单回路简单回路20无向图连通与连通分支设无向图设无向图G=, u,v Vu与与v连通连通: 若若u与与v之间有通路之间有通路. 规定规定u与自身总是连通的与自身总是连通的.连通图连通图: 任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图连通关系连通关系 :R=| u,v V且且u与与v连通连通. 连通分支连通分支: 连通的子图连通的子图.连通分支数连通分支数:p(G)=k G是连通图是连通图 p(G)=121无向图中的最短路与距离u与与v间的最短路间的最短路:u与与v之间长度最短的通路之间长度最短的通路(

11、设设u与与v连通连通)u与与v间的距离间的距离d(u,v):u与与v之间短程线的长度之间短程线的长度若若u与与v不连通不连通, 规定规定d(u,v)=.性质：性质：(1) d(u,v) 0, 且且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w) d(u,w) abcde f ghi例如例如 a与与e之间的短程线之间的短程线:ace,afe. d(a,e)=2, d(a,h)= 22点割集与边割集设无向图设无向图G=, v V, e E, VV, EE. 记记G v: 从从G中删除中删除v及关联的边及关联的边G V : 从从G中删除中删除V 中所有的顶

12、点及关联的边中所有的顶点及关联的边G e : 从从G中删除中删除eG E : 从从G中删除中删除E 中所有边中所有边定义定义设无向图设无向图G=, VV, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 则称则称V 为为G的的点割集点割集. 若若v为点为点割集割集, 则称则称v为为割点割点.设设EE, 若若p(G E )p(G)且且 E E , p(G E )=p(G), 则则称称E 为为G的的边割集边割集. 若若e为边割集为边割集, 则称则称e为为割边割边或或桥桥.23实例abcde fge1e2e3e4e5e6e7e8e9点割集点割集:e,f ,割点割点: e, f

13、c,d 桥桥: e8, e9边割集边割集:e8,e9, e1,e2,e1, e3, e6, e1, e3, e4, e724点连通度与边连通度定义定义设无向连通图设无向连通图G=, (G)=min|V | | V 是是G的点割集或使的点割集或使G-V 成为平凡图成为平凡图 称为称为G的的点连通度点连通度 (G)=min|E | | E 是是G的边割集的边割集称为称为G的的边连通度边连通度例如例如 (G)= 3 (G)= 325有向图的连通性及其分类设有向图设有向图D=, u,v V, u可达可达v: u到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的.u与与v相互可达相互可达:

14、 u可达可达v且且v可达可达uD弱连通弱连通(连通连通): 略去各边的方向所得无向图为连通图略去各边的方向所得无向图为连通图D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达D是强连通的当且仅当是强连通的当且仅当D中存在经过所有顶点的回路中存在经过所有顶点的回路D是单向连通的当且仅当是单向连通的当且仅当D中存在经过所有顶点的通路中存在经过所有顶点的通路26实例强连通强连通单连通单连通弱连通弱连通27有向图中的最短路和距离u到到v的最短路的最短路: u到到v长度最短的通路长度最短的通路 (设设u可达可达v)距离距离d: u到到

15、v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=.性质：性质： d 0, 且且d=0 u=v d+d d 注意注意: 没有对称性没有对称性28图的矩阵表示v关联矩阵v邻接矩阵29无向图的关联矩阵设无向图设无向图G=, V=v1, v2, , vn, E=e1, e2, , em. 令令mij为为vi与与ej的关联次数的关联次数, 称称(mij)n m为为G的关联矩阵的关联矩阵, 记记为为M(G). mij的可能取值为的可能取值为:0,1,2例如例如M(G)=2 1 1 0 0 00 1 0 1 1 10 0 0 0 1 10 0 0 0 0 00 0 1 1 0 0 e1e2

16、e3e4e5e6v5v1v2v3v430有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩阵, 记为记为M(D).的的终终点点为为，不不关关联联与与，的的始始点点为为jijijiijevevevm10,1设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em. 令令v1v2v3v4e2e1e3e4e5e6e7M(D)=-1 1 0 0 0 1 1 0 -1 1 0 0 0 0 0 0 -1 -1 -1 1 -1 1 0 0 1 1 0 031无向图的邻接矩阵设无向图设无向图G=, V=v1, v2, , vn, 令令aij为为vi与与vj的之

17、的之间边的数目间边的数目, 称称(aij)n n为为G的邻接矩阵的邻接矩阵,记为记为A(G). aij的可的可能取值为能取值为:0,1,2例如例如e1e2e3e4e5e6v5v1v2v3v4A(G)= 1 1 0 0 1 1 0 2 0 1 0 2 0 0 0 0 0 0 0 0 1 1 0 0 0 32有向图的邻接矩阵设无向图设无向图D=, V=v1, v2, , vn, 令令aij为为vi到到vj的边的边的数目的数目, 称称(aij)n n为为G的邻接矩阵的邻接矩阵,记为记为A(G). aij的可的可能取值为能取值为:0,1,2v1v2v3v4A=1 1 0 00 0 1 01 0 0 0

18、1 0 2 033带权图的邻接矩阵设无向图设无向图W=, V=v1, v2, , vn, 令令aij为为vi与与vj的的之间边的长度之间边的长度, （到自身记为（到自身记为0；若有平行边取较小值；若有平行边取较小值,无无边记为无穷）称边记为无穷）称(wij)n 为为W的邻接矩阵的邻接矩阵,记为记为A(W). 5v1v2v3v4v5v684375261834完全图与正则图无向完全图无向完全图: 每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图.n阶无向完全图记作阶无向完全图记作Kn, 顶点数顶点数n, 边数边数m=n(n-1)/2, = =n-1有向完全图有向完全图: 每对顶

19、点之间均有两条方向相反的边的有向每对顶点之间均有两条方向相反的边的有向简单图简单图.顶点数顶点数n, 边数边数m=n(n-1), += += -= -=n-1, = =2(n-1)k-正则图正则图: 每个顶点的度数均为每个顶点的度数均为k的无向简单图的无向简单图顶点数顶点数n, 边数边数m=kn/235实例K3K53阶有向完全图阶有向完全图2正则图正则图4正则图正则图 3正则图正则图彼得松图彼得松图36圈图与轮图无 向 圈 图无 向 圈 图 Cn= , 其 中其 中 V = v1, v2, , vn , E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1), n 3有向圈图有

20、向圈图Cn=, 其中其中V=v1,v2,vn, E=, n 3轮图轮图Wn:无向圈图无向圈图Cn-1内放一个顶点内放一个顶点, 且与圈图的每个顶且与圈图的每个顶点之间恰有一条边点之间恰有一条边, n 437方体图n方体图方体图Qn=是是2n阶无向简单图阶无向简单图, 其中其中 V=v|v=a1a2an, ai=0,1, i=1,2,n E=(u,v)| u,v V u与与v恰好有一位数字不同恰好有一位数字不同. 0100011011000 001010 01111010011110138二部图（二分图）定义定义 设无向图设无向图 G=, 若能将若能将V 分成分成V1 和和 V2 使得使得V1

21、V2=V, V1 V2=, 且且G中的每条边的两个端点都一个中的每条边的两个端点都一个属于属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简单图, 且且V1中每个中每个顶点均与顶点均与V2中每个顶点都相邻中每个顶点都相邻, 则称则称G为为完全二部图完全二部图, 记记为为Kr,s, 其中其中r=|V1|, s=|V2|. K23K3339二部图的判别定理定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇长度中无奇长度的回路的回路证证 必要性必要性. 设设G=是二部图是二部图, 每

22、条边只能从每条边只能从V1到到V2, 或从或从V2到到V1, 故任何回路必为偶长度故任何回路必为偶长度.充分性充分性. 不妨设不妨设G至少有一条边且连通至少有一条边且连通. 取任一顶点取任一顶点u, 令令 V1=v | v V d(v,u)为偶数为偶数, V2=v | v V d(v,u)为奇数为奇数则则V1 V2=V, V1 V2=. 先证先证V1中任意两点不相邻中任意两点不相邻. 假设存假设存在在s,t V1, e=(s,t) E. 设设1, 2分别是分别是u到到s,t的短程线的短程线, 则则1 e 2是一条回路是一条回路, 其长度为奇数其长度为奇数, 与假设矛盾与假设矛盾. 同理可同理可

23、证证V2中任意两点不相邻中任意两点不相邻. 40实例非二部图非二部图非二部图非二部图41实例例例1 某中学有某中学有3个课外活动小组个课外活动小组:数学组数学组, 计算机组和生物计算机组和生物组组. 有赵有赵,钱钱,孙孙,李李,周周5名学生名学生, 问分别在下述问分别在下述3种情况下种情况下, 能能否选出否选出3人各任一个组的组长人各任一个组的组长?(1) 赵赵, 钱为数学组成员钱为数学组成员, 赵赵,孙孙,李为计算机组成员李为计算机组成员, 孙孙,李李,周为生物组成员周为生物组成员.(2) 赵为数学组成员赵为数学组成员, 钱钱,孙孙,李为计算机组成员李为计算机组成员, 钱钱,孙孙,李李,周周

24、为生物组成员为生物组成员.(3) 赵为数学组和计算机组成员赵为数学组和计算机组成员, 钱钱,孙孙,李李,周为生物组成员周为生物组成员.42实例(续)解解(1),(2)有多种方案有多种方案, (3) 不可能不可能(1)数数计计生生赵赵 钱钱 孙孙 李李 周周(2)数数计计生生赵赵 钱钱 孙孙 李李 周周(3)数数计计生生赵赵 钱钱 孙孙 李李 周周43欧拉图哥尼斯堡七桥哥尼斯堡七桥44欧拉图欧拉通路欧拉通路:经过所有顶点且每条边恰好经过一次的通路经过所有顶点且每条边恰好经过一次的通路 欧拉回路欧拉回路:经过所有顶点且每条边恰好经过一次的回路经过所有顶点且每条边恰好经过一次的回路欧拉图欧拉图:有欧

25、拉回路的图有欧拉回路的图说明：说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用规定平凡图为欧拉图规定平凡图为欧拉图欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路环不影响图的欧拉性环不影响图的欧拉性45欧拉图判别定理定理定理6.8 无无向图向图G具有欧拉回路当且仅当具有欧拉回路当且仅当G是连通的且无是连通的且无奇度顶点奇度顶点. 无向图无向图G具有欧拉通路、但没有欧拉回路当且仅当具有欧拉通路、但没有欧拉回路当且仅当G是连是连通的且有通的且有2个奇度顶点个奇度顶点, 其余顶点均为偶度数的其余顶点均为偶度数的. 这这2个奇个奇度顶点是每条欧拉通路的端点

26、度顶点是每条欧拉通路的端点.推论推论 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通的且无奇度顶点是连通的且无奇度顶点46实例无欧拉通路无欧拉通路欧拉图欧拉图欧拉图欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图无欧拉通路无欧拉通路47欧拉图判别定理(续)定理定理6.9 有向图有向图D有欧拉回路当且仅当有欧拉回路当且仅当D是连通的且所有是连通的且所有顶点的入度等于出度顶点的入度等于出度.有向图有向图D有欧拉通路、但没有欧拉回路当且仅当有欧拉通路、但没有欧拉回路当且仅当D是连通是连通的且有一个顶点的入度比出度大的且有一个顶点的入度比出度大1、一个顶点的入度比

27、出、一个顶点的入度比出度小度小1, 其余的顶点的入度等于出度其余的顶点的入度等于出度.推论推论 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是连通的且所有顶点的是连通的且所有顶点的入度等于出度入度等于出度.48实例欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路无欧拉通路无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路49周游世界问题(W.Hamilton, 1859年)50哈密顿回路与哈密顿通路哈密顿通路哈密顿通路: : 经过图中所有顶点一次且仅一次的通路经过图中所有顶点一次且仅一次的通路. .哈密顿回路哈密顿回路: : 经过图中所有顶点一次

28、且仅一次的回路经过图中所有顶点一次且仅一次的回路. .哈密顿图哈密顿图: : 具有哈密顿回路的图具有哈密顿回路的图. .说明：说明：哈密顿通路是初级通路哈密顿通路是初级通路哈密顿回路是初级回路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路有哈密顿通路不一定有哈密顿回路环与平行边不影响图的哈密顿性环与平行边不影响图的哈密顿性51哈密顿图的必要条件定理定理 若无向图若无向图G=是哈密顿图是哈密顿图, 则对于则对于V的任意的任意非空真子集非空真子集V1均有均有 p(G V1) |V1|.证证 设设C为为G中一条哈密顿回路中一条哈密顿回路, 有有p(C V1) |V1|. 又因为又因为C G, 故故 p(G V1) p(C V1) |V1|. 例如例如 当当rs时时, Kr,s不是哈密顿图不是哈密顿图推论推论 有割点的图不是哈密顿图有割点的图不是哈密顿图52实例例例2 证明下述各图不是哈密顿图证明下述各图不是哈密顿图:(a)(