第9章 图与网络模型
图论起源于18世纪，1736年瑞士数学家欧拉发表了第一篇图论文章“哥尼斯堡的七座桥”.近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中.
图论中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段表示两个事物的特定的联系，就得到了描述这个“图”的几何形象.图与网络是运筹学中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域.下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题.
图论问题有一个特点：它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络.与图和网络相关的最优化问题就是网络最优化或称网络优化问题.由于多数网络优化问题是以网络上的流为研究的对象，因此网络优化又常常被称为网络流或网络流规划等.
下面首先简要介绍图与网络的一些基本概念.
一个无向图G是由一个非空有限集合V（G）和V（G）中某些元素的无序对集合E（G）构成的二元组，记为G=（V（G），E（G））.其中V（G）={v1，v2，…，vn}称为图G的顶点集或节点集，V（G）中的每一个元素vi（i=1，2，…，n）称为该图的一个顶点或节点；E（G）={e1，e2，…，em}称为图G的边集，E（G）中的每一个元素ek（即V（G）中某两个元素vi，vj的无序对）记为ek=（vi，vj），被称为该图的一条从vi到vj的边.
当边ek=（vi，vj）时，称vi，vj为边ek的端点，并称vj与vi相邻；边ek称为与顶点vi，vj关联.如果某两条边至少有一个公共端点，则称这两条边在图G中相邻.边上赋权的无向图称为赋权无向图或无向网络.图G的顶点数用符号|V|表示，边数用|E|表示.端点重合为一点的边称为环.一个图称为简单图，如果它既没有环也没有两条边连接同一对顶点.
一个有向图G是由一个非空有限集合V和V中某些元素的有序对集合A构成的二元组，记为G=（V，A）.其中V={v1，v2，…，vn}称为图的顶点集，V中的每一个元素vi称为该图的一个顶点；A={a1，a2，…，am}称为图的弧集.
也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0.在邻接矩阵的所有n2个元素中，只有m个为非零元.图9-1的网络中邻接矩阵如下所示.
同样，对于网络中的权，也可以用类似邻接矩阵的n×n矩阵表示.只是此时一条弧所对应的元素不再是1，而是相应的权而已.如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
