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

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

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