《01图论与网络基本知识》由会员分享，可在线阅读，更多相关《01图论与网络基本知识（56页珍藏版）》请在金锄头文库上搜索。
1、图论与网络基本内容授课提纲v几个有意思的例子v图与网络的基本定义v图的连通性v图的矩阵表示v几种特殊的图几个有意思的例子v哥德堡七桥问题哥德堡七桥问题v四色猜想四色猜想vHamilton周游世界游戏周游世界游戏vRamsey 问题问题哥德堡七桥问题 问题问题 能否从某一块陆地出发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。四色猜想四色猜想 问题问题 在任何平面或球面上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。Hamilton 环游世界问题 问题问题 能否从某一顶点出发，走遍每一个顶点一次且仅仅一次，最后回到出发点。Ramsey Ramsey 问题问题v任何六个人中，或有
2、三个人互相认识，或有三个人互任何六个人中，或有三个人互相认识，或有三个人互不认识，二者必居其一。不认识，二者必居其一。v更一般性的问题：若一群人中或有更一般性的问题：若一群人中或有m m个人互相认识，或个人互相认识，或有有n n个人互不认识，则这群人最少得有多少人？记为个人互不认识，则这群人最少得有多少人？记为Ramsey(m,n) 例例 Ramsey(3,3)=6图与网络的基本定义v无向图v有向图v图中的元素及关系v网络v顶点的度数无向图定定义义：无无向向图图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) 有向图定义：有向图定义：有向图D=, 其中其中V称为称为顶点集顶点集, 其元素称其元素称为为顶点顶点或或结点结点; E是是V V的多重子集的多重子集, 称为称为边集边集, 其其元元素称为素称为无向边无向边，简称，简称边边. 有时用有时用
4、V(D)和和E(D)分别表示分别表示V和和E。e1e2e3e4e5e6e7dabc图中的元素及关系端点：端点： ek=(vi, vj) E, 称称vi, vj为为ek的的端点；端点；关联：关联： ek与与vi ( vj)关联；关联；相邻：相邻：具有公共端点的两条边；或者与同一条边关联的两个点称为具有公共端点的两条边；或者与同一条边关联的两个点称为 相邻；相邻；平行边：平行边：具有相同端点的两条边具有相同端点的两条边环：环：两个端点为同一个点的边两个端点为同一个点的边简单图：简单图：无平行边无环的图无平行边无环的图e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dab
5、c带权图（网络）图图G的每一条边的每一条边e附加一个实数附加一个实数w(e), 称作边称作边e的的权权. 图图G连连同同 附附 加加 在在 边边 上上 的的 权权 称称 作作 带带 权权 图图 （ 网网 络络 ） , 记记 作作G=.无向图顶点的度数设设G=为无向图为无向图, v V,v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边G的最大度的最大度 (G)=maxd(v)| v VG的最小度的最小度 (G)=mind(v)| v V例如例如 d(v5)=3, d(
6、v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶点是悬挂顶点, e7是悬挂边是悬挂边, e1是环是环e1e2e3e4e5e6e7v5v1v2v3v4有向图顶点的度数设设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+(a)=4,
7、 d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3e1e2e3e4e5e6e7dabc握手定理定理定理 任何图任何图(无向图和有向图无向图和有向图)的所有顶点度数之和都的所有顶点度数之和都等于边数的等于边数的2倍。倍。证证 图中每条边图中每条边(包括环包括环)均有两个端点均有两个端点, 所以在计算各顶所以在计算各顶点点度数之和时度数之和时, 每条边均提供每条边均提供2度度, m条边共提供条边共提供2m度。度。推论推论 任何图任何图(无向图和有向图无向图和有向图)都有偶数个奇度顶点。都有偶数个奇度顶点。定理定理
8、 有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数证证 每条边恰好提供每条边恰好提供1个入度和个入度和1个出度。个出度。图的连通性v路与圈v无向图的连通性与连通分支v无向图中的最短路与距离v点割集与边割集v点连通度与边连通度v有向图的连通性及其分类v有向图中的最短路与距离路与圈定定义义：给给定定图图G=, G中中顶顶点点与与边边的的交交替替序序列列 =v0e1v1e2elvl.若若 i(1 i l), ei=(vi 1,vi), 则则称称 为为v0到到vl的的通通路路, v0和和vl分分别别为为通通路路的的起起点点和和终终点点, l为为路路的的长度长度.
9、 又若又若v0=vl, 则称则称 为为回路回路. 若若通通路路(回回路路)中中所所有有顶顶点点(对对于于回回路路, 除除v0=vl)各各异异, 则则称称为为初初级级通通路路或或路路(初初级级回回路路或或圈圈). 长长度度为为奇奇数数的的圈圈称称作作奇圈奇圈,长度为偶数的圈称作长度为偶数的圈称作偶圈。偶圈。表示方法表示方法 按按 定定 义义 用用 顶顶 点点 和和 边边 的的 交交 替替 序序 列列 , =v0e1v1e2elvl 用边序列用边序列, =e1e2el 简单图中简单图中, 用顶点序列用顶点序列, =v0v1vl实例非初级的简单通路非初级的简单通路初级通路初级通路初级回路初级回路非初
10、级的非初级的简单回路简单回路无向图连通与连通分支设无向图设无向图G=, u,v Vu与与v连通连通: 若若u与与v之间有通路之间有通路. 规定规定u与自身总是连通的与自身总是连通的.连通图连通图: 任意两点都连通的图任意两点都连通的图. 平凡图是连通图平凡图是连通图连通关系连通关系 :R=| u,v V且且u与与v连通连通. 连通分支连通分支: 连通的子图连通的子图.连通分支数连通分支数:p(G)=k G是连通图是连通图 p(G)=1无向图中的最短路与距离u与与v间的最短路间的最短路:u与与v之间长度最短的通路之间长度最短的通路(设设u与与v连通连通)u与与v间的距离间的距离d(u,v):u与
11、与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)= 点割集与边割集设无向图设无向图G=, v V, e E, VV, EE. 记记G v: 从从G中删除中删除v及关联的边及关联的边G V : 从从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边G e : 从从G中删除中删除eG
12、 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为为割边割边或或桥桥.实例abcde fge1e2e3e4e5e6e7e8e9点割集点割集:e,f ,割点割点:e, fc,d 桥桥: e8,e9边割集边割集:e8,e9,e1,e2,e1, e
13、3, e6, e1, e3, e4, e7点连通度与边连通度定义定义设无向连通图设无向连通图G=, (G)=min|V | | V 是是G的点割集或使的点割集或使G-V 成为平凡图成为平凡图 称为称为G的的点连通度点连通度 (G)=min|E | | E 是是G的边割集的边割集称为称为G的的边连通度边连通度例如例如 (G)= 3 (G)= 3有向图的连通性及其分类设有向图设有向图D=, u,v V, u可达可达v: u到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的.u与与v相互可达相互可达: u可达可达v且且v可达可达uD弱连通弱连通(连通连通): 略去各边的方向所得无向图为
14、连通图略去各边的方向所得无向图为连通图D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达D是强连通的当且仅当是强连通的当且仅当D中存在经过所有顶点的回路中存在经过所有顶点的回路D是单向连通的当且仅当是单向连通的当且仅当D中存在经过所有顶点的通路中存在经过所有顶点的通路实例 强连通强连通单连通单连通弱连通弱连通有向图中的最短路和距离u到到v的最短路的最短路: u到到v长度最短的通路长度最短的通路 (设设u可达可达v)距离距离d: u到到v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=.性质：性质： d 0,
15、且且d=0 u=v d+d d 注意注意: 没有对称性没有对称性图的矩阵表示v关联矩阵v邻接矩阵无向图的关联矩阵设无向图设无向图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 e1e2e3e4e5e6v5v1v2v3v4有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩
16、阵, 记为记为M(D).设无环有向图设无环有向图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 0无向图的邻接矩阵设无向图设无向图G=, V=v1, v2, , vn, 令令aij为为vi与与vj的之的之间边的数目间边的数目, 称称(aij)n n为为G的邻接矩阵的邻接矩阵,记为记为A(G). aij的可的可能取值为能取值为:0,1,2例如例如e1e2e3e4e5e6v5v1v2v3v4A(G)
17、= 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 有向图的邻接矩阵设无向图设无向图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 01 0 2 0带权图的邻接矩阵设无向图设无向图W=, V=v1, v2, , vn, 令令aij为为vi与与vj的的之间边的长度之间边的长度, （到自身记为（到自身记为0；若有平行边取较小值；若有平行边
18、取较小值,无无边记为无穷）称边记为无穷）称(wij)n 为为W的邻接矩阵的邻接矩阵,记为记为A(W). 5v1v2v3v4v5v6843752618完全图与正则图无向完全图无向完全图: 每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图.n阶无向完全图记作阶无向完全图记作Kn, 顶点数顶点数n, 边数边数m=n(n-1)/2, = =n-1有有向向完完全全图图: 每每对对顶顶点点之之间间均均有有两两条条方方向向相相反反的的边边的的有有向向简单图简单图.顶点数顶点数n, 边数边数m=n(n-1), += += -= -=n-1, = =2(n-1)k-正则图正则图: 每个顶点的
19、度数均为每个顶点的度数均为k的无向简单图的无向简单图顶点数顶点数n, 边数边数m=kn/2实例K3K53阶有向完全图阶有向完全图2正则图正则图4正则图正则图 3正则图正则图彼得松图彼得松图圈图与轮图无无向向圈圈图图Cn=, 其其中中V=v1,v2,vn, E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1), n 3有向圈图有向圈图Cn=, 其中其中V=v1,v2,vn, E=, n 3轮图轮图Wn:无向圈图无向圈图Cn-1内放一个顶点内放一个顶点, 且与圈图的每个顶且与圈图的每个顶点之间恰有一条边点之间恰有一条边, n 4方体图n方体图方体图Qn=是是2n阶无向简单图阶无向
20、简单图, 其中其中 V=v|v=a1a2an, ai=0,1, i=1,2,n E=(u,v)| u,v V u与与v恰好有一位数字不同恰好有一位数字不同. 0100011011000 001010 011110100111101二部图（二分图）定义定义 设无向图设无向图 G=, 若能将若能将V 分成分成V1 和和 V2 使得使得V1 V2=V, V1 V2=, 且且G中的每条边的两个端点都一个中的每条边的两个端点都一个属于属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简单图, 且且V1中每
21、个中每个顶点均与顶点均与V2中每个顶点都相邻中每个顶点都相邻, 则称则称G为为完全二部图完全二部图, 记记为为Kr,s, 其中其中r=|V1|, s=|V2|. K23K33二部图的判别定理定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇长度中无奇长度的回路的回路证证 必要性必要性. 设设G=是二部图是二部图, 每条边只能从每条边只能从V1到到V2, 或从或从V2到到V1, 故任何回路必为偶长度故任何回路必为偶长度.充分性充分性. 不妨设不妨设G至少有一条边且连通至少有一条边且连通. 取任一顶点取任一顶点u, 令令 V1=v | v V d(v,u)为偶数为偶数, V2=v
22、| 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是一条回路是一条回路, 其长度为奇数其长度为奇数, 与假设矛盾与假设矛盾. 同理可同理可证证V2中任意两点不相邻中任意两点不相邻. 实例非二部图非二部图非二部图非二部图实例例例1 某中学有某中学有3个课外活动小组个课外活动小组:数学组数学组, 计算机组和生物计算机组和生物组组. 有赵有赵,钱钱,孙孙,李李,周周5名学生名学生, 问分别在下述问分别在下述
23、3种情况下种情况下, 能能否选出否选出3人各任一个组的组长人各任一个组的组长?(1) 赵赵, 钱为数学组成员钱为数学组成员, 赵赵,孙孙,李为计算机组成员李为计算机组成员, 孙孙,李李,周为生物组成员周为生物组成员.(2) 赵为数学组成员赵为数学组成员, 钱钱,孙孙,李为计算机组成员李为计算机组成员, 钱钱,孙孙,李李,周周为生物组成员为生物组成员.(3) 赵为数学组和计算机组成员赵为数学组和计算机组成员, 钱钱,孙孙,李李,周为生物组成员周为生物组成员.实例(续)解解(1),(2)有多种方案有多种方案, (3) 不不可能可能(1)数数计计生生赵赵钱钱 孙孙李李 周周(2)数数计计生生赵赵钱钱
24、孙孙李李周周(3)数数计计生生赵赵钱钱 孙孙李李周周欧拉图哥尼斯堡七桥哥尼斯堡七桥欧拉图欧拉通路欧拉通路:经过所有顶点且每条边恰好经过一次的通路经过所有顶点且每条边恰好经过一次的通路 欧拉回路欧拉回路:经过所有顶点且每条边恰好经过一次的回路经过所有顶点且每条边恰好经过一次的回路欧拉图欧拉图:有欧拉回路的图有欧拉回路的图说明：说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用规定平凡图为欧拉图规定平凡图为欧拉图欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路环不影响图的欧拉性环不影响图的欧拉性欧拉图判别定理定理定理6.8 无无向图向图G具有欧拉回路当且
25、仅当具有欧拉回路当且仅当G是连通的且无是连通的且无奇度顶点奇度顶点. 无向图无向图G具有欧拉通路、但没有欧拉回路当且仅当具有欧拉通路、但没有欧拉回路当且仅当G是连是连通的且有通的且有2个奇度顶点个奇度顶点, 其余顶点均为偶度数的其余顶点均为偶度数的. 这这2个奇个奇度顶点是每条欧拉通路的端点度顶点是每条欧拉通路的端点.推论推论 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通的且无奇度顶点是连通的且无奇度顶点实例无欧拉通路无欧拉通路欧拉图欧拉图欧拉图欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图无欧拉通路无欧拉通路欧拉图判别定理(续)定理定理6.9 有向图
26、有向图D有欧拉回路当且仅当有欧拉回路当且仅当D是连通的且所有是连通的且所有顶点的入度等于出度顶点的入度等于出度.有向图有向图D有欧拉通路、但没有欧拉回路当且仅当有欧拉通路、但没有欧拉回路当且仅当D是连通是连通的且有一个顶点的入度比出度大的且有一个顶点的入度比出度大1、一个顶点的入度比出、一个顶点的入度比出度小度小1, 其余的顶点的入度等于出度其余的顶点的入度等于出度.推论推论 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是连通的且所有顶点的是连通的且所有顶点的入度等于出度入度等于出度.实例欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路无欧拉通路
27、无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路周游世界问题(W.Hamilton, 1859年)哈密顿回路与哈密顿通路哈密顿通路哈密顿通路: : 经过图中所有顶点一次且仅一次的通路经过图中所有顶点一次且仅一次的通路. .哈密顿回路哈密顿回路: : 经过图中所有顶点一次且仅一次的回路经过图中所有顶点一次且仅一次的回路. .哈密顿图哈密顿图: : 具有哈密顿回路的图具有哈密顿回路的图. .说明：说明：哈密顿通路是初级通路哈密顿通路是初级通路哈密顿回路是初级回路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路有哈密顿通路不一定有哈密顿回路环与平行边不影响图的哈密顿性环与平行边不影响图的哈密顿性
28、哈密顿图的必要条件定理定理 若无向图若无向图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不是哈密顿图不是哈密顿图推论推论 有割点的图不是哈密顿图有割点的图不是哈密顿图实例例例2 证明下述各图不是哈密顿图证明下述各图不是哈密顿图:(a)(b)(c)(c) 中存在哈密顿通路中存在哈密顿通路实例例例3 证明右图不是哈密顿图证明右图不是哈密顿图
29、证证 假设存在一条哈密顿回路假设存在一条哈密顿回路, a,f,g是是2度顶点度顶点, 边边(a,c), (f,c)和和(g,c)必在这条哈密顿回路上必在这条哈密顿回路上,从而点从而点c出现出现3次次, 矛盾矛盾.abcde fg此外此外, 该图满足定理该图满足定理6.10的条件的条件, 这表明此条件是必要、这表明此条件是必要、而不充分的而不充分的.又又, 该图有哈密顿通路该图有哈密顿通路.存在哈密顿回路(通路)的充分条件定理定理设设G是是n(n 3)阶无向简单图阶无向简单图, 若任意两个不相邻若任意两个不相邻的顶点的度数之和大于等于的顶点的度数之和大于等于n 1, 则则G中存在哈密顿通路中存在
30、哈密顿通路;若任意两个不相邻的顶点的度数之和大于等于若任意两个不相邻的顶点的度数之和大于等于n, 则则G中中存在哈密顿回路存在哈密顿回路, 即即G为哈密顿图为哈密顿图.推论推论 设设G是是n(n 3)阶无向简单图阶无向简单图, 若若 (G) n/2, 则则G是哈密是哈密顿图顿图当当n 3时时, Kn是哈密顿图是哈密顿图; 当当r=s 2时时, Kr,s是哈密顿图是哈密顿图.定理定理设设D是是n(n 2)阶有向图阶有向图, 若略去所有边的方向后若略去所有边的方向后所得无向图中含子图所得无向图中含子图Kn, 则则D中有哈密顿通路中有哈密顿通路.应用例例4 有有7个人个人, A会讲英语会讲英语, B会讲英语和汉语会讲英语和汉语, C会讲英语、会讲英语、意大利语和俄语意大利语和俄语, D会讲日语和汉语会讲日语和汉语, E会讲德语和意大利会讲德语和意大利语语, F会讲法语、日语和俄语会讲法语、日语和俄语, G会讲法语和德语会讲法语和德语. 问能否将问能否将他们沿圆桌安排就坐成一圈他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人使得每个人都能与两旁的人交谈交谈?解解作无向图作无向图, 每人是一个顶点每人是一个顶点, 2人之间有边人之间有边他们有共同的语言他们有共同的语言.ABCDEFGACEGFDBA是一条哈密顿回路是一条哈密顿回路,按此顺序就坐即可按此顺序就坐即可.
