第七章 图与网络分析

第七章图与网络分析1.图的基本概念2.最小树问题3.最短路问题4.最大流问题5.最小费用最大流问题本章内容例：七桥问题ABCD问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。问题：能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。例：中国邮路问题

一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。问题：他如何走？点：路口；边：两路口之间道路，第i条道路长ei。问题：求一个圈，过每边至少一次，并使圈的长度最短。例：四色猜想

能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家；边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。有二十个顶点标以二十个城市的名字，要求游戏者找一条从某一城市出发的路线，它经过每一个城市恰好一次，并且最后回到出发点。

点：城市

边：城市之间的道路问题：游戏者怎么走才能恰好每个城市走一次，而且不重复？如图：例：

Hamilton

第一节图的基本概念点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及结果)。对称关系：桥、道路、边界；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。例：有甲、乙、丙、丁、戊五个球队，各队之间比赛情况如表：点：球队；连线：两个球队之间比赛过，如甲胜乙，用

v1v2表示。v1v2v3v4v5一、图的定义定义1：一个图，是由非空集合V(G)={vi}和V(G)中元素的有序对（或无序对）的集合E(G)={ek}

所组成的二元组（V(G)，E(G)）所构成。记为

G=（V(G)，E(G)）简记G=（V，E）其中V={vi}称为点集，vi为点。

E={ek}称为边集，ek为边（或弧）。

当V，E为有限集时，称G为有限图。否则称为无限图。无向图：由点及边构成，边[vi，vj]有向图：由点及弧构成，弧（vi，vj）

图G中点集V的顶点个数，记为p(G)，边数记为q(G),简记p，q。1.简单图与多重图

某条边两个端点相同，称这条边为环。若两点之间有多于一条的边，称这些边为多重边。无环、无多重边的图称为简单图。多重图：无环、但允许有多重边。v1e1e2e3v2v3e5e4v4二、图论中常用术语2.相邻与关联

若边e=[u，v]∈E，称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关联边。

若两条边有一个公共的端点，则称这两条边相邻接。

vivjevi，vj相邻

e

与vi，vj关联vie1vjvke2

点与边关联点与点相邻边与边相邻接定理1图G=（V，E）中，所有点的次之和为边数的两倍，即3.奇点与偶点次为奇数的点称为奇点，否则称为偶点。定理2任一图中奇点的个数为偶数。证明：设v0和ve分别是G中的奇点和偶点的集合，由定理1，有因

是偶数，也是偶数，故必为偶数。即在一个图中奇点的个数必为偶数。4.次与悬挂点、孤立点图G中以点v为端点的边的数目，称为v在G中的次，记为d（v）。d(v1)=2d(v2)=3d(v3)=4d(v4)=1

次为1的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。v1e1e2e3v2v3e5e4v45.链与圈

给定一个图G=（V，E），G中的一个点、边交错序列（vi1，ei1，vi2，ei2，…，vik-1，eik-1，vik），如果满足eit=[vit，vit+1]（t=1，2，…，k-1），则称为一条联接vi1和vik的链，记为=（vi1，vi2，…，vik）。

链（vi1，vi2，…，vik）中，若vi1=vik

，称之为一个圈，记为C=（vi1，vi2，…，vik-1，vi1

）。初等链：链中点都不同。简单链：链中边都不同。（边能否相同？）（点能否相同？）v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链：2=（v2，v1，v3，v5）简单圈：C1=（v1，v2，v4，v3，v5，v6，v3，v1）初等圈：C2=（v1，v2，v4，v6，v5，v3，v1）

有向图中，不考虑弧的方向，有类似链（圈）的定义。当链（圈）上弧的方向一致时，称为路（回路）。3.连通图

给定图G=（V，E），任何两点间至少有一条链，则称G是连通图，否则为不连通图。

若G是不连通的，它的每个连通部分称为G的连通分图。三、一些特殊图类

1.平凡图节点数n=1,边数m=0的图。2.零图边数m=0的图。5.完备图无向图的完备图：任何两点之间有一条边；有向图的完备图：任何两点u与v之间有两条有向边（u，v）及（v，u）。基本图：把有向图的每条边除去方向得到的无向图。

若V(G)=X∪Y,X∩Y=Ф，X、Y中的任两顶点不相邻，则G称为二分图，记为（S,X,Y）。4.树无圈连通图。6.二分图9.网络

若对图G=（V，E）中每条边[vi，vj]赋予一个数wij，则称wij为边[vi，vj]的权，并称图G为网络（或赋权图）。网络：无向网络、有向网络。7.完全二分图

若V(G)=(S,X,Y),如果任意μ∈X、ν∈Y、，都有[μ，ν]∈E，则称G是完全的二分图。8.正则图

如果G中每个点的次数都相同，则G叫做正则图。1.子图与支撑子图定义2给定图G=（V，E），若图G1=（V1，E1），其中V1V，E1={uv|uv∈E，u，v∈v’}，则称G1是G的子图。定义3给定图G=（V，E），若图G1=（V，E1），其中E1E，则称G1是G的一个支撑子图。点全部保留（a）（b）子图（c）支撑子图四、图的运算2.图的收缩运算

设图G=(V,E)，V1V,在G中收缩V1是指在图G中，在V1中的点重为一个点，G与V1中的点相关联的边变为与这个新点相关联的边，称这样的图为关于V1收缩，记为GoV1。3.割集

给定图G=（V，E），点的子集S

V，T

V，定义G中边的集合[S，T]G={uv|u∈s，v∈T}为一个割集。若X={v1}若X∈V是V的真子集，常记为v6v2v3v4v5v1v1v2v3v4v5v6若X={v1，v2}，4.图的同构定义4设图G=（V，E）与G1=（V1，E1），若它们的点之间存在一一对应，并且保持同样的相邻关系，则称G与G1同构。记为G≌G1。v1v2v3v4abcdv1v2v3v4abcd?(a)(b)图(a)和(b)就为同构五、图的矩阵表示

图的矩阵表示方法有：邻接矩阵、关联矩阵、可达矩阵、权矩阵等。1.邻接矩阵

邻接矩阵用于描述两个顶点之间是否有边（弧）相连。对于有n个顶点的无向图G=(V,E)，定义邻接矩阵(B=bij)n×n

。其中，对于有几个顶点的有向图G=(V,A)

，定义邻接矩阵(B=bij)n×n

。其中，例题1已知无向图所示，求其邻接矩阵。v5v3v1v2v4v6则显然，无向图的邻接矩阵是关于对角线的对称矩阵。

例

2已知：图所示，求其邻接矩阵。v2v5v3v1v4v6则：v1v2v3v4v5v6v1011000v2001110v3000100v4000011v5001001v6000000其邻接矩阵为：

v4v5v2v1v3当G为无向图时，邻接矩阵为对称矩阵。在有向图中可达矩阵用于描述两点之间是否有路相连,即R=(rij)n×n

,其中，2.可达矩阵

例题3求例题2的可达矩阵则v1v2v3v4v5v6v1111111v2011111v3001111v4000111v5000011v60000013.关联矩阵有向图的关联矩阵也称顶点—边关联矩阵。设有向图

G=(V,A)，其中rij=V=｛v1,v2,v3…vn｝，

，则关联矩阵可定义为

M=(mij)n×m其中：例题4求下图的关联矩阵v4v2v1v3