【正文】 次為偶數(shù)的點稱作 偶點 。 ? 邊數(shù) 集合 E中元素的個數(shù)，記作 q(G)。由定理1有 qddVV2)()(21?? ???? ????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 鏈 ? 由兩兩相鄰的點及其相關聯(lián)的邊構成的點邊序列稱為 鏈 。 ? 若 V1?V2 ， ? E1={ [u,v] | u∈ V1, v∈ V1}，則稱 G1是 G2中 由 V1導出的 導出子圖 。 網(wǎng)絡概念 ? 圖只能用來研究事物之間有沒有某種關系 ， 而不能研究這種關系的強弱程度 。權數(shù)表示兩地間公路的長度（單位：公里）。為省去弧的方向，如下圖 : (a)和 (b)、 (c)和 (d)的意義相同。 (6,6) (3,4) (5,7) (2,5) (2,4) （ 2,3） (4,4) (1,3) (2,8) （ 3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) 二、最小費用最大流的網(wǎng)絡圖論解法 對網(wǎng)絡上?。?vi,vj）的（ cij,bij）的表示作如下改動，用 (b)來表示 (a)。 最終得到下圖，可知， v1到 v6的距離是 53，最短路徑有兩條： v1 v3v6和 v1v4v6 v1 v2 v3 v4 v5 v6 16 22 30 41 59 16 22 30 41 31 23 17 18 17 23 V1 （ 0,s） v3 v4 (41,1) v5 v6 22 30 41 59 16 (22,1) 30 41 31 23 17 18 17 23 V2 （ 16,1） 16 (30,1) (53,3) (53,4) 網(wǎng)絡最大流問題 ? 所謂最大流問題就是在一定的條件下 ， 要求流過網(wǎng)絡的物流 、 能量流或信息流等流量為最大的問題 ， 在最大流問題中一般有如下規(guī)定： 1) 網(wǎng)絡有一個起點 υs和一個終點 υt 2) 網(wǎng)絡是有向網(wǎng)絡 ， 即流有方向性 。 4. 對上述弧的集合中的每一條弧，計算 sij=li+cij 。 3. 連通 ， q=p1。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 子圖 ? 子圖的定義 設， G1=(V1,E1), G2=(V2,E2)，如果 V1?V2 ，又 E1?E2 ，則稱 G1是 G2的 子圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 定理 ? 若圖 G中所有點都是孤立點，則稱圖 G為 空圖 。第十一章 圖與網(wǎng)絡規(guī)劃 Graph Theory and Network Analysis 圖與網(wǎng)絡的基本概念 最短路問題 網(wǎng)絡最大流問題 最小費用最大流問題 內(nèi)容簡介 ? 是近幾十年來運籌學領域中發(fā)展迅速、而且十分活躍的一個分支． ? 對實際問題的描述具有直觀性 ? 廣泛應用于物理學、化學、信息論、控制論、計算機科學、社會科學以及現(xiàn)代經(jīng)濟管理科學等許多科學領域． ? 圖與網(wǎng)絡分析的內(nèi)容十分豐富．本章只介紹圖與網(wǎng)絡的基本概念以及圖論在路徑問題、網(wǎng)絡流問題等領域中的應用．重點講明方法的物理概念、基本原理及計算步驟． 圖與網(wǎng)絡的基本概念 ? 圖的理論研究已有 200多年的歷史了．早期圖論與“數(shù)學游戲”有著密切關系．所謂“哥尼斯堡七橋”問題就是其中之一． 200多年前的東普魯士有一座哥尼斯堡城，城中有一條河叫普雷格爾河，河中有兩個島嶼共建七座橋．平時城中居民大都喜歡來這里散步，并提出這樣一個問題：一個散步者能否經(jīng)過每座橋恰恰一次再回到原出發(fā)點． 圖與網(wǎng)絡的基本概念 ? 當時有許多人都探討了這個問題，但不得其解． ? 著名數(shù)學家歐拉（ Euler）將這個問題簡化為一個如右圖所示圖形．圖 4個點 A、 B、 C、 D表示兩岸和小島．兩兩點間連線表示橋． 圖與網(wǎng)絡的基本概念 ? 于是問題轉(zhuǎn)化為一筆畫問題，即能否從某一點開始一筆畫出這個圖形，不許重復，最后回到原出發(fā)點． ? 歐拉否定了這種可能性． ? 原因是圖中與每一個點相關聯(lián)的線都是奇數(shù)條． ? 為此他寫下了被公認為世界第一篇有關圖論方面的論文（ 1736年） 圖與網(wǎng)絡的基本概念 ? 1859年哈密爾頓提出了另一種游戲：在一個實心的 12面體（見圖）的20個頂點上標以世界上著名的城市名稱，要求游戲者從某一城市出發(fā)，遍歷各城市恰恰一次而返回原地，這就是所謂“繞行世界問題”． 圖與網(wǎng)絡的基本概念 ? 作圖，此問題變成在從某一點出發(fā)尋找一條路徑，過所有 20個點僅僅一次，再回到出發(fā)點． ? 解決這個問題可以按序號1—2—3—4一 … 一 20—1所形成的一個閉合路徑，并稱此路徑為哈密爾頓圈． ? 具有哈密爾頓圈的圖稱為哈密爾頓圖． 圖與網(wǎng)絡的基本概念 ? 由此可見，圖論中所研