运筹学-Ch5-图与网络规划

第五章图与网络规划1ppt课件CH5

图与网络规划图的基本知识最小权支撑树问题最大流问题最短有向路问题学习目的§5.1

图的基本知识4ppt课件一.

图Def.

一个图G是指由一集合V(G)和V(G)中某些元素的无序对的集合E(G)所构成的二元组(V(G),E(G)).V(G)称为G的顶点集,其中的元素称为G的顶点(node).E(G)称为G的边集,其中的元素称为G的边(edge).简计V=V(G),E=E(G).如果V和E均为有限集合,则称G为有限图,否则称为无限图.若边集是空集,则称该图为空图,记为;否则称其为非空图.只有一个顶点的图称为平凡图.图中顶点的个数叫做图的阶.连接同一对顶点的边的条数叫做边的重数(multiplicity),若图G中存在重数大于1的边,则称G为一多重图(multigraph).对于图G,设V=,E=.若,则称顶点与是相邻的(adjacent),并称,为边e的端点,也称e与,相关联(incident).如果,且和有公共的端点,则称与是相邻的(邻接).若V中的某顶点和E中任何边均不关联,则称该顶点为孤立点.两个端点重合的边称为环(loop).没有环及没有重数大于1的边的图称为简单图(simplegraph).设有两个图,,它们的顶点集间有一一对应的关系,且使得边之间有如下的关系:设,,,如果,则,而且的重数与的重数相同,这种对应关系叫作同构(isomorphism).同构关系是图之间的一个等价关系,故通常将同构的图看作是相同的.每一对不同的顶点之间均有一条边相连的简单图称为完全图(completegraph).Th.1

:

n阶完全图有条边.

图的每条边有一个端点在中,另一个端点在中.如果图的顶点能分成二个集合与,使得同一集合中的任何两个顶点都不相邻,则称此图为二部(分)图(bipartitegraph).可写成.分划称为图的一个二分划(bipartition).一个完全二分图,是一个具有二分划的简单二分图,其中的每个顶点与的每个顶点都相连.设图G=(V,E),集合.令,则图称为G的补图(complement).图H称为G的子图(subgraph),记作,若,,且H中的边的重数不超过G中对应边的重数.设,且下列三个条件中至少有一个成立:(1)(2)(3)H中至少有一个边的重数小于G中对应边的重数,则说H是G的真子图(propersubgraph).设图G=(V,E),一个满足,的真子图,叫做G的生成或支撑子图(spanningsubgraph).4531245312G的支撑子图设

是图G=(V,E)的顶点集合V的一个非空子集,以作为顶点集,以两端点均在中的边的全体为边集的子图,称为由导出的G的子图,记为,并称是G的点导出子图.若,以中边的所有端点作为点集的子图称为由导出的子图,记为,并称是G的边导出子图.45312G43124312:以和的点集的交为点集,边集的交为边集.:以和的点集的并为点集,边集的并为边集;若和没有公共边,则称它们的边是不重的.设和是G的子图,若和没有公共顶点,则称它们是不相交的;3154263154264263154两个不相交的子图两个边不重的子图Th.2:

设G是没有孤立点的图,其边数为,若包括图G本身和空集在内,则G的所有不同子图的个数为.设,G中与顶点v关联的边的个数(与v关联的每个环算作两条边)称为v(在G中)的度(degree),

记作,或简记为d(v).如果d(v)是奇数,则称顶点v是奇的或奇顶点(奇点);如果d(v)是偶数,则称顶点v是偶的或偶顶点(偶点).显然,若v为孤立点,则d(v)=0,且有:Th.3:

图G中所有顶点的度的和等于边数的2倍,且任意一个图一定有偶数个奇顶点.q—边数图G=(V,E)中的一个顶点序列称为是一条途径(walk)W,若对i=1,‥‥,k,有

.

称为W的起点,称为W的终点,称为W的内部顶点(中间点)

.途径W的长度定义为它所含的边的数目,即为k.也可以用其相应边的序列来表示途径W,这里.315426315264路(12342356)若在W中的顶点互不相同,则称W为一路径(初等链,初级路)(path).315426由到的一条路,若路中的边不重复,则称为简单路.简单图中的任一条路必为简单路,记为.若,则称途径W是闭的.称闭途径W为一个回路或圈(cycle),

如果且构成一路经.31542631526简单路(125346)初级路(12356)长为偶数的圈称为偶圈,长为奇数的圈称为奇圈.Th.4

:

一个图是一条路经当且仅当它中有两个顶点的度为

1,而其余顶点的度均为2.Th.5

:

存在图G的顶点的一个唯一划分,使得这些子集满足:顶点i和j位于同一子集中当且仅当G含有一条i-j路径.Th.6

:

当且仅当一个图无奇圈时,它才是二分图.设u,v为图G中的两个顶点,若在G中存在一条u-v路径,则常称顶点u和v是连通的.如果图G中每对不同的顶点u,v间都有一条路经,则称G为连通图(connectedgraph),否则称为非连通图.顶点之间的连通性是一个等价关系.一个图G,如果能把它画在平面上,且除端点外任意两条边均不相交,则称G可嵌入平面.若图G可以嵌入平面,则称G为可平面图(planargraph).可平面图在平面上的一个嵌入称为一个平面图(planegraph).设为Th5中之划分中的一个子集,则称子图为G的一个连通分支或简称为分支(component),这里表示两个端点均在中的边的集合.显然,当且仅当G只有一个分支时,G是连通图.若图G是不连通的,则其补图连通.二.有向图

有向图D是指由一非空有限集合V(D)和V(D)中某些元素的有序对的集合A(D)所构成的二元组(V(D),A(D)),V(D)称为D的顶点集,其中的元素称为D的顶点.A(D)称为D的弧(arc)集,其中的元素称为D的弧,在不至混淆时,记V=V(D),A=A(D).起点与终点重合的弧称为环.若两条弧有相同的起点和相同的终点,则称这两条弧为重弧.既没有环也没有重弧的有向图称为简单有向图.若u,vV,则弧a=(u,v)A是顶点u和v的有序对.常称u为弧a的起点(尾),v为a的终点(头).

a称为u的出弧,也称为v的入弧.对于有向图D的任一顶点v,以v为起点的弧的数目叫做v的出度(outdegree),记为;以v为终点的弧的数目叫做v的入度(indegree),记为.显然,.u

va对一个有向图D,可以在其顶点集合上作一个图G,使得对应于D的各条弧,G有一条相同端点的边,这个无向图G称为D的基础图(underlyinggraph).一般说来,对应于一个基础图可以有多个有向图.Th.7

:

设D=(V,A)是一有向图，则.这里

表示集合A中的元素数目

.顶点序列称为有向图D=(V,A)中的一条

有向途经(directedwalk),若对有.若该有向途经中的顶点互不相同,则称其为一条有向路径;而如果,且唯一重复的顶点是,则称其为一有向回路或有向圈.Th.8

:

设P是有向图D的一个子图,若1）.2）对任意的

有.

则P是一条有向i-j路径.这里V(P)表示图P的顶点集.Th.9

:

设C是有向图D的一个子图，若1）对任意的

,有.2）对任意的.

则C是一条有向回路.给定有向图D=(V,A),对D中的每条弧a赋予一个实数ω(a),称为弧a的权.ω是A上的一实值函数,称为D的权函数.赋权的有向图D称为网络或赋权有向图,记为D=(V,A,

ω

).赋以权ω的图G称为无向网络或赋权图,记为G=(V,E,

ω

).对于网络D=(V,A,

ω

),若是D的一个子图,则称为D的子网络,并定义为子网络的权.若对有向图D的每一对顶点,均有一条有向路径连接它们,则称D是强连通的(stronglyconnected).若D是强连通的,则它亦是连通的.割边:一条边称为G的割边,如果从G中删去它,则使图的连通分支数严格增加.该条边不包含在G的任何简单回路中.132456G=(V,E),S,T

V,S

T=,{S,T}表示一个端点在S中,而另一个端点在T中的边集合.边割:指G的边集E的形如的一个子集,其中S是V的非空真子集,,且若从G中删去这些边,则G的连通分支数严格增加.割集:G的极小边割.每条割边均为一个割集任何边割都是不相交割集的并21435214352143521435{{2,1},{2,4},{2,3}}割集{{2,3},{2,4},{1,4},{1,5}}割集{{2,3},{4,3},{4,5}{1,5}}不是割集,但为边割{{2,3},{2,4},{1,4}}既非割集,亦非边割三.

图的表示直观：图1对于规模较大的图,则用一个矩阵来记录.有下列两种方式:顶点—边关联矩阵设G=(V,E)是一个非空无环图,定义例如,图1中所示的图G的关联矩阵为则所得到的阶矩阵M(G)＝称为图G的关联矩阵.图的关联矩阵有下列明显的性质:1.每一列恰好有两个非零元素1.2.每一行的元素之和等于对应顶点的度.3.将一个关联矩阵中的两行或两列互换,相当于在同一个图中将两个对应的顶点或边的标号互换.5.n阶图G是连通的当且仅当G的关联矩阵是n-1.4.若G有个连通分支,则通过适当的排列

G的顶点和边所对应的行和列,G的关联矩阵可以写成块对角形式,其中是的关联矩阵.邻接矩阵例如,图1中所示图的邻接矩阵为:设图G=(V,E),令

等于G中顶点与之间的边数,则阶方阵A(G)=()称作G的邻接矩阵.显然,1)

A是一对称矩阵.2)当图G中不存在重数大于1的边时,A的元素只取0和1两个值.对于有向图,亦可用类似于图的方法来表示.例如,图2给出了一个具有五个顶点、九条弧的有向图D=(V,A).图2同样,有向图也可用关联矩阵或邻接矩阵来表示.设D=(V,A)是一非空无环有向图,定义易知,图2中有向图的关联矩阵为则阶矩阵M(D)＝称为图D的顶点—弧关联矩阵.有向图的关联矩阵与图的关联矩阵有着类似的性质:1.

M(D)的每一列恰好有两个非零元素,一个1和一个-1.2.

M(D)的每一行中1的个数等于对应顶点的入度,而-1的个数等于对应顶点的出度.3.将M(D)的两行或两列互换,相当于在D中将两个对应的顶点或边的标号互换.4.若是D的所有连通分支,,则M(D)可以写成块对角形式,其中为的关联矩阵,.§5.2

树32ppt课件Def.

不含圈的图称为无圈图,连通的无圈图称为树.称连通分支都是树的非连通图为森林.

如果T是G的一个支撑子图,且T是树,则称T为G的支撑树,也称为生成树.Th.

:

树的性质:1)

树的顶点数比其边数多1;2)树是无环图且树的任意两个顶点之间有唯一的一条路经;3)在树中去掉任一条边,即变成非连通图;4)在树中任两个不相邻顶点之间加上一条边,则构成一个恰有一个圈的图;5)在树中至少存在两个度数为1的顶点.Proof:

2)

图G是树

任意两个顶点之间恰有一条链(路径)必要性:G连通任两个顶点之间至少有一条链若某两个顶点之间有两条链G中含有圈与树的定义矛盾∴任两个顶点之间恰有一条链充分性:设图G中任两个顶点之间恰有一条链G连通若G中含有圈,则这个圈上任两个顶点之间有两条链与假设矛盾∴G不含圈,于是G是树.5)

设图G=(V,E)是一个树,

p(G)≥2,则G中至少有两个悬挂点.令