1、第八章 网络模型和 Petri网讨论两个主题：网络模型和 Petri网。8.1 网络模型输油管道网络：z ab cd e(码头 ) (炼油厂 )2223 445边上的 标号指出子管道的容量。问题是：求出从码头 a到炼油厂 z的最大流量并计算该最大流量值。图 8.1.1 传输网络Def 8.1.1一个传输网络 (更简单地、称为网络 )是一个满足下列条件的简单、加权、有向图：(1) 一个没有进入边的确定顶点，称作源。(2) 一个没有离开边的确定顶点，称作汇。(3) 有向边 (i,j)的权 Cij是 一个非负数，称为有向边 (i,j)的容量。ex8.1.1图 8.1.1是一个传输网络。源是顶点 a,
2、 汇是顶点 z。 边 (a,b)的容量 Cab=3， 边 (b,c)的容量 Cbc=2, 。注意：本章中，若 G是一个网络，则用 a表示源，用 z表示汇。Def 8.1.2设 G是一个传输网络。令 Cij表示有向边 (i,j)的容量。 G的一个流量 F赋于每个有向边 (i, j)一个非负数 Fij， 使得(1) Fij Cij(2) 对于既不是源也不是汇的每个顶点 j:(8.1.1)(总假定对所有顶点 i求和。若 (i, j)不是边，则设 Fij=0)。称 Fij为在边 (i, j)中的流量。对 任何顶点 j ， 称 为流入 j的流量，称 为流出 j的流量。由 Def 8.1.2可知：一个网络
3、的流量就是对每个有向边赋流量值，该值不超过所在边的容量值。对于既不是源也不是汇的顶点 V， 假定流入 V的流量等于流出 V的流量。ex8.1.2对图 8.1.1中的每条有向边赋值：Fab=2, Fbc=2, Fcz=3, Fad=3Fdc=1, Fde=2, Fez=2z ab cd e2, 22, 12, 23, 2 4, 34, 25, 3于是对图 8.1.1这个传输网络定义了一个流量。图 8.1.2 网络流量注意： 1. 若边 e的容量是 x且边 e的流量是 y，则边 e被标以 “x, y”。2. 流出源 a的流量：Fab+Fad=2+3=5流入汇 z的流量：Fcz+Fez=3+2=5可见：流出源 a的流量 =流入汇 z的流量。Th 8.1.1给定网络一个流量，流出源的流量等于流入汇的流量，就是：(对所有顶点 i求和，若 (i,j)不是边，则设 Fij=0)
