图与网络西安电子科技大学经济管理学院.pptx

运筹学;第十章?????? 图与网络;主要内容：;主要内容：;§ 10.1 基本概念 ;若N和E均为有限集合，则称为G为有限图，否则称无限图。 若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。 若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。 ;def 2：一个有向图G是一个有序的二元组，记为G=(V, A)，其中V=(V1V2…Vn)称为G的点集合，A={aij}称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。 |V|=n表示G中节点个数为n，此节点个数n也称为图G的阶 |A|=m表示有向图G中弧的个数为m 任一顶点相关联（连接）的边的数目称为该顶点的次数;2 连通图 def 3：在有向图G中,一个点和边的交替序列{Vi eij Vj…Vk ekl Vl} 称为G中从点Vi到Vl的一条路，记为A，其中Vi为此路A的起点，Vj为路A的终点；若路A的起点与终点重合,则称A为回路；又若G中点Vi与Vj间存在一条路，则称点Vi与Vj是连通的；若G中任何二点都是连通的，则称G为连通图，或图G为连通的。在无向图中有对应的概念。 ;;例：下示图G1是图G的子图，图G2是图G的生成子图。;4 赋权图（加权图）与网路 def 5：设G是一个图（或有向图），若对G的每一条边（或弧）eij都赋予一实数ωij，称其为该边（弧）的权，则G连同其他弧上的权集合称为一个赋权图，记作G= (V, E, W) 或G= (V, A, W)，此中W={ωij}，ωij为对应边（弧）eij的权。若G= (V, E, W) （或(V, A, W)）为赋权图，且在G的V中指定一个发点（常记为Vs）和一个收点（记为Vt），其余点称为中间点，则称这样指定了发点与收点的赋权图G为网络。 ;; 最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用。 ;（一）Bellman最优化原理;证明（反证）： 若P1不是从Vs到Vl的最小路，则存在另一条 Vs 到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2) + W(P3)W(P1) + W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更小的一条路，这与P使G中从Vs到Vt的一条最小路矛盾。 ;2 算法思想： 设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 ;⑵ 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=φ），此时 迭代结束。I称为已标号集合,J称为未标号集合。 ;⑶ 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 ⑷ 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，此中 |V|=n ; ⑸ 以下介绍的是适用于弧权为正值的有向网络中求最短有向路的Dijkstra算法，又称双括号法。事实上该算法亦适用于弧权为负值的有向网络求最短路问题。 ;由图G建立一步可达距离阵D=(dij)n×n;;;例2 求如下G之最小路;;; 由表三知 V1 V8 最短路P1：V8 V6 V2 V1 最短路P2：V8 V6 V5 V3 V2 V1 最短路长 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13 ;;;; ① 由表四可得 最短路P： V7 V6 V5 V3 V1 最短距离 |P|=10+4+2+6=22 ② 还可得到自V1（甲）到任一中间点之最短路，例如 V1 V4 最短路由表四可知为 P14