ORXJTU第五章 图与网络规划CH 5 图与网络规划图的根本知的根本知识最小最小权支撑支撑树问题最大流最大流问题最短有向路最短有向路问题ORXJTU第五章 图与网络规划学习目的学习目的 5.1 图的根本知识ORXJTU第五章 图与网络规划一一. 图图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) .ORXJTU第五章 图与网络规划对于图对于图G, 设设V= , E= .假设假设 , 那么称顶点那么称顶点 与与 是是相邻的相邻的(adjacent), 并称并称 , 为边为边e的的端点端点,也称也称e与与 , 相关联相关联(incident) .假设假设 , 且且 和和 有公共的端点有公共的端点,那么称那么称 与与 是相邻的是相邻的(邻接邻接) .假假设V中的某中的某顶点和点和E中任何中任何边均不关均不关联,那么称那么称该顶点点为孤立点孤立点 .两个端点重合的两个端点重合的边称称为环(loop) .没有没有环及没有重数大于及没有重数大于1的的边的的图称称为简单图(simple graph) .ORXJTU第五章 图与网络规划 设有两个图设有两个图 , , 它们的顶点集间它们的顶点集间有一一对应的关系有一一对应的关系, 且使得边之间有如下的关系且使得边之间有如下的关系: 设设 , , , 假设假设 ,那么那么 , 而且而且 的重数与的重数与 的重数一样的重数一样, 这种对应关系叫作这种对应关系叫作同构同构(isomorphism) . 同构关系是同构关系是图之之间的一个等价关系的一个等价关系, 故通常将同构的故通常将同构的图看作是一看作是一样的的 . 每一每一对不同的不同的顶点之点之间均有一条均有一条边相相连的的简单图称称为完全完全图(complete graph) .Th.1 : n阶完全完全图有有 条边 .ORXJTU第五章 图与网络规划 图的每条边图的每条边有一个端点在有一个端点在 中中,另一个端点在另一个端点在 中中. 假设图的顶点能分成二个集合假设图的顶点能分成二个集合 与与 , 使得同一集合中的任何两个顶点都不相邻使得同一集合中的任何两个顶点都不相邻, 那么称此图为二部那么称此图为二部(分分)图图(bipartite graph) .可写成可写成 . 分划分划 称为图的一个二分划称为图的一个二分划(bipartition) . 一个完全二分图一个完全二分图, 是一个具有二分划是一个具有二分划 的简单二分图的简单二分图, 其中其中 的每个顶点与的每个顶点与 的每个顶点都相连的每个顶点都相连 .ORXJTU第五章 图与网络规划设图设图G = (V, E ) , 集合集合 .令令 , 那么图那么图 称为称为G的的补图补图(complement) . 图图H称为称为G的子图的子图(subgraph),记记作作 ,假设假设 , ,且且H中的边的重数不超越中的边的重数不超越G中对应边中对应边的重数的重数 .ORXJTU第五章 图与网络规划 设设 , 且以下三个条件中至少且以下三个条件中至少有一个成立有一个成立 : (1) (2) (3) H中至少有一个边的中至少有一个边的 重数小于重数小于G中对应边的重数中对应边的重数 ,那么说那么说H是是G的真子图的真子图(proper subgraph). 设图设图G = (V, E ), 一个满足一个满足 , 的真子图的真子图, 叫做叫做G的生成或支撑子的生成或支撑子图图(spanning subgraph) .4531245312G的支撑子的支撑子图ORXJTU第五章 图与网络规划 设设 是图是图G = (V, E )的顶点集合的顶点集合V的一个非空子集的一个非空子集, 以以 作为顶点集作为顶点集, 以以两端点均在两端点均在 中的边的全体为边集的中的边的全体为边集的子图子图, 称为由称为由 导出的导出的G的子图的子图, 记为记为 , 并称并称 是是G的点导出子图的点导出子图 . 假设假设 , 以以 中边的一切端点中边的一切端点作作为点集的子图称为由为点集的子图称为由 导出的子图导出的子图,记记为为 ,并称并称 是是G的边导出子图的边导出子图 .45312G43124312ORXJTU第五章 图与网络规划: 以以 和和 的点集的交为点集的点集的交为点集, 边集的交为边集边集的交为边集 .: 以以 和和 的点集的并为点集的点集的并为点集, 边集的并为边边集的并为边集集 ;假设假设 和和 没有公共边没有公共边, 那么称它们的边是不那么称它们的边是不重的重的 . 设设 和和 是是G的子图的子图, 假设假设 和和 没有公共顶点没有公共顶点, 那么那么称它们称它们是不相交的是不相交的 ;3154263154264263154两个不相交的子两个不相交的子图两个两个边不重的子不重的子图ORXJTU第五章 图与网络规划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 边数ORXJTU第五章 图与网络规划 图G = (V, E )中的一个中的一个顶点序列点序列 称称为是一条是一条 途径途径(walk)W, 假假设对i=1, , k, 有有 . 称称为W的起点的起点, 称称为W的的终点点, 称称为W的内部的内部顶点点(中中间点点) . 途径途径W的的长度定度定义为它所含的它所含的边的数的数目目,即即为k . 也可以用其相应边的序列也可以用其相应边的序列 来表示途径来表示途径W, 这里这里 .315426315264路路(1 2 3 4 2 3 5 6)ORXJTU第五章 图与网络规划 假假设在在W中的中的顶点互不一点互不一样, 那么称那么称W为一途径一途径(初等初等链, 初初级路路) (path) .315426 由由 到到 的一条路的一条路, 假设路中的边假设路中的边不不反复反复, 那么称为简单路那么称为简单路 . 简单图中的任一条路必为简单路简单图中的任一条路必为简单路, 记为记为 .假设假设 , 那么称途径那么称途径W是是闭的闭的 . 称闭途径称闭途径W为一个回路或圈为一个回路或圈(cycle), 假设假设 且且 构成一路经构成一路经 .31542631526简单路路(1 2 5 3 4 6)初初级路路(1 2 3 5 6) 长为偶数的圈称偶数的圈称为偶圈偶圈,长为奇数奇数的圈称的圈称为奇圈奇圈 .ORXJTU第五章 图与网络规划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为连通通图(connected graph), 否那么称否那么称为非非连通通图 .顶点之点之间的的连通性是一个等价关系通性是一个等价关系 .ORXJTU第五章 图与网络规划 一个一个图G, 假假设能把它画在平面上能把它画在平面上, 且除端点外恣意两条且除端点外恣意两条边均不相交均不相交, 那么称那么称G可嵌入平面可嵌入平面. 假假设图G可以嵌入平面可以嵌入平面, 那么称那么称G为可平面可平面图(planar graph) . 可平面可平面图在平面上的一个嵌入在平面上的一个嵌入称称为一个平面一个平面图(plane graph) . 设设 为为Th 5中之划分中的一个子集中之划分中的一个子集, 那么称子图那么称子图 为为G的一个连通分支或简称为分支的一个连通分支或简称为分支(component), 这里这里 表示两个端点均在表示两个端点均在 中的边的集合中的边的集合 . 显然显然, 当且仅当当且仅当G只需一个分支时只需一个分支时, G是连通图是连通图 . 假设图假设图G是是不连通的不连通的, 那么其补图那么其补图 连通连通 .ORXJTU第五章 图与网络规划二二. 有向图有向图 有向有向图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) .ORXJTU第五章 图与网络规划 起点与起点与终点重合的弧称点重合的弧称为环 . 假假设两两条条弧有一弧有一样的起点和一的起点和一样的的终点点, 那么称那么称这两两条条弧弧为重弧重弧. 既没有既没有环也没有重弧的有向也没有重弧的有向图称称为简单有向有向图. 假设假设u,v V, 那么弧那么弧a=(u,v) A是顶点是顶点u和和v的有的有序对序对. 常称常称u为弧为弧a的起点的起点(尾尾) , v为为a的终点的终点(头头). a称为称为u的出弧的出弧, 也称为也称为v的入弧的入弧. 对于有向图对于有向图D的任一顶点的任一顶点v, 以以v为起点为起点的弧的数目叫做的弧的数目叫做v的出度的出度(outdegree) , 记为记为 ;以以v为终点的弧的数目叫做为终点的弧的数目叫做v的入度的入度(indegree) , 记为记为 . 显然显然, .u vaORXJTU第五章 图与网络规划 对一个有向一个有向图D, 可以在其可以在其顶点集合上作一个点集合上作一个图G, 使得使得对应于于D的各条弧的各条弧, G有一条一有一条一样端点的端点的边, 这个无向个无向图G称称为D的根底的根底图(underlying graph) .普通普通说来来, 对应于一个根底于一个根底图可以有多个有向可以有多个有向图 .Th.7 : 设D = (V, A )是一有向是一有向图， 那那么 . 这里里 表示集合表示集合A中的元素中的元素数目目 . 顶点序列顶点序列 称为有向图称为有向图D = (V, A )中的一条中的一条 有向途经有向途经(directed walk) , 假设对假设对 有有 .假设该有向途经中的顶点互不一样假设该有向途经中的顶点互不一样, 那么称其为一条那么称其为一条 有有向路向路径径; 而假设而假设 ,且独一反复的顶点是且独一反复的顶点是 , 那么称其为一那么称其为一有向有向回路或有向圈回路或有向圈 .ORXJTU第五章 图与网络规划Th.8 : 设P是有向是有向图D的一的一个子子图, 假假设 1 . 2对恣意的恣意的 有有 . 那那么P是一是一条有向有向i-j途途径. 这里里V(P)表示表示图P的的顶点集点集 . Th.9 : 设C是有向是有向图D的一的一个子子图， 假假设 1对恣意的恣意的 ,有有 . 2对恣意的恣意的 . 那那么C是一是一条有向回路有向回路 . ORXJTU第五章 图与网络规划 给定有向定有向图D = (V, A ), 对D中的每条弧中的每条弧a赋予一个予一个实数数(a),称称为弧弧a的的权. 是是A上的一上的一实值函数函数, 称称为D的的权函数函数 . 赋权的有向的有向图D称称为网网络或或赋权有向有向图, 记为D = (V, A, ).赋以以权的的图G称称为无向网无向网络或或赋权图, 记为G = (V, E, ). 对于网于网络D = (V, A, ), 假假设 是是D的一个子的一个子图, 那么那么 称称为D的子网的子网络, 并定并定义 为子网子网络的的权 . 假设对有向图假设对有向图D的每一对顶点的每一对顶点, 均有一条有向途径衔接它们均有一条有向途径衔接它们, 那么称那么称D是强连通的是强连通的(strongly connected) .假假设D是是强连通的通的, 那么它亦是那么它亦是连通的通的 .ORXJTU第五章 图与网络规划割边割边 : 一条边称为一条边称为G的割边的割边, 假设从假设从G中删中删 去它去它, 那么使图的连通分支数严厉添那么使图的连通分支数严厉添加加 .该条条边不包含在不包含在G的任何的任何简单回路中回路中 . 132456 G=(V,E), S,T V, S T= , S,T表示一个端点在S中, 而另一个端点在T中的边集合. 边割边割 : 指指G的边集的边集E的形如的形如 的一个子集的一个子集, 其中其中S是是V的非空的非空 真子集真子集, , 且假设从且假设从G中删去这些边中删去这些边, 那么那么G的连的连通分通分 支数严厉添加支数严厉添加 .割集割集 : G的极小的极小边割割 .每条割每条割边均均为一个割集一个割集任何任何边割都是不相交割集的并割都是不相交割集的并ORXJTU第五章 图与网络规划214352143521435214352,1,2,4,2,3割集2,3,2,4,1,4,1,5割集2,3,4,3,4,51,5不是割集, 但为边割2,3,2,4,1,4既非割集,亦非边割ORXJTU第五章 图与网络规划三三. 图的表示图的表示直直观 ：图 1ORXJTU第五章 图与网络规划对于规模较大的图对于规模较大的图, 那么用一个矩阵来记录那么用一个矩阵来记录. 有以下两种方有以下两种方式式 :l顶点点 边关关联矩矩阵设G=(V, E) 是一个非空无是一个非空无环图, 定定义例如例如, 图1中所示的中所示的图G的关的关联矩矩阵为那么所得到的那么所得到的 阶矩阵阶矩阵M(G) 称为图称为图G的关联矩的关联矩阵阵 .ORXJTU第五章 图与网络规划图的关联矩阵有以下明显的性质图的关联矩阵有以下明显的性质 :1. 每一列恰好有两个非零元素每一列恰好有两个非零元素1.2. 每一行的元素之和等于每一行的元素之和等于对应顶点的度点的度.3. 将一个关将一个关联矩矩阵中的两行或两列互中的两行或两列互换, 相当于在同一个相当于在同一个图 中将两个中将两个对应的的顶点或点或边的的标号互号互换.5. n阶图G是是连通的当且通的当且仅当当G的关的关联矩矩阵是是 n-1.4. 假设假设G有有 个连通分支个连通分支 , 那么经过适当的那么经过适当的陈列陈列 G的顶点和边所对应的行和列的顶点和边所对应的行和列, G的关联矩阵可以写成块的关联矩阵可以写成块 对角方式对角方式 , 其中其中 是是 的关联矩阵的关联矩阵 .ORXJTU第五章 图与网络规划l邻接矩阵邻接矩阵例如例如, 图1中所示中所示图的的邻接矩接矩阵为 : 设图设图G=(V,E), 令令 等于等于G中顶点中顶点 与与 之间的边数之间的边数, 那么那么 阶阶方阵方阵A(G)=( )称作称作G的邻接矩阵的邻接矩阵 .显然然, 1) A是一是一对称矩称矩阵 .2) 当当图G中不存在重数大于中不存在重数大于1的的边时, A的元素只取的元素只取0和和1 两个两个值 .ORXJTU第五章 图与网络规划对于有向图对于有向图, 亦可用类似于图的方法来表示亦可用类似于图的方法来表示 . 例如例如, 图2给出了一个具有五个出了一个具有五个顶点、九条弧的有向点、九条弧的有向图D = (V, A ) .图 2ORXJTU第五章 图与网络规划同样同样, 有向图也可用关联矩阵或邻接矩阵来表示有向图也可用关联矩阵或邻接矩阵来表示.设D = (V, A )是一非空无是一非空无环有向有向图, 定定义易知易知, 图2中有向中有向图的关的关联矩矩阵为那么那么 阶矩矩阵M(D) 称称为图D的的顶点点弧关弧关联矩矩阵 .ORXJTU第五章 图与网络规划有向图的关联矩阵与图的关联矩阵有着类似的性质有向图的关联矩阵与图的关联矩阵有着类似的性质 :1. M(D)的每一列恰好有两个非零元素的每一列恰好有两个非零元素, 一个一个1和一个和一个-1.2. M(D)的每一行中的每一行中1的个数等于的个数等于对应顶点的入度点的入度, 而而-1的个数的个数 等于等于对应顶点的出度点的出度 .3. 将将M(D)的两行或两列互的两行或两列互换, 相当于在相当于在D中将两个中将两个对应的的顶 点或点或边的的标号互号互换.4. 假设假设 是是D的一切连通分支的一切连通分支, , 那么那么M(D)可以写可以写 成块对角方式成块对角方式 , 其中其中 为为 的关联矩阵的关联矩阵, . 5.2 树ORXJTU第五章 图与网络规划Def. 不含圈的图称为无圈图不含圈的图称为无圈图 , 连通的无圈图称为树连通的无圈图称为树. 称称 连通分支都是树的非连通图为森林连通分支都是树的非连通图为森林. 假假设T是是G的一个支撑子的一个支撑子图, 且且T是是树, 那么称那么称T为G的支撑的支撑树, 也称也称为生成生成树.Th. : 树的性的性质:1 ) 树的的顶点数比其点数比其边数多数多1 ;2 ) 树是无是无环图且且树的恣意两个的恣意两个顶点之点之间有独一的一条路有独一的一条路经 ;3 ) 在在树中去掉任一条中去掉任一条边, 即即变成非成非连通通图 ;4 ) 在在树中任两个不相中任两个不相邻顶点之点之间加上一条加上一条边, 那么构成一个那么构成一个恰恰 有一个圈的有一个圈的图 ;5 ) 在在树中至少存在两个度数中至少存在两个度数为1的的顶点点 .ORXJTU第五章 图与网络规划Proof: 2 ) 图G是是树 恣意两个恣意两个顶点之点之间恰有一条恰有一条链(途径途径)必要性必要性 : G连通任两个任两个顶点之点之间至少有一条至少有一条链假假设某两个某两个顶点之点之间有两条有两条链G中含有圈与与树的定的定义矛盾矛盾任两个任两个顶点之点之间恰有一条恰有一条链充分性充分性 :设图G中任两个中任两个顶点之点之间恰有一条恰有一条链G连通假假设G中含有圈中含有圈, 那么那么这个圈上任两个个圈上任两个顶点之点之间有两有两条条链与假与假设矛盾矛盾G不含圈不含圈, 于是于是G是是树 .ORXJTU第五章 图与网络规划5 ) 设图G=(V,E)是一个是一个树, p(G) 2, 那么那么G中至少有两个中至少有两个悬挂挂点点 . 令令 是是G中含边数最多的一条初等链中含边数最多的一条初等链, 且且G连通连通P中至少有一条边, 从而 与 不同 反反证法法. if , 那么存在边 ,使同理可证同理可证 也是悬挂点也是悬挂点 . 假设顶点假设顶点 不在不在P上上, 那么那么 构成构成G中另一中另一条条初等链初等链, 它含的边数比它含的边数比P多一条多一条与与P是含是含边数最多的初等数最多的初等链矛盾矛盾 假设点假设点 在在P上上, 那么那么 又构成又构成G中的一个中的一个圈圈, 这与树的定义矛盾这与树的定义矛盾ORXJTU第五章 图与网络规划Th. : G有支撑有支撑树 G是是连通通的的.Proof: 设G有支撑有支撑树TT连通G具有连通的支撑子图, 从而它必连通 .反之反之, 设G连通通G的极小连通支撑子图T的每条边也都是割边由树的性质由树的性质( T为树为树 T 连通且每条边均是割边连通且每条边均是割边 )T是G的一个支撑树ORXJTU第五章 图与网络规划 一个一个图可有多个生成可有多个生成树. 假假设给图G赋以以权, 那么称相那么称相应无无向向网网络G中中权值最小的支撑最小的支撑树为最小最小权支撑支撑树, 或或简称称为最小最小树,而称而称寻求求该树的的问题为最小最小树问题 . 同同样, 把有向把有向图D中中连通、无圈的支撑子通、无圈的支撑子图称称为D的支撑的支撑树 . 假假设图G中存在包含一切中存在包含一切边的的闭途径途径W, 那么称那么称G是是Euler图, W称称为G的的Euler闭途径途径 . 假假设有向有向图D中存在包含一切弧的有向中存在包含一切弧的有向闭途径途径W, 那么称那么称D是有向是有向Euler图, W称称为D的有向的有向Euler闭途径途径 .Def. ORXJTU第五章 图与网络规划 包含图包含图G的每个顶点的途径的每个顶点的途径, 称为称为Hamilton途径途径, 简称简称Hamilton路路; 包含包含G的一切顶点的圈的一切顶点的圈, 称为称为Hamilton圈圈(或回或回路路).假设图假设图G包含一个包含一个Hamilton圈圈, 那么称此图为那么称此图为Hamilton图图. 类似地似地, 在有向在有向图中亦可定中亦可定义Hamilton圈和圈和Hamilton路路. 存在存在Hamilton圈的有向圈的有向图称称为有向有向Hamilton图 .