第一节图的基本概念 V2 7 V4 2 V1 5 3 2 V6 4 6 V3 1 V5 图8-9赋权图 赋权图的应用是很广泛的，例如在一张交通 路线图中，边的权数可以是两点之间的距离，也 可以是两地的单位货物的运费，还可以该路线的 最大运能等等。 28
28 第一节 图的基本概念 赋权图的应用是很广泛的，例如在一张交通 路线图中，边的权数可以是两点之间的距离，也 可以是两地的单位货物的运费，还可以该路线的 最大运能等等。 图8-9 赋权图
第一节图的基本慨念 在一个工程网络图中，可以表示工序的完成 时间。在一个设备维修图中，权数可表示维修所 需的费用等。在本章讨论的各种图中，绝大多数 均为赋权图 假设在赋权图中有一条通路，则通路上所有 的边的权数之和称为这条通路的权 对于一个有向图，类似地也可以定义它的权 数，从而使它成为一个赋权图 29
29 第一节 图的基本概念 在一个工程网络图中，可以表示工序的完成 时间。在一个设备维修图中，权数可表示维修所 需的费用等。在本章讨论的各种图中，绝大多数 均为赋权图。 假设在赋权图中有一条通路，则通路上所有 的边的权数之和称为这条通路的权。 对于一个有向图，类似地也可以定义它的权 数，从而使它成为一个赋权图
第一节图的基本慨念 一个连通图连同定义在其边集上的实函数 V(c)一起称为一个网络。 若一个网络的每条边均是有方向的，则称该 网络为有向网络；若每一条边均无方向，称为无 向网络；若其中有些边有方向，有些边没有方向， 则称为混合网络。本章讨论的各种算法既适用于 无向网络，也适用于有向网络或混合网络。 30
30 第一节 图的基本概念 一个连通图连同定义在其边集上的实函数 W(c)一起称为一个网络。 若一个网络的每条边均是有方向的，则称该 网络为有向网络；若每一条边均无方向，称为无 向网络；若其中有些边有方向，有些边没有方向， 则称为混合网络。本章讨论的各种算法既适用于 无向网络，也适用于有向网络或混合网络
第一节图的基本慨念 四、图的矩阵表示 图形虽然有直观、简洁等优点，但随着实际 问题的大型化，大多数算法均要在计算机上运算 和求解，而要计算机能直接处理这类图形，显然 是十分困难的，下面将要介绍图的矩阵表示，其 目的是将图转化为代数矩阵，从而可以利用计算 机对图形进行处理与运算： 1.无权图的矩阵表示 对于无权图8-10，我们可以用矩阵表示。 31
31 第一节 图的基本概念 四、图的矩阵表示 图形虽然有直观、简洁等优点，但随着实际 问题的大型化，大多数算法均要在计算机上运算 和求解，而要计算机能直接处理这类图形，显然 是十分困难的，下面将要介绍图的矩阵表示，其 目的是将图转化为代数矩阵，从而可以利用计算 机对图形进行处理与运算。 1．无权图的矩阵表示 对于无权图8-10，我们可以用矩阵表示
第一节图的基本概念 v2 4 3 v5 图8-10无权图 在图8-10中两顶点之间有边相连的记为“1” 无边相连的记为“0”。点与自身之间没有边（简 单图)，对角线上的数字记为“0”。这样，对于 图8-10就可以得到下面的对称矩阵： 32
32 第一节 图的基本概念 在图8-10中两顶点之间有边相连的记为“1” ， 无边相连的记为“0” 。点与自身之间没有边（简 单图），对角线上的数字记为“0” 。这样，对于 图8-10就可以得到下面的对称矩阵： 图8-10 无权图