半直覺模糊圖的路徑研究

魚先鋒 邢 雪 李 超

(商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院 商洛 726000)

半直覺模糊圖的路徑研究

魚先鋒 邢 雪 李 超

(商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院 商洛 726000)

將對象視為頂點,用直覺模糊數(shù)刻畫對象間的相關(guān)性和不相關(guān)性,作為直覺模糊邊,建立了半直覺模糊圖模型。給出了半直覺模糊圖的路徑、序關(guān)系等概念。定義了半直覺模糊圖路徑的限制可達度和整體可達度,用以刻畫路徑的擁塞情況。引入半直覺模糊圖最強可達路徑的概念。給出了求最強可達路徑的算法,用以計算擁塞狀況為主要限制因素下的最優(yōu)路徑。證明了算法的合理性并分析了算法的復(fù)雜度。給出了求最強可達路徑的一個實例,結(jié)果顯示求最強可達路徑的算法合理高效且自動化程度高。

半直覺模糊圖; 路徑可達度; 最強可達路徑

Class Number TP301.6

1 引言

最優(yōu)路徑是圖論中最具現(xiàn)實意義的研究熱點問題之一[1～3]。經(jīng)典圖論只能用以刻畫對象間的確定關(guān)系;而現(xiàn)實世界中對象間很多關(guān)系都是不確定的。模糊集[4]和直覺模糊集[5]可以客觀自然地表示對象間不確定的隸屬關(guān)系,已經(jīng)廣泛應(yīng)用于用于模糊控制、模糊識別、模糊決策等領(lǐng)域。1975年Rosenfeld將經(jīng)典圖論推廣到模糊圖論[6]。Rosenfeld在文獻[6]中給出了模糊集之間的模糊關(guān)系,得到了一些與歐拉圖論中相對應(yīng)的結(jié)論;接著Bhattacharya給出了模糊圖的一些注記[7];Bhutani介紹了模糊圖之間的同構(gòu)及弱同構(gòu)[8];Mordeson與Peng[11]介紹了模糊圖的笛卡爾積、合成、并與聯(lián)等運算;Mordesor給出了模糊圖的補運算[10],后來Sunitha與Vijayakumarl對其做了更深入的研究[11];Bhutani與Rosenfeld引進了M-強模糊子圖的概念并研究了一些性質(zhì)[12];文獻[13]中研究了模糊圖的強弧;Nagoorgani與Malarvizhi研究了模糊圖的同構(gòu)性質(zhì)并定義了自補模糊圖[14～15]。模糊圖論的應(yīng)用領(lǐng)域也極為廣泛,比如聚類分析、系統(tǒng)分析、數(shù)據(jù)理論、運輸系統(tǒng)、network分析以及信息理論等等[16～18]。

建立了半直覺模糊圖模型,用頂點表示對象,用具有直覺模糊測度的邊刻畫對象之間的聯(lián)系。并給出了半直覺模糊圖的生成子圖、度、路徑、相關(guān)截圖、序關(guān)系、最大生成樹等概念。文章繼續(xù)研究了半直覺模糊圖路徑相關(guān)問題。定義了半直覺模糊圖的路徑可達度用以刻畫路徑的擁塞情況,引入最強可達路徑的概念,用以計算擁塞狀況為主要限制因素下的最優(yōu)路徑。給出了求最強可達路徑的形式化方法,證明了算法的合理性;并作了算法復(fù)雜度分析。最后結(jié)合實例用該算法計算了商洛學(xué)院到商洛市區(qū)內(nèi)其他10個地方的最優(yōu)路徑。

2 半直覺模糊圖及其路徑可達性

1)V={v1,v2,…,vn}為頂點之集,表示有限個對象;

1) 序列v0e1v1e2…vkek稱為頂點v0到頂點vk的通路或路徑,記作path(v0,vk);

2)k稱為路徑path(v0,vk)的特征長度pt(v0,vk);

3) 若path(v0,vk)上的所有邊都不相同,則稱path(v0,vk)為簡單通路;若所有頂點都不相同,則稱path(v0,vk)為基本通路;

4) 若v0=vk則稱path(v0,vk)為回路;若path(v0,vk)既是簡單通路又是回路,稱path(v0,vk)為簡單回路;若path(v0,vk)上除v0,vk外其他頂點各不相同且path(v0,vk)是回路,稱path(v0,vk)為基本回路。

1) 若d>0則稱e1相關(guān)大于或不相關(guān)小于e2記作e1?e2。

2) 若d<0則稱e1相關(guān)小于或不相關(guān)大于e2記作e1e2。

path(v0,vk)=v0e1v1e2…vk-1ekvk

定義path(v0,vk)可達度為

定理1pl(v0,vk)刻畫了path(v0,vk)的最小通暢情況和最大擁塞情況。pll(v0,vk)根據(jù)乘法原理計算了path(v0,vk)整體的通暢情況和擁塞情況。

path(v0,vk)1=v0e1v1e2…vk1-1ek1vk

path(v0,vk)2=v0e1v1e2…vk2-1ek2vk

?

path(v0,vk)m=v0e1v1e2…vkm-1ekmvk

?j=1,2,…,m,定義v0到頂點vk的最強可達度為

其中取得最強可達度的路徑：

path(v0,vk)j=v0e1v1e2…vkj-1ekjvk

稱為點v0到頂點vk的最強可達路徑，記作

PATH(v0,vk)

1)PL(v0,vk)為頂點v0到頂點vk的所有以最小通暢、最大擁塞可達的路徑中可達性最高的路徑的可達度。

2)PLL(v0,vk)為頂點v0到頂點vk的所有路徑中整體通暢情性最高的路徑的可達度。

定理3 若(μ1,λ1),(μ2,λ2)為半直覺模糊圖中兩條相鄰邊e1,e2的可達度,則路徑e1,e2的可達度不大于(μ1,λ1),(μ2,λ2)。

證明:因為μ1,λ1,μ2,λ2∈[0,1]，所以：

pl(e1,e2)=(μ1∧μ2,λ1∨λ2)≤(μ1,λ1),(μ2,λ2)

pll(e1,e2)=(μ1·μ2,λ1·λ2)≤(μ1,λ1),(μ2,λ2)

定理3表明同一路徑上越長的前綴路徑可達度越小。

定理4 設(shè)(μ1,λ1),(μ2,λ2),(μ3,λ3)分別為半直覺模糊圖中邊e1,e2,e3的可達度,且存路徑e1,e2和e1,e3;若

(μ2,λ2)≥(μ3,λ3)

則路徑e1,e2可達度大于路徑e1,e3可達度。

證明:因為(μ2,λ2)≥(μ3,λ3),μ1,λ1,μ2,λ2,μ3,λ3∈[0,1]，所以

pl(e1,e2) =(μ1∧μ2,λ1∨λ2)≥(μ1∧μ3,λ1∨λ3)

=pl(e1,e3)

pll(e1,e2) =(μ1·μ2,λ1·λ2)≥(μ1·μ3,λ1·λ3)

=pll(e1,e3)

定理4表明特征長度相同的路徑上的邊的可達度越大,路徑可達度越大。

證明:用反證法。

前提PATH(v0,vk)=v0e1v1e2…vk-1ekvk,根據(jù)定義5有,路徑path(v0,vk)=v0e1v1e2…vk-1ekvk,限制可達度pl(v0,vk)最大。

pl(v0,vk-1)′=PL(v0,vk-1)≥pl(v0,vk-1)

pl(v0,vk)′=pl(v0,vk-1)′°(μek,λek,)

≥pl(v0,vk-1)°(μek,λek,)=pl(v0,vk)

這與pl(v0,vk)最大矛盾。所以假設(shè)不成立,即,path(v0,vk-1)=v0e1v1e2…vk-2ek-1vk-1是最強可達路徑。

若用整體可達度計算證明過程一樣,所以,PATH(v0,vk-1)=v0e1v1e2…vk-2ek-1vk-1。

定理5表明最強可達路徑的前綴路徑也是最強可達路徑。

3 半直覺模糊圖最強可達路徑計算

1) 初始標(biāo)識:

(1)對s做標(biāo)記為〈(1,0),φ〉,令L={s};

(2)?v∈V-L標(biāo)記為〈es,v,s〉標(biāo)識前件為可達度標(biāo)記,后件為前驅(qū)標(biāo)記。

2) 更新標(biāo)識:

(1)取V-L中所有頂點可達度標(biāo)記最大的一個頂點u,將u加入到L中；

(2)將V-L中與u相鄰的頂點x的可達度標(biāo)記更新成下列二者中的較大者:

x的舊可達度標(biāo)記、u的可達度標(biāo)記(μ,λ)與邊eu,x的可達度(μu,x,λu,x)的合成,(μ,λ)°(μu,x,λu,x)。

這里

如果x的可達度標(biāo)記確實改變,則將x的前驅(qū)標(biāo)記替換成u。若L≠V轉(zhuǎn)到2)。

2) 構(gòu)造最強可達路徑:

v∈V若其可達標(biāo)記為(0,1)，則s到v沒有可達路徑;否則s到v的最強可達度為v的可達度標(biāo)記,序列:v,v的前驅(qū),v的前驅(qū)的前驅(qū),…,s,的逆序列就構(gòu)成了s到v的最強可達路徑計算算法。

證明:只需證明?v∈L,v的可達度標(biāo)識為PL(s,v)或PLL(s,v)即可。

用數(shù)學(xué)歸納法證明。

1) 初始狀態(tài)L={s},s標(biāo)記為〈(1,0),NULL〉,PL(s,s)=PLL(s,s)=(1,0)結(jié)論成立。

2) 設(shè)u1,u2,…,um∈L是L中的u的前驅(qū),則u被u1,u2,…,um的標(biāo)識更新過,且由s到u1,u2,…,um的最強可達路徑已經(jīng)找到。因為u是V-L中所有頂點可達度標(biāo)記最大的一個頂點,不妨設(shè)u1更新u后u的標(biāo)識〈PL(s,u1)°(μu1,u,λu1,u),u1〉的可達標(biāo)識最大。

3) 現(xiàn)在證明u的最終標(biāo)識為

〈PL(s,u1)°(μu1,u,λu1,u),u1〉

由定理5有最強可達路徑的前綴必是最強可達路徑。所以v到u的最強可達路徑至少經(jīng)過u1,u2,…,um中的一個頂點。

將u1,u2,…,um分成兩類，一類是使得u的可達度標(biāo)記最大的u1;u2,…,um劃歸，一類以u2為代表。

現(xiàn)將可能的到達u的最強可達路徑分成四種:

第一種:s,…,u1,u;

第二種:s,…,u1,x,u;x∈V-L且x是s到u的路徑上u的前一個頂點;

第三種:s,…,u2,u;

第四種:s,…,u2,x,u;x∈V-L且x是s到u的路徑上u的前一個頂點。

現(xiàn)在只需證明第一種路徑的可達性最大即可。

由定理3,pl(s,…,u1,u)≥pl(s,…,u1,x,u)和pl(s,…,u2,u)≥pl(s,…,u2,x,u)成立。

又因為前設(shè)“u1更新u后u的標(biāo)識〈PL(s,u1)°(μu1,u,λu1,u),u1〉的可達標(biāo)識最大”有pl(s,…,u1,u)≥pl(s,…,u2,u)。這樣就證明了第一種路徑的可達性最大。

由1)、2)、3)歸納得到?v∈L,v的可達度標(biāo)識為PL(s,v)或PLL(s,v)。

定理7 用最強可達路徑計算算法的空間復(fù)雜度和時間復(fù)雜度都為o(n2)。

證明:算法的輸入為半直覺模糊圖;其頂點集和鄰接矩陣空間復(fù)雜度為o(n)和o(n2)。中間計算需存儲標(biāo)識規(guī)模為o(n)。所以算法的空間復(fù)雜度不超過o(n2)。

算法的主要計算時間在第2)步更新標(biāo)識。找到當(dāng)前可達標(biāo)識最大的頂點復(fù)雜度為o(n),更新其他頂點標(biāo)識的時間復(fù)雜度也是o(n)。而每次向L中添加一個頂點就更新一次標(biāo)識,共添加n-1次頂點,根據(jù)加法原理總的時間復(fù)雜度為o((n-1)·o(n))=o(n2)。

4 基于半直覺模糊圖的最優(yōu)路徑選擇實例

經(jīng)典圖論中求路徑可達性和最優(yōu)路徑?jīng)]有考慮路徑的通暢情況,比如路況如何、道路是否擁擠或堵車。半直覺模糊圖中邊的相關(guān)度和不相關(guān)度可以很自然地刻畫這些信息。下面給出一個實例。圖1為商洛市區(qū)交通地圖的一部分。圖1中有14條邊代表14段街道,現(xiàn)將統(tǒng)計結(jié)果所得的每條街道通暢程度和阻塞程度作為半直覺模糊圖的邊的相關(guān)度和不相關(guān)度得到圖2所示半直覺模糊圖。

圖1 商洛市部分交通圖

圖2 圖1建模所得直覺模糊圖

下面用最強可達路徑計算算法求求解商洛學(xué)院v0到中心醫(yī)院v9的最強可達路徑PATH(v0,v9)。

基于限制可達度計算的結(jié)果為表1。

基于整體可達度的計算結(jié)果為表2。

結(jié)果顯示基于限制可達度計算的最強可達路徑為v0v1v3v5v6v8v7v9,最強可達度為(0.63,0.36)，表明該路徑上最壞情況下63%暢通,36%擁堵;基于整體可達度計算的最強可達路徑為v0v1v3v5v7v9,最強可達度為(0.23,0.00)，表明該路徑上最壞總體來說23%的暢通,0.00%擁堵。因為商洛市區(qū)道路擁塞相對不嚴(yán)重，所以認為基于整體可達度計算的最強可達路徑為v0v1v3v5v7v9，即為商洛學(xué)院v0到中心醫(yī)院v9的最優(yōu)路徑。

表1 基于限制可達度計算結(jié)果

表2 基于整體可達度計算結(jié)果

5 結(jié)語

文章建立了半直覺模糊圖模型。給出了半直覺模糊圖的路徑、序關(guān)系等概念。定義了半直覺模糊圖路徑的限制可達度和整體可達度,分別從最保守情況和整體情況兩個方面刻畫了現(xiàn)實中道路的擁塞情況。引入了最強可達路徑的概念,最強可達路徑是擁塞成為路徑選擇主要因素時的最優(yōu)路徑。給出了求最強可達路徑的算法,證明了算法的合理性,并對算法的復(fù)雜度進行了分析,給出了詳盡的證明過程。給出了一個求最強可達路徑的實例,結(jié)果顯示文章給出的求最強可達路徑的算法合理高效且自動化程度高。

現(xiàn)實道路的通暢性與路況、流量、時間等因素都有關(guān)系。比如假期通暢性差于平時,就對平時而言上下班時段道路通暢性也要差于其他時間。所以路徑的可達度是難以確定的。解決的方法是分情況對待,比如按時間段給出道路的通暢情況;計算特定時段的最優(yōu)路徑。最優(yōu)路徑還與路徑的長度相關(guān),考慮到這一主要因素,可以給半直覺模糊圖的邊加權(quán),然后計算最優(yōu)加權(quán)路徑。這些問題筆者會在后續(xù)研究中解決。

[1] Yuan Y,王丁偉.緊急撤離時的多目標(biāo)路徑選擇模型與算法[C]//2007 IEEE自動化與邏輯國際會議.中國南京:IEEE,2007:340-344. Yuan Y, WANG Dingwei. Multi—objective path selection model and algorithm for emergency evacuation[C]//2007 IEEE International Conference on Automation and Logistics. Jinan, China: IEEE,2007:340-344.

[2] Fujita N, 1wata A. Adaptive and efficient multiple path pre—computation for QoS routing protecols[C]//2001 Global Telecommunications Conference. SanAntonio, TX, USA: IEEE,2001:2215-2219.

[3] Li Yuxi, Harms J, Hohe R. Fast exact multi-constraint shortest path algorithms[C]//2007 IEEE International Conference on Communication. Glasgow, Scodland, UK: IEEE,2007:123-130.

[4] K Atanassov. Intuitionistic Fuzzy sets[J]. Fuzzy Sets And System,1986(1):87-96.

[5] Zadeh L A. Fuzzy Sets[J]. Information and Control,1965,8:338-353.

[6] A. Rosenfeld. Fuzzy graphs[C]//L. A. Zadeh, K. S. Fu, M. Shimura. Fuzzy Sets and Their Applications. New York: Academic Press, 1975:77-95.

[7] P. Bhattacharya. Some remarks on fuzzy graphs[J]. Pattern Recognition Letters,1987,6:297-302.

[8] K. R. Bhutani. On Automorphism of Fuzzy graphs[J]. Pattern Recognition Letters,1989,9:159-162.

[9] J. N. Mordeson, C. S. Peng. Operations on fuzzy graphs[J]. Information Sciences,1994,79:159-170.

[10] J. N. Mordeson, P. S. Nair. Fuzzy Graphs and Fuzzy Hypergraphs[M]. Heidelberg: PhysicaVerlag, 1998. Second edition 2001.

[11] M. S. Sunitha, A. Vijayakumar. Complement of a fuzzy graph[J]. Indian Journal of Pureand Applied Mathematics,2002,33:1451-1464.

[12] K. R. Bhutani, A. Battou. On M-strong fuzzy graphs[J]. Information Sciences,2003,155:103-109.

[13] K. R′ Bhutani, A. Rosenfeld. Strong arcs in fuzzy graphs[J]. Information Sciences,2003,152:319-322.

[14] A. N. Gani, J. Malarvizhi. Isomorphism properties on strong fuzzy graphs[J]. International Journal of Algorithms, Computing and Mathematics,2009,2:39-47.

[15] A. Boulmakoul. Fuzzy graphs modelling for HazMat telegeomonitoring[J]. European Journal of Operational Research,2006,175(3):1514-1525.

[16] K. P. Huber, M. R. Berthold. Application of fuzzy graphs for metamodeling[C]//FuzzySystems Proceedings, 1998. IEEE World Congress on Computational Intelligence,1998(1):640-644.

[17] A. Kiss. An application of fuzzy graphs in database theory[J]. Pure Mathematics and Applications,1991,1(3-4):337-342.

[18] L. T. Koczy. Fuzzy graphs in the evaluation and optimization of networks[J]. Fuzzy Sets and Systems,1992,46:307-319.

Path of Half Intuitionistic Fuzzy Graph

YU Xianfeng XING Xue LI Chao

(Institute of Mathematics and Computer Application, Shangluo University, Shangluo 726000)

Seen objects as vertex set, intuitionistic fuzzy number is used to depict the correlation and irrelevance between objects, which are defined as intuitionistic fuzzy edge. A half intuitionistic fuzzy graph model is built. The definations about path, and order relation of a half intuitionistic fuzzy graph are given. The limitative accessibility and gross accessibility of the path of a half intuitionistic fuzzy graph are defined. which are used to calculate the congestion situation of the path. The definition about strongest accessible path of a half intuitionistic fuzzy graph is introduced. The calculation algorithm of strongest accessible path is given. The algorithm can be used to calculate an optimum path when congestion is regarded as a main limiting factor. The rationality of the algorithm is proved and its complexity is analyzed. A example about calculating the strongest accessible path is given. The calculation result shows that the algorithm is reasonable and efficient and has a high degree of automation.

half intuitionistic fuzzy graph, path accessibility, strongest accessible path

2016年8月11日,

2016年9月18日

商洛學(xué)院科研項目(編號:15SKY001);陜西省教育廳專項科研計劃項目(編號:16JK1236)資助。

魚先鋒,男,碩士,講師,研究方向:模糊系統(tǒng)分析、模型檢測。邢雪,女,碩士,講師,研究方向:優(yōu)化算法與模型。李超,男,碩士,教授,研究方向:數(shù)論。

TP301.6

10.3969/j.issn.1672-9722.2017.02.019