若G含圈，则任取G的一个圈，从该圈中任意去掉一 条边，得到图G的一生成子图G1。若G1不含圈，则G1是G 的一个生成树。 若G1仍然含圈，则任取G1的一个圈，再从圈中任意 去掉一条边，得到图G的一生成子图G2。依此类推，可以 得到图G的一个生成子图GK，且不含圈，从而GK是一个 生成树。
第二节
图的生成树的求法1：
等问题，都可以应用图论的方法，简便、快捷地加以
解决。
一、图与网络的基本知识
第八章
在实际的生产和生活中，人们为了反映事物之间的关系， 常常在纸上用点和线来画出各式各样的示意图。
例1:图8.2是我国北京、上海、重庆等十四个城市之间 的铁路交通图，这里用点表示城市，用点与点之间的线表示 城市之间的铁路线。
称矩阵A为网络G的权矩阵。
一、图与网络的基本知识
第八章
用矩阵表示图对研究图的性质及应用常常是比较方
便的．图的矩阵表示方法有权矩阵、邻接矩阵、关联矩
阵、回路矩阵、割集矩阵等，这里只介绍其中两种常用 矩阵。 定义12 对于图G＝(V，E)，|V|=n，构造一个矩阵A ＝(aij)n╳n，其中
1 (vi , v j ) E aij 0 other
（三）图的矩阵表示
第八章
用矩阵表示图对研究图的性质及应用常常是比较方
便的．图的矩阵表示方法有权矩阵、邻接矩阵、关联矩
阵、回路矩阵、割集矩阵。
定义11 网络(赋权图)G＝(V，E)，其边(vi，vj)有权 wij,构造矩阵A＝(aij)n╳n，其中
(vi , v j ) E wij aij 0 other
第八章 图与网络分析
一、图与网络的基本知识
二、树 三、最短路问题
四、最大流问题
引
言
第八章
图论是应用非常广泛的运筹学分支，它已经广泛
地应用于物理学控制论，信息论，工程技术，交通运
输，经济管理，电子计算机等各项领域。对于科学研 究，市场和社会生活中的许多问题，可以同图论的理 论和方法来加以解决。例如，各种通信线路的架设， 输油管道的铺设，铁路或者公路交通网络的合理布局
一、图与网络的基本知识
3、子图
第八章
定义7
图G＝(V，E)，若E’是E的子集，V’是V的子集，
且E’中的边仅与V’中的顶点相关联，则称G’＝(V’，E’)是 G的一个子图。特别地，若V’＝V，则G’称为G的生成子图
(支撑子图)。
4、网络 点或边带有某种数量指标的图称为网络(赋权图)。 网络分为有向网络和无向网络。
一、图与网络的基本知识
第八章
定义2 一个无环，无多重边的图称为简单图，含有 多重边的图称为多重图。如不特别说明，都是简单图。
定义3 每一对顶点间都有边相连的无向简单图称为
完全图。有n个顶点的无向完全图记作Kn。 有向完全图则是指每一对顶点间有且仅有一条有向边 的简单图。 定义4 图G＝(V，E)的点集V可以分为两个非空子集 X，Y，即X∪Y＝V，X ∩Y＝ Ø ，使得E中每条边的两 个端点必有一个端点属于X，另一个端点属于Y．则称G 为二部图(偶图)，有时记作G＝(X，Y，E)。
一、图与网络的基本知识
例如.图8.4是一个无向图G=（V，E） 其中V={v1,v2,v3,v4} E={[v1,v2],[v2,v1],[v2,v3], [v3,v4],[v1,v4],[v2,v4], [v3,v3]} v1 v2
第八章
图8.4 v4 v3
一、图与网络的基本知识
第八章
图8.5是一个有向图D=（V，A） 其中V={v1,v2,v3,v4,v5,v6,v7} A={(v1,v2),(v1,v3),(v3,v2), (v3,v4),(v2,v4),(v4,v5), (v4,v6),(v5,v3),(v5,v4), (v5,v6),(v6,v7)}
图论中的图是由点和点与点之间的线所组成的。通
常，我们把点与点之间不带箭头的线叫做边（无向边）， 带箭头的线叫做弧（有向边）。
一、图与网络的基本知识
第八章
如果一个图是由点和边所构成的，那么，称为为无向 图，记作 G =(V，E)，其中 V 表示图 G 的点集合，E表示图G 的边集合。连接点 vi,vjV 的边记作[vi,vj]，或者[vj,vi]。 如果一个图是由点和弧所构成的，那么称为它为有向 图，记作D =(V,A)，其中V 表示有向图D的点集合，A表示 有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。 两个点u，v属于V，如果边(u，v)属于E，则称u,v两点 相邻。u,v称为边(u,v)的端点。 两条边ei,ej属于E，如果它们有一个公共端点u，则称 ei,ej相邻。边ei,ej称为点u的关联边。
A
B C D E
F G H
第二节
定义14
树
第八章
连通且不含圈的无向图称为树。
树中次为1的点称为树叶，次大于1的点称为分枝点。 树的性质可用以下定理表示： 定理6 图T=(V,E)，|V|=n,|E|=m,则下列关于树的说法是等 价的：
1 T是一个树。
2 T无圈，且m=n-1。 3 T连通，且m=n-1。 4 T无圈，但每加一新边即得惟一一个圈。 5 T连通，但任舍去一边就不连通了。 6 T中任意两点，有惟一链相连。 图8-9
第二节
树
第八章
一、树及其性质 在各种各样的图中，有一类图是十分简单又非常具有应用 价值的图，这就是树。树在自然科学和社会科学,特别是在计 算机科学领域中有广泛的应用。 例8.3：已知有六个城市，它们之间要架设电话线，要求 任意两个城市均可以互相通话，并且电话线的总长度最短。 v2 v1 六个城市的一个电话网就作成一个图。
v3
v1 v2
v5
v7
v6
v4
图8.5
一、图与网络的基本知识
常用的名词：
第八章
一个图G或有向图D中的点数,记作P(G)或P(D),简记作
P,边数或者弧数,记作q(G)或者q(D),简记作q。
如果边[vi,vj]E,那么称vi,vj 是边的端点，或者vi,vj 是相
邻的。如果一个图G中，一条边的两个端点是相同的,那么 称为这条边是环，如图8.4中的边[v3,v3]是环。如果两个端 点之间有两条以上的边，那么称为它们为多重边。
一、图与网络的基本知识
第八章
定理8.1 任何图中，顶点次数的总和等于边数的2倍。
定理8.2 任何图中，次为奇数的顶点必为偶数个。
vV1
d (v) d (v) d (v) 2m
vV2 vV
定义6
有向图中，以vi为始点的边数称为点vi的
出次，用d+(vi)表示，以vi为终点的边数称为点vi的入次， 用d-(vi)表示。vi点的出次与入次之和就是该点的次。容 易证明有向图中，所有顶点的入次之和等于所有顶点的 出次之和。
一、图与网络的基本知识
中国邮路问题也可以转为如下问题：
第八章
在连通图G＝(V，E)中，求一个边集E1∈E，把G中属
于E1的边均变为二重边得到图G*＝G+E1，使其满足G* 无奇点，且L（E1）=∑l(e)最小。 定理5 己知图G*＝G+E1无奇点，则L（E1）=∑l(e)的 最小的充分必要条件为: (1)每条边最多重复一次； (2)对图G中每个初等圈来讲，重复边的长度和不超过 圈长的一半。
树
第八章
定理7充分性的证明，提供了一个寻找连通图生成树的方
法,叫做“破圈法”。就是从图中任取一个圈，去掉一条边。 再对剩下的图重复以上步骤，直到不含圈时为止，这样就得 到一个生成树。 例8.4:用破圈法求出图8-11的一个生成树。 V2 e7 e1 e4 e3 V1 V4 V5 e8 e5 e2 e6 V3 图8-11
一、图与网络的基本知识
（二）连通图
第八章
定义8 链：由两两相邻的点及其相关联的边构成的点 边序列;如: v0 ,e1 ,v1 ,e2 ,v2 ，e3 ,v3 ,…,vn-1, en , vn ;
v0 ，vn分别为链的起点和终点；
初等链：链中没有重复点和重复边者称为初等链； 有向图中，链上的边方向相同时称为道路；
v2 v4
v1
v6
v3
v5
图8.2
一、图与网络的基本知识
第八章
从以上的几个例子可以看出，我们用点和点之间
的线所构成的图，反映实际生产和生活中的某些特定
对象之间的特定关系。一般来说，通常用点表示研究 对象，用点与点之间的线表示研究对象之间的特定关 系。由于在一般情况下，图中的相对位置如何，点与 点之间线的长短曲直，对于反映研究对象之间的关系，
第二节
树
第八章
二、图的生成（支撑）树 定义15 设图K=(V,E’)是图G=(V,E)的一生成（支撑）子 图,如果图K=(V,E’)是一个树,那么称K是G的一个生成树。 G中属于生成树的边称为树枝，不在生成树上的边称为弦。 例如,图8.10b 是图8.10a 的一个生成树。 v5 v3 v5 v3 v1 v6 v2 v2 a v4 b v4 v1
太原 石家庄 北京 天津 塘沽
济南
青岛
郑州
重庆 武汉 图8.1 南京
徐州
连云港 上海
一、图与网络的基本知识
第八章
例2:有六支球队进行足球比赛，我们分别用点v1…v6表示 这六支球队。它们之间的比赛情况，也可以用图反映出来，已 知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这 个胜负情况，可以用图8.3所示的有向图反映出来。
这个图必须是连通图。
v3 v4
v5 v6 图8-8
这个图必须是无圈的。
图8.8是一个不含圈的连通图，代表 了一个电话线网。
第二节
树
第八章
再比如，乒乓球单打比赛抽签后的对阵形式以及企业的 组织结构图等。