半直覺模糊圖的路徑研究

魚先鋒 邢 雪 李 超

(商洛學院數學與計算機應用學院 商洛 726000)

半直覺模糊圖的路徑研究

魚先鋒 邢 雪 李 超

(商洛學院數學與計算機應用學院 商洛 726000)

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

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

Class Number TP301.6

1 引言

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

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

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相關大于或不相關小于e2記作e1?e2。

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

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

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

定理1pl(v0,vk)刻畫了path(v0,vk)的最小通暢情況和最大擁塞情況。pll(v0,vk)根據乘法原理計算了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 設(μ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,根據定義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)最大矛盾。所以假設不成立,即,path(v0,vk-1)=v0e1v1e2…vk-2ek-1vk-1是最強可達路徑。

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

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

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

1) 初始標識:

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

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

2) 更新標識:

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

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

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

這里

如果x的可達度標記確實改變,則將x的前驅標記替換成u。若L≠V轉到2)。

2) 構造最強可達路徑:

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

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

用數學歸納法證明。

1) 初始狀態L={s},s標記為〈(1,0),NULL〉,PL(s,s)=PLL(s,s)=(1,0)結論成立。

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

3) 現在證明u的最終標識為

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

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

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

現將可能的到達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的前一個頂點。

現在只需證明第一種路徑的可達性最大即可。

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

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

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

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

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

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

4 基于半直覺模糊圖的最優路徑選擇實例

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

圖1 商洛市部分交通圖

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

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

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

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

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

表1 基于限制可達度計算結果

表2 基于整體可達度計算結果

5 結語

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

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

[1] Yuan Y,王丁偉.緊急撤離時的多目標路徑選擇模型與算法[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日

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

魚先鋒,男,碩士,講師,研究方向:模糊系統分析、模型檢測。邢雪,女,碩士,講師,研究方向:優化算法與模型。李超,男,碩士,教授,研究方向:數論。

TP301.6

10.3969/j.issn.1672-9722.2017.02.019