《現(xiàn)代物流運籌學（第二版）》 課件 12.圖的基本概念

圖的基本概念《現(xiàn)代物流運籌學》主講教師：王東輝圖的基本概念近代圖論的歷史可追溯到18世紀的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。K?nigsberg橋對應的圖圖的基本概念在一個人群中，對相互認識這個關系我們可以用圖來表示。例(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。圖的有關概念表示為：G=（V，E）V--點集合E--邊集合簡稱圖，由點和邊組成。無向圖：帶箭頭的聯(lián)線，表示不對稱關系。不帶箭頭的聯(lián)線，表示對稱關系。?。悍从硨ο笾g關系的一種工具。圖：表示兩個對象之間的某種特定關系。連線：表示研究對象。點：有向圖：由點和弧組成。邊：無向圖的有關概念有多重邊的圖。多重圖：無環(huán)，無多重邊的圖。簡單圖：兩點之間多于一條邊。多重邊：若u=v，e是環(huán)。環(huán)：e是點u，v的關聯(lián)邊。關聯(lián)邊：e=[u,v]∈E，則u,v是e的端點，稱u,v相鄰。端點：無向圖的有關概念V1v2v3v4e1e2e5e4e6e3次為偶數(shù)的點。偶點：次為奇數(shù)的點。奇點：次為0的點。孤立點：懸掛點的關聯(lián)邊。懸掛邊：次為1的點。懸掛點：例:如圖示d(v1)=4，d(v4)=4以點v為端點的邊數(shù)稱為v的次。表示為：d(v)次：無向圖的有關概念圈中邊均不相同。簡單圈：鏈中邊均不相同。簡單鏈：圈中無重復的點和邊。

初等圈：鏈中無重復的點和邊。初等鏈：如一條鏈中起點和終點重合。圈：點邊交錯序列。鏈：無向圖的有關概念圖G去掉點v及v的關聯(lián)邊的圖。G-v：對G=（V，E），若Gˊ=(Vˊ，Eˊ),使Vˊ=V，Eˊ是E的子集，則Gˊ是G的一個支撐子圖。支撐子圖：對不連通圖，每一連通的部分稱為一個連通分圖。連通分圖：任意兩點之間至少有一條鏈。連通圖：有向圖的有關概念有多重弧。多重有向圖：無自環(huán)，無多重弧。簡單有向圖：圈中無重復的點和弧。初等圈（回路）：鏈中無重復的點和弧。初等鏈（道路）：如一條鏈中起點和終點重合。圈（回路）：點弧交錯序列。鏈（道路）：對弧a=(u，v)，u為a的始點，v為a的終點。始點和終點：由點和弧組成。表示為：D=（V，A）V--點集合A--弧集合有向圖：圖的基本概念與模型子圖，部分圖(支撐子圖)v3e7e4e8e5e6e1e2e3v1v2v4v5（G圖）圖G1={V1、E1}和圖G2={V2，E2}如果有稱G1是G2的一個子圖。若有，則稱G1是G2的一個部分圖(支撐子圖)。v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)圖的基本概念與模型網(wǎng)絡（賦權圖）設圖G＝（V，E），對G的每一條邊(vi,vj)相應賦予數(shù)量指標wij，wij稱為邊(vi,vj)的權，賦予權的圖G稱為網(wǎng)絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。