图的概念课件

第六章图与网络方法

图的概念

树 最短路问题 网络最大流 最小费用流1引言--哥尼斯堡七桥问题

十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。2顶点(Vertex)表示研究对象

－－物理实体、事物，一般用vi

表示边(Edge)

表示两个对象之间的某种特定关系

－－顶点间的连线，一般用ei

表示

图(Graph)顶点和边的集合G＝（V，E）V--点集合E--边集合1、什么是图3例V={v1，v2，v3，v4}E={e1，e2，…，e7}eij4e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9阶：顶点的个数n

关联：若某顶点与某条边连接，则称它们彼此关联孤立点：与任何边没有关联的顶点多重边：某两个顶点之间多于一条边多重图：具有多重边的图环：起点和终点为一个顶点的边简单图：无多重边，无环的图相邻：两顶点之间至少存在一条边次数：与某个顶点相关联的边的数目5

无向图由顶点和边组成G=（V，E）

弧(Arc)

顶点与顶点之间有方向的连线

有向图：由点和弧组成

G=（V，A）2、有向图和无向图例V={v1，v2,…,v6}A={a1，a2,…,a9}a1a2a3a4a5v2v3v1v4v5v6a6a7a8a96无向图有向图混合图连线为弧既有边又有弧连线为边7子图设：G1=(V1，E1)，G2=(V2，E2)若：V1

V2，又E1

E2

则称G1是G2的子图3、子图e1e2e3e4e5v2v3v1G1e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9G28生成子图（支撑子图）设：G1=(V1，E1)

G2=(V2，E2)若：V1＝V2又E1

E2

则称G1是G2的生成子图9基础图(母图)子图支撑子图10

链点边交错系列，记为：圈的链简单链（圈）链（圈）中的边均不相同初等链（圈）点均不相同路

初等链回路初等圈无重复点,无重复边有重复点,无重复边4、链、路、圈和回路11路回路简单链初等链初等圈12

5、连通图若一个图G的任意两点之间至少存在一条链，则称这个图G是一个连通图，否则称作不连通图。例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。

e1e2e3e4e5v2v3v1v4v5v6e6e7e8e913K部图连通图不连通图二部图14权程度的度量，数量描述线权给图的边赋以某一数值点权给图的顶点赋以某一数值网络赋权的图（边权图、点权图、混合图）6、加权图

v1139538362v6

v5

v3

v4

v2对G中的每一条边相应的有一个数wij15图与矩阵

在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有——邻接矩阵、关联矩阵、权矩阵等。7、关联矩阵和邻接矩阵16e10e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8A=(aij)=v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12

1

01

000000000110010000000010001110000000000001001001111000000000000001

100000000000111000

1

001

10000关联矩阵

0若顶点i与边j不关联aij=1若顶点i与边j相关联17B=（bij）n

n=v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8

010010001010100001001002

0000011011100001000100100001110000201000e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8邻接矩阵bij=连接顶点vi和vj的边数18邻接矩阵示例图（1）的邻接矩阵是

图（2）的邻接矩阵是

3451342122345124319说明

当图的顶点和边（弧）的编号确定之后，关联矩阵和邻接矩阵就与图建立了确定的一一对应关系，因而可用关联矩阵或邻接矩阵来表达图。一般来说，图的邻接矩阵比关联矩阵小，因而在存贮和计算时用得较多。20二、树1、什么是树树:连通的无圈图称为树，通常用字母T表示悬挂点21树的性质如果树的顶点数≥2，则它至少有两个悬挂点243512435124351如果树的顶点个数为n，则边的个数为n-1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈22定理：（树的六个等价定义）&

T连通且无回路&无圈，且有n－1条边&连通，且有n－1条边&无圈，但增加一条边，可得到一个且仅一个圈&连通，但舍弃一条边，图便不连通&每一对顶点之间有一条且仅有一条初等链232、生成树（支撑树）定义

设图T是图G的一个生成子图,如果T是一棵树,则称树T是G的一个生成树（支撑树）24图的生成树由网络的所有节点（n个）和网络的n-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦423142314231423142314231423125生成树的变换4231网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树423142314231生成树2生成树3生成树1////26生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换273、最小生成树支撑树的权

若T=(V,E)是G的一个支撑树,E中的所有边的权（）之和称为支撑树的权,记为w(T):28

最小树（T*）

在赋权图G的所有支撑树中，必有某个支撑树，其所有边的权的和最小，称为最小树。求最小树的丢边法（破圈法）

求最小树的加边法（避圈法）

T29丢边法（破圈法）655172344v1v2v3v4v5v6思路：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。30v1v2v3v5e2e3e5e1e6e7e8v1v2e1v3e2e4e4v4v4v5e6加边法（避圈法）思路：从所有边中选出一条权最小的边，并把它纳入树中；在余下的未选边中，再选出一条最小且与已选入树中的边不构成圈的边，将其纳入树中；如此重复，直到树中含有n－1条边为止。31图G1542453134421512生成最小树T生成最