俞玉森主编,数学规划的原理和方法,1985 唐焕文,实用数学规划导论,1986 魏权龄等,数学规划与优化设计,1984 §2图与网络方法 所谓图乃是指由一组给定的点(称为顶点)及一组连接这些点的线(称为边或弧)所组成的总 体(如交通图),而图论则是研究图的理论。图论的产生可以上溯到十八世纪,但它得到重视而且逐 渐成为一门学科,则是本世纪三十年代之后的事。特别是五十年代以来,由于许多具有离散性的问 题皆可以通过图来表示,使得图论的研究越来越为人们所重视,如 兰姆赛问题( Ramsey):任意六个人在一起,若不是有三个人彼此相互认识,必然有三个人互 不认识 将此问题化为图来分析:视6个人为6个顶点,认识,用实线相连接;不认识,用虚线连接。 往证至少存在一个实三角形或虚三角形。任取一点V1,它与其他五点的连线中至少有三条同为实线 或同为虚线,不妨假设为实线,而另一端点分别为V2,V3,V4 这后三个顶点形成的三角形若是虚线的则问题已经解决,不然则至少有一条边为实线,从而又与 已知实线构成一实三角形,故问题得证。 图1 可见用图来处理问题有时很有效,并且形象直观(如哥尼斯堡七桥问题)。许多有经济意义的问 题都归结为图与网络(边上有各种数据的连通图叫做网络,数据又叫权),如 (Ⅰ)、最短路问题 在给定网络中求指定两点的最短路是图论中的一个基本问题,此问题已有有效算法 用d表示连接顶点i和j的线段长(若无则视d=+∞),现在要从点1出发,走到n,问怎样 走路程最短? 66 俞玉森主编，数学规划的原理和方法，1985 唐焕文，实用数学规划导论，1986 魏权龄等，数学规划与优化设计，1984 §2 图与网络方法 所谓图乃是指由一组给定的点（称为顶点）及一组连接这些点的线（称为边或弧）所组成的总 体（如交通图），而图论则是研究图的理论。图论的产生可以上溯到十八世纪，但它得到重视而且逐 渐成为一门学科，则是本世纪三十年代之后的事。特别是五十年代以来，由于许多具有离散性的问 题皆可以通过图来表示，使得图论的研究越来越为人们所重视，如 兰姆赛问题（Ramsey）：任意六个人在一起，若不是有三个人彼此相互认识，必然有三个人互 不认识。 将此问题化为图来分析：视 6 个人为 6 个顶点，认识，用实线相连接；不认识，用虚线连接。 往证至少存在一个实三角形或虚三角形。任取一点 V1，它与其他五点的连线中至少有三条同为实线 或同为虚线，不妨假设为实线，而另一端点分别为 V2 ，V3 ，V4 ，这后三个顶点形成的三角形若是虚线的则问题已经解决，不然则至少有一条边为实线，从而又与 已知实线构成一实三角形，故问题得证。 1 2 3 5 4 6 图 1 可见用图来处理问题有时很有效，并且形象直观（如哥尼斯堡七桥问题）。许多有经济意义的问 题都归结为图与网络（边上有各种数据的连通图叫做网络，数据又叫权），如 （I）、最短路问题。 在给定网络中求指定两点的最短路是图论中的一个基本问题，此问题已有有效算法。 用 ij d 表示连接顶点 i 和 j 的线段长（若无则视 ij d ＝＋∞），现在要从点 1 出发，走到 n，问怎样 走路程最短？