利用二元擬陣Kn圖的一種建格方法

毛華，史明

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定, 071002)

利用二元擬陣Kn圖的一種建格方法

毛華，史明

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定, 071002)

由于交通網(wǎng)絡(luò)紛繁復(fù)雜，難以直觀分析和直接處理。若出行者根據(jù)自己喜好和習(xí)慣決定出行策略，則需對(duì)出行方案有清楚的了解。針對(duì)此問(wèn)題，建立交通網(wǎng)絡(luò)圖——Kn模型，對(duì)具有帶環(huán)路和重邊路的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)圖，可以完全轉(zhuǎn)化為Kn圖處理。通過(guò)概念格理論，得到Hasse示圖，方便人們對(duì)某些屬性條件方案的提取，便于后續(xù)工作處理。對(duì)Kn圖進(jìn)行研究之后發(fā)現(xiàn)，在特定的多個(gè)屬性影響下，會(huì)形成一個(gè)三角形圈，于是結(jié)合擬陣中二元擬陣的標(biāo)準(zhǔn)矩陣的定義，挖掘出一種特殊形式背景。根據(jù)這種形式背景的特殊性，給出基于二元擬陣的Kn圖的概念格算法。結(jié)合生活中的例子，驗(yàn)證該算法可行性。由于模型具有這種普遍性，所有結(jié)果可推廣到具有類似形式背景的其他領(lǐng)域研究中。

二元擬陣；標(biāo)準(zhǔn)矩陣表示；Kn圖；二部圖；圖論；概念格；形式背景；Hasse示圖

中文引用格式：毛華，史明.利用二元擬陣Kn圖的一種建格方法[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(3): 333-340.

英文引用格式：MAO Hua，SHI Ming. A constructive method of lattice using theKndiagram of binary matroid[J]. CAAI transactions on intelligent systems, 2017, 12(3): 333-340.

現(xiàn)代經(jīng)濟(jì)發(fā)展中，大城市經(jīng)濟(jì)圈[1]內(nèi)至少有一個(gè)或多個(gè)經(jīng)濟(jì)發(fā)達(dá)并具有較強(qiáng)城市功能的中心城市，以便帶動(dòng)周圍其他城市的發(fā)展，這種經(jīng)濟(jì)圈模式現(xiàn)已成為城市經(jīng)濟(jì)圈發(fā)展的增長(zhǎng)級(jí)。實(shí)踐證明，經(jīng)濟(jì)圈中以三個(gè)地區(qū)為最好，例如京津冀經(jīng)濟(jì)圈、長(zhǎng)江三角洲經(jīng)濟(jì)圈、珠三角經(jīng)濟(jì)圈等。另外，從數(shù)學(xué)方面分析，若將經(jīng)濟(jì)圈中每個(gè)城市視為一個(gè)頂點(diǎn)，城市間有路可達(dá)時(shí)連接為邊，則一個(gè)經(jīng)濟(jì)圈為一個(gè)圖。依據(jù)圖論的知識(shí)可知，在多邊形圖中，三個(gè)頂點(diǎn)構(gòu)成的圈(即三角形)是最穩(wěn)定的，因此本文考慮的圈將以三角形為基本單元。

隨著經(jīng)濟(jì)的發(fā)展，許多城市面臨著嚴(yán)重的交通擁堵。若出行者對(duì)自己要經(jīng)過(guò)交通網(wǎng)絡(luò)的路徑、費(fèi)用、時(shí)間等能夠以清晰地、直觀地方式得到，則完成任務(wù)的效率將會(huì)大大提高。關(guān)于在復(fù)雜的交通網(wǎng)絡(luò)的條件下，研究合理的出行路徑模型和算法，請(qǐng)參見(jiàn)文獻(xiàn)[2-9]?；诙鄬傩詶l件路徑選擇問(wèn)題，文獻(xiàn)[2-9]以及目前掌握的材料中，均沒(méi)有涉及對(duì)于交通網(wǎng)路信息提取的概念格[10]可視化研究。

概念格建立了對(duì)象和屬性之間的一種概念層次結(jié)構(gòu)，是數(shù)據(jù)分析和規(guī)則提取的一種有效工具。Whitney[11]在1935年首次提出的擬陣已經(jīng)被廣泛地應(yīng)用于信息編碼[12]和網(wǎng)絡(luò)安全[13]等領(lǐng)域。將擬陣與概念格理論結(jié)合、圖論[14-15]與概念格理論結(jié)合來(lái)解決問(wèn)題，已有許多成功的案例[16-21]。

由于現(xiàn)實(shí)生活中，人們出行受多個(gè)屬性條件的限制，針對(duì)這些限制，經(jīng)過(guò)研究發(fā)現(xiàn)Kn簡(jiǎn)單圖中形成三角形圈的一種特殊性質(zhì)。由此，可以對(duì)復(fù)雜的交通網(wǎng)絡(luò)進(jìn)行分析、轉(zhuǎn)化，形成Kn簡(jiǎn)單圖。進(jìn)而，能夠建立網(wǎng)絡(luò)模型，構(gòu)建模型所對(duì)應(yīng)的關(guān)聯(lián)矩陣。依據(jù)Kn圖所產(chǎn)生的特殊形式背景，建立概念格信息提取方法。從而，給出基于二元擬陣Kn圖的一種建格方法，并利用具體實(shí)例驗(yàn)證方法的正確性與有效性。

1 預(yù)備知識(shí)

本節(jié)主要介紹網(wǎng)絡(luò)Kn圖、擬陣和概念格一些定義與相關(guān)結(jié)論。有關(guān)圖的基本概念和完全圖的定義，讀者請(qǐng)參見(jiàn)文獻(xiàn)[14]。有關(guān)二元擬陣和圖的擬陣可表示性請(qǐng)參見(jiàn)文獻(xiàn)[11]。

定義1[22]設(shè)任意(無(wú)向)圖G=(V,E)，其中頂點(diǎn)集V={v1,v2,…,vn}，邊集E={e1,e2,…,ee}。用mij表示頂點(diǎn)vi與邊ej關(guān)聯(lián)的次數(shù)，可能取值為0,1,2，稱所得矩陣M(G)=(mij)n×e為圖G的關(guān)聯(lián)矩陣。

定義4[17]形式背景K=(G,M,I)定義為一個(gè)三元數(shù)組，其中G中的元素被稱為對(duì)象，M中的元素被稱為屬性。I?G×M，用gIm表示(g,m)∈I，即對(duì)象g具有屬性m。

定義5[17]形式背景(G,M,I)中的概念定義為元素對(duì)(A,B)，其中A?G，B?M，A稱為概念的外延，B稱為概念的內(nèi)涵，并且滿足以下條件：

2)A?A″,B?B″;

定義6[17]設(shè)(A1,B1)、(A2,B2)是L(G,M,I)中的兩個(gè)概念，定義二元關(guān)系(A1,B1)≤(A2,B2)?A1?A2?B1?B2,稱(A1,B1)是(A2,B2)的子概念，(A2,B2)是(A1,B1)的父概念。若不存在概念(A3,B3)使得(A1,B1)≤(A3,B3)≤(A2,B2)成立，則稱(A1,B1)是(A2,B2)的直接子概念，(A2,B2)是(A1,B1)的直接父概念。

不難證明這種父概念-子概念關(guān)系(也稱泛化-特化關(guān)系)是L(G,M,I)上的一個(gè)偏序關(guān)系。事實(shí)上L(G,M,I)關(guān)于該偏序關(guān)系是一個(gè)完備格，稱為形式背景(G,M,I)的概念格，記為L(zhǎng)(G,M,I)。

引理2[17]設(shè)(G,M,I)是一個(gè)形式背景，則L(G,M,I)關(guān)于上面定義的序“≤”構(gòu)成的是完備格，其中上下確界由下式給出：

為了模型的建立和討論表述簡(jiǎn)捷，給出如下幾個(gè)定義。

定義7 含圈基：在Kn圖中滿足從一個(gè)頂點(diǎn)出發(fā)，到其他n-1個(gè)頂點(diǎn)的相連接的邊叫做含圈基。

定義8 基頂點(diǎn)：在Kn圖中滿足從一個(gè)頂點(diǎn)出發(fā)包含的所有相連的含圈基的頂點(diǎn)叫做基頂點(diǎn)。

定義9 基最小圈：在一個(gè)三角形最小圈中，滿足一個(gè)最小圈中包含兩個(gè)基的三角形圈，叫做基最小圈。

2 模型的建立

圖論主要研究圖的拓?fù)湫再|(zhì)，為任何一個(gè)包含某種二元關(guān)系系統(tǒng)提供一種分析和描述模型。眾所周知，交通網(wǎng)絡(luò)可以用圖表示出來(lái)，也可把交通網(wǎng)絡(luò)里的距離當(dāng)作兩點(diǎn)之間的權(quán)值加入進(jìn)去。

復(fù)雜網(wǎng)絡(luò)中的交通網(wǎng)絡(luò)對(duì)應(yīng)圖論里一類特殊的圖結(jié)構(gòu)，具有與應(yīng)用相關(guān)的很多重要特征。對(duì)于一些網(wǎng)絡(luò)中出現(xiàn)的復(fù)雜的網(wǎng)絡(luò)，作如下處理。

1)對(duì)于兩個(gè)頂點(diǎn)之間具有多重邊的情況，選擇其中權(quán)值最小的邊。

2) 當(dāng)兩個(gè)頂點(diǎn)之間的權(quán)值一樣時(shí)，任意選擇其中一條邊，固定下來(lái)，成為最熟悉的一條道路。

3)對(duì)于帶環(huán)圖的這種情況，因?yàn)閷?shí)際問(wèn)題考慮的是對(duì)于一個(gè)工廠的運(yùn)輸，自身運(yùn)輸沒(méi)有任何實(shí)際的意義。例如：如果是一家超市，自身對(duì)于自身運(yùn)輸也沒(méi)有意義，所以不予考慮。

具有重邊或有環(huán)的圖都可以轉(zhuǎn)化為簡(jiǎn)單圖應(yīng)對(duì)出行問(wèn)題，因此復(fù)雜網(wǎng)絡(luò)圖可以轉(zhuǎn)化為簡(jiǎn)單圖，用以討論相應(yīng)的出行問(wèn)題。由于在具有n個(gè)頂點(diǎn)的簡(jiǎn)單圖中，Kn圖結(jié)構(gòu)最復(fù)雜，所以只要解決了Kn圖的出行問(wèn)題，其他的簡(jiǎn)單圖的出行問(wèn)題將會(huì)迎刃而解。對(duì)于非Kn的n個(gè)頂點(diǎn)的簡(jiǎn)單圖，因?yàn)樗鼈兪荎n的子圖，所以可以通過(guò)加邊，使其成為Kn圖，只需將新加邊的權(quán)值定義為0，采用本文的方法，完全可以解決出行問(wèn)題。基于以上的討論，只需解決具有Kn圖這樣的交通網(wǎng)絡(luò)的出行問(wèn)題，因此本文只研究Kn圖。

現(xiàn)有n個(gè)城市，任意兩個(gè)城市均由交通道路連接。一位出行者要從自己所居住的城市去其他n-1個(gè)城市辦事情，要求到達(dá)其他任意兩個(gè)城市后再回到自己所居住的城市，現(xiàn)在的問(wèn)題是：如何找到以3個(gè)城市為三角形經(jīng)濟(jì)圈的一個(gè)出行方案。

首先建立一個(gè)網(wǎng)絡(luò)模型，構(gòu)建其關(guān)聯(lián)矩陣。由于關(guān)聯(lián)矩陣是一個(gè)0-1矩陣，信息提取中的任一個(gè)形式背景可視為一個(gè)0-1矩陣，因此依據(jù)形式背景的特殊性，建立概念格信息提取方法，進(jìn)而找到人們所需的最適合出行方案。

2.1 問(wèn)題的提出

在不同城市間構(gòu)建現(xiàn)代化交通網(wǎng)絡(luò)，實(shí)現(xiàn)城市間交通一體化，將會(huì)極大方便交通出行。問(wèn)題是：如何在眾多出行方案中選取合適的方案，成為人們出行前需要解決的問(wèn)題。交通運(yùn)輸網(wǎng)絡(luò)錯(cuò)綜復(fù)雜，很難給人們帶來(lái)直接幫助，需要對(duì)交通運(yùn)輸網(wǎng)絡(luò)進(jìn)行簡(jiǎn)化和直觀化，得到一個(gè)簡(jiǎn)化的網(wǎng)絡(luò)。若出行者需要計(jì)算出自己所居住的城市和其他任意兩個(gè)城市的距離和，即第1節(jié)定義9中的基最小圈，判斷走哪個(gè)基最小圈距離和最短時(shí)，探究交通網(wǎng)絡(luò)Kn圖模型中的最小經(jīng)濟(jì)圈所需出行的路徑距離就變得有意義了。

2.2 模型的條件

設(shè)有n個(gè)城市，每個(gè)城市看作一個(gè)頂點(diǎn)，兩個(gè)城市之間有路可達(dá)時(shí)，用一條線相連接，建立城市網(wǎng)絡(luò)圖。圖中頂點(diǎn)用v1，v2，…，vn表示，組成集合V={v1,v2,…,vn}。網(wǎng)絡(luò)圖中vi，vj之間有路徑可達(dá)，記相連接的邊為eij，將此交通網(wǎng)絡(luò)圖記為G=(V,E)，得G為一個(gè)有限無(wú)向圖。出行者從給定的一個(gè)頂點(diǎn)城市v1出發(fā)去辦事，要求路徑中必須經(jīng)過(guò)兩個(gè)頂點(diǎn)城市(除去給定城市頂點(diǎn)以外的其他任意兩個(gè)頂點(diǎn)城市)，再返回到出發(fā)城市頂點(diǎn)v1。由于出行者走的道路為一個(gè)三角形，現(xiàn)在的問(wèn)題是要選擇一個(gè)三角形在距離和花費(fèi)的時(shí)間都少的三角形作為出行者的最終出行方案，這就需要找到所有可能的出行方法，換句話說(shuō)，出行者需要出行前找到所有需要走過(guò)的路徑和出行方案，以便從中選擇最佳方案， 這些方案對(duì)決策者綜合路徑距離、時(shí)間、花費(fèi)決策時(shí)有重要的意義，可以幫助其更加直觀、快速地做決定，節(jié)約決策時(shí)間。

2.3 問(wèn)題的分析

交通城市之間的無(wú)向圖G進(jìn)行轉(zhuǎn)化后是頂點(diǎn)為n的完全圖，記G為Kn圖。因Kn圖對(duì)應(yīng)的關(guān)聯(lián)矩陣滿足二元擬陣M，知定義7的含圈基滿足定義3的擬陣M，即實(shí)際生活中人們出行方案里的最小三角形圈。于是在Kn圖的二元擬陣的標(biāo)準(zhǔn)矩陣表示如下：在對(duì)應(yīng)組成基本圈的三條邊下標(biāo)記1，沒(méi)有組成基本圈的邊下標(biāo)記0，然后把得到的矩陣作為含0和1的形式背景。在上面進(jìn)行概念格的探索和證明時(shí)發(fā)現(xiàn)，在Kn圖中將二元擬陣中的基本圈即定義9的基最小圈，作為對(duì)象，每?jī)蓚€(gè)頂點(diǎn)之間相連的邊作為屬性，建立形式背景，找尋概念會(huì)遵循一定的數(shù)學(xué)規(guī)律，運(yùn)用此規(guī)律進(jìn)行建格，速度很快。

2.4 模型的解決

2.4.1 Kn圖的建格模型

表1 頂點(diǎn)數(shù)與基最小圈的規(guī)律

Table 1 Vertex number and the basis of the smallest circle of the law

頂點(diǎn)邊數(shù)含圈基基最小圈3321463351046615510721615????n…n-1n(n-1)2-(n-1)

將圖G=(V,E)對(duì)應(yīng)的擬陣M中定義9基最小圈集O視為形式背景中的對(duì)象集，將圖G的邊集E視為屬性集P，圈Ci中含有某條邊ej時(shí)，記Ciej值為1，否則為0，得到形式背景(O,P,I)，對(duì)象集O={C1,C2,…,Cn}，屬性P={b1,b2,…,bn}。特別地，當(dāng)圖G=(V,E)為Kn圖時(shí)，圖G=(V,E)對(duì)應(yīng)的形式背景L(Okn,Pkn,Ikn)如表2所示。

表2Kn圖的形式背景L(Okn,Pkn,Ikn)

Table 2 Formal contextL(Okn,Pkn,Ikn) ofKndiagram

Ib1b2b3bn-1…bn(n-1)2C11010…0C20110…0C31101…0?????0Cn(n-1)2-(n-1)00………1

定義10 在Kn圖的形式背景L(Okn,Pkn,Ikn)對(duì)應(yīng)的概念格L(O,P,I)中給出“層”的定義：

引理3 1)根據(jù)完全圖的定義和表1知，當(dāng)定義7含圈基個(gè)數(shù)為n-1時(shí)，與定義8基頂點(diǎn)相連接的每個(gè)基b1，b2，…，bn-1對(duì)應(yīng)的對(duì)象個(gè)數(shù)為n-2個(gè)。

2)根據(jù)定義9含兩個(gè)基的基最小圈最多有一條重邊。

定理1Kn圖對(duì)應(yīng)的形式背景概念格有且僅有4層。

定理2Kn圖模型建立的概念格L(Kn)的第2層和第3層的Hasse示圖組成一個(gè)二部圖。

證明 根據(jù)定義2(二部圖)的定義，二部圖G=(V1,V2,E)由頂點(diǎn)集V1和V2及邊集E?V1×V2組成，V1={x1,x2,…,xs}，V2={y1,y2,…,yt}，則二部圖G=(V1,V2,E)的伴隨矩陣為二元矩陣A(aij)，這里aij=1，當(dāng)且僅當(dāng)(xi,yj)∈E。設(shè)V1為對(duì)象集，V2為屬性集，則二部圖的伴隨矩陣就是形式背景。二部圖G=(V1,V2,E)由兩個(gè)非交頂點(diǎn)集V1，V2組成，且G的每條邊的頂點(diǎn)分別在V1，V2中。設(shè)V1是第2層概念的集合，V2是第3層概念的集合，則在Kn圖中概念之間滿足定義6，(C1,b1)≤(C2,b2)?C1?C2(?b2?b1)，根據(jù)子概念-父概念的關(guān)系建立連線是一個(gè)二部圖，如圖1所示。

圖1 K4圖的二部圖Fig.1 Bipartite graph of K4 diagram

再把第1層和第4層概念(O,{})和({},P)加進(jìn)圖1，根據(jù)定理1建立概念格得Hasse示圖，如圖2所示。Hasse圖是利用概念之間的泛化和特化進(jìn)行繪制的，由于概念格的完備性，概念格確定了，其Hasse圖也唯一確定了。概念格最上層是全概念，最下層是空概念。Hasse圖中的邊分別連接在直接父概念和直接子概念之間。

圖2 K4圖的概念格Fig.2 Concept lattice of K4 diagram

根據(jù)K4圖的格結(jié)構(gòu)，利用數(shù)學(xué)歸納法分別對(duì)K5圖、K6圖、Kn圖進(jìn)行建格，得出Kn圖建立概念格的一個(gè)算法過(guò)程。

2.4.2 算法過(guò)程

通過(guò)對(duì)特殊限制Kn圖的規(guī)律發(fā)現(xiàn)，滿足Kn圖二元標(biāo)準(zhǔn)矩陣特點(diǎn)的都可以建成一個(gè)Hasse示圖。對(duì)于具有這種特定形式背景的概念，用上面的建格方法進(jìn)行建格，速度很快。下面給出對(duì)象是基最小圈，屬性是邊的形式背景的建格過(guò)程。

輸入 形式背景(O,P,I)。

輸出 集合C，(O,P,I)所有的概念。

1)C：={P′,P}初始化屬性集合B=?。

2)找第2層的概念，根據(jù)規(guī)律知道，當(dāng)完全圖為Kn時(shí)，頂點(diǎn)數(shù)為n，與基頂點(diǎn)相連的邊為n-1,即第2層的概念為n-1個(gè)，根據(jù)屬性b1,b2,…，bn-1找到所對(duì)應(yīng)的基最小圈對(duì)象。

4)第1層中的元(概念)，與且僅與第2層的每一個(gè)元分別連線，第4層的元與且僅與第3層的每一個(gè)元分別連線，第2層的元與第3層的元之間的連線關(guān)系可以根據(jù)定理2進(jìn)行。這樣就可以得到所有應(yīng)該存在的連線。即根據(jù)定義6和引理2的偏序關(guān)系(C1,b1)≤(C2,b2)?C1?C2(?b2?b1)，滿足概念格子概念-父概念的關(guān)系，把第1層的概念(O,{})與第2層的概念建立連線，第4層的概念({},P)與第3層概念建立連線加入到步驟2)和3)組成的二部圖中。

2.4.3 算法的復(fù)雜度

根據(jù)形式背景的特殊性，此處得到的概念格有且僅有4層。

第1層的概念和第四層的概念分別是(O,{})和({},P)。

第2層的概念與基頂點(diǎn)連接的邊個(gè)數(shù)為n-1(n表示頂點(diǎn)數(shù))。

與定義5和定義6找尋概念的方式(即參考文獻(xiàn)[22]中13頁(yè)概念格的生成算法1)相比，本文提出的方法更有效。因?yàn)?，如果存在|G|個(gè)對(duì)象，|M|個(gè)屬性，那么相應(yīng)的概念格將可能包含2|G|或2|M|個(gè)概念，計(jì)算量太大。而本文構(gòu)造的概念的算法方式，由于具有一定的規(guī)律性，大大減少了計(jì)算量。

3 應(yīng)用實(shí)例

超市里冷凍豬肉和冷鮮豬肉因儲(chǔ)存時(shí)間的長(zhǎng)短不同，價(jià)格有很大差別。當(dāng)決策者需要判斷送貨多少時(shí)，也許會(huì)出現(xiàn)這家超市里冷鮮豬肉已經(jīng)賣完，而另一家超市里的冷鮮肉賣不出去，這時(shí)由于冷鮮豬肉放置太長(zhǎng)時(shí)間，變成冷凍豬肉而導(dǎo)致價(jià)格下降，造成虧損。針對(duì)這種情況，為了減少虧損，合理決策冷鮮豬肉配送供給，變得十分重要。

因?yàn)楣?yīng)超市里每個(gè)時(shí)間段內(nèi)宰殺豬的數(shù)量一定，所以供貨量一定;又因?yàn)槌蟹峙涿枯v貨車行走的公里數(shù)一定，油費(fèi)消耗一定。根據(jù)以上限制條件，需要貨車從供應(yīng)超市出發(fā)到達(dá)其他任意兩個(gè)供給城市的連鎖超市后，再返回原來(lái)的供應(yīng)超市。為讓決策者更快地給出供應(yīng)超市的貨車供給方案，應(yīng)對(duì)其供貨方案和距離進(jìn)行概念格的可視化建格。

貨物(冷鮮肉)將從石家莊市超市出發(fā)分別運(yùn)往周邊的縣市超市。記石家莊市超市為v1，正定縣超市記為v2，鹿泉市超市記為v3，新樂(lè)市超市記為v4，藁城市超市記為v5。但是貨物運(yùn)輸時(shí)由于宰殺豬數(shù)量的限制只能帶夠發(fā)往兩個(gè)縣市超市的貨物量，再回到出發(fā)地取貨，為了選擇出合適的運(yùn)輸方案，對(duì)其進(jìn)行建格。

根據(jù)貨車配送路線，v1超市距v2超市的距離為b1=15 km，v1超市距v3超市的距離為b2=15 km，v1超市距v4超市的距離為b3=38 km，v1超市距v5超市的距離為b4=31 km，v2超市到v5超市的距離為b5=39 km，v3超市到v5超市的距離為b6=57 km，v4超市到v5超市的距離為b7=52 km，v2超市到v4超市的距離為b8=33 km，v3超市到v4超市的距離為b9=60 km，v2超市到v3超市的距離為b10=34 km。根據(jù)任意兩個(gè)超市之間是否有路相連接，得無(wú)向圖的關(guān)聯(lián)矩陣(這里的距離是大約值，具體的取值可以根據(jù)用戶的需求來(lái)定)：

根據(jù)出行人員的實(shí)際要求，從城市v1出發(fā)后要經(jīng)過(guò)兩個(gè)城市再返回原城市，符合基最小圈定義。建立數(shù)學(xué)模型，根據(jù)無(wú)向圖的關(guān)聯(lián)矩陣A得圖3所示K5圖模型。以頂點(diǎn)v1為出發(fā)地，根據(jù)運(yùn)送貨物的實(shí)際情況，從頂點(diǎn)v1出發(fā)運(yùn)送到其他兩個(gè)頂點(diǎn)經(jīng)過(guò)的距離，得送貨所有可能的方案分別是C1={b1，b4，b5}，C2={b2，b4,b6}和C3={b3,b4,b7}，C4={b1，b3，b8}，C5={b2，b3,b9}，C6={b1，b2，b10}。為在最短的距離內(nèi)把貨物送完，找出所有的送貨路線，提取里面的規(guī)則進(jìn)行建格。

圖3 K5圖Fig.3 K5 diagram

根據(jù)定義3得K5圖的二元擬陣的標(biāo)準(zhǔn)矩陣：

根據(jù)概念格的定義4建立形式背景，如表3。

表3 K5圖的形式背景

利用表3中K5圖的形式背景，根據(jù)本文所給出算法過(guò)程，進(jìn)行概念格Hasse圖的建立。

1)C：={P′,P}初始化屬性集合B=?。

2)找第2層的概念，根據(jù)屬性b1、b2、b3、b4、b5、b6找到所對(duì)應(yīng)的基最小圈對(duì)象C1C4C6、C2C5C6、C3C4C5、C1C2C3得到概念(C1C4C6，b1)、(C2C5C6，b2)、(C3C4C5,b3)、(C1C2C3,b4)。

3)找第3層的概念，根據(jù)完全圖Kn的特點(diǎn)，由對(duì)象C1、C2、C3、C4、C5、C6找到所對(duì)應(yīng)的屬性b1b4b5、b2b4b6、b3b4b7、b1b3b8、b2b3b9、b1b2b10得到概念(C1,b1b4b5)、(C2，b2b4b6)、(C3,b3b4b7)、(C4,b1b3b8)、(C5，b2b3b9)、(C6,b1b2b10)。

4)把第1層和第4層概念(O,{})和({},P)，根據(jù)定義6和引理2的偏序關(guān)系(C1,b1)≤(C2,b2)?C1?C2(?b2?b1)，對(duì)滿足概念格子概念-父概念的關(guān)系[23]，把第1層的概念(O,{})與第2層的概念建立連線,第4層的概念({},P)與第3層概念建立連線加入到步驟2)和3)組成的二部圖中，得到概念格的Hasse示圖，如圖4。

圖4 K5圖的概念格Fig.4 Concept lattice of K5 diagram

從圖4中可以看出，滿足b1這段距離油耗的貨車有且僅有C1、C4、C6方案，滿足b2這段距離油耗的貨車有且僅有C2、C5、C6方案，滿足b3這段距離油耗的貨車有且僅有C3、C4、C5方案，滿足b4這段距離油耗的貨車有且僅有C1、C2、C3方案，還可以快速地計(jì)算出每個(gè)方案需要走的距離里程。若采用方案C1，需走的距離里程為b1+b4+b5=85 km；若采用方案C2，需走的距離里程為b2+b4+b6=103 km;若采用方案C3，需走的距離里程為b4+b6+b7=140 km;若采用方案C4，需走的距離里程為b1+b3+b8=86 km;若采用方案C5，需走的距離里程為b2+b3+b9=113 km;采用方案C6，需要走的距離里程為b1+b2+b10=64 km。從中比較可知，若運(yùn)送貨物途經(jīng)距離最短，可以選擇方案C6。

從圖4中可快速地篩選出運(yùn)輸最短路徑的運(yùn)輸方案和最長(zhǎng)路徑的運(yùn)輸方案，方便出行者對(duì)出行方案的選擇。在其他復(fù)雜網(wǎng)絡(luò)中，兩個(gè)頂點(diǎn)之間會(huì)出現(xiàn)兩條邊，比如重邊的情況，在尋找哪種方案最優(yōu)時(shí)，可能出現(xiàn)多種方案，而本文開(kāi)始時(shí)就已經(jīng)刪除了那些對(duì)選擇方案無(wú)用的邊，因此從概念格的Hasse圖中很容易看出哪個(gè)方案最優(yōu)，不需要出行者進(jìn)行2次或更多次的重新比較。

4 結(jié)束語(yǔ)

根據(jù)京津冀緊密對(duì)接的一體化交通網(wǎng)絡(luò)?；诔鲂姓邔?duì)于交通網(wǎng)絡(luò)路徑的選擇，根據(jù)實(shí)際生活中的一些屬性條件的限制，在Kn圖模型中，根據(jù)三角形圈的一種特殊性，尋找規(guī)律，結(jié)果發(fā)現(xiàn)，對(duì)Kn圖擬陣的標(biāo)準(zhǔn)矩陣的形式背景產(chǎn)生4層。根據(jù)此規(guī)律進(jìn)行建格，提出利用二元擬陣的Kn圖的概念格的建格方法。相比最基本的建格方法，此方法的計(jì)算量要少很多。通過(guò)實(shí)例發(fā)現(xiàn)，針對(duì)這種特殊的形式背景，出行者在提取有用的方案時(shí)，會(huì)更加快速、方便。由于研究背景和素材來(lái)源于實(shí)踐，這類事件很多，因此提出的方法具有很好的推廣意義和應(yīng)用前景。在接下來(lái)的研究中，將會(huì)在Kn圖中加入權(quán)值，進(jìn)行距離和時(shí)間等多種屬性的研究。

[1]左鋒. 經(jīng)濟(jì)學(xué)視野中大城市經(jīng)濟(jì)圈的形成與發(fā)展—論中國(guó)三大城市經(jīng)濟(jì)圈的現(xiàn)狀及其發(fā)展[J]. 華東師范大學(xué)學(xué)報(bào)：哲學(xué)社會(huì)科學(xué)版, 2002, 34(5): 89-95. ZUO Feng. The formation and development of a metropolitan economic circle in the perspec-tive of economics[J]. Journal of east cluna normal university:philosophy and social sciences, 2002, 34(5): 89-95.

[2]胡一竑. 基于復(fù)雜網(wǎng)絡(luò)的交通網(wǎng)絡(luò)復(fù)雜性研究[D]. 上海:復(fù)旦大學(xué), 2008: 1-121. HU Yihong. Analysis of complex transportation networks[D].Shanghai: Fudan University, 2008: 1-121.

[3]劉佳. 復(fù)雜網(wǎng)絡(luò)中最短路徑問(wèn)題的優(yōu)化算法研究[D]. 太原: 太原科技大學(xué), 2007: 1-30. LIU Jia. Research on the algorithm for shortest path problem in complicated network[D]. Taiyuan: Taiyuan University of Science and Technology, 2007: 1-30.

[4]嚴(yán)寒冰, 劉迎春. 基于GIS的城市道路網(wǎng)最短路徑算法探討[J]. 計(jì)算機(jī)學(xué)報(bào), 2000, 23(2): 210-215. YAN Hanbing, LIU Yingchun. A new algorithm for finding shortcut in a city’s road net based on GIS technology[J]. Chinese journal of computers, 2000, 23(2): 210-215.

[5]謝政, 李建平. 網(wǎng)絡(luò)算法與復(fù)雜性理論[M]. 北京:國(guó)防科技大學(xué)出版社, 1995: 120-140.

[6]LAM W H K, LI Zhichun, HUANG Haijun, et al. Modeling time-dependent travel choice problems in road networks with multiple user classes and multiple parking facilities[J]. Transportation research part B: methodological, 2006, 40(5): 368-395.

[7]GAO Song, Chabini I. Optimal routing policy problems in stochastic time-dependent networks[J]. Transportation research parB: methodological, 2006, 40(2): 93-122.

[8]于德新, 楊薇, 楊兆升. 重大災(zāi)害條件下基于 GIS的最短路徑改進(jìn)算法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2011, 11(4): 123-126. YU Dexin, YANG Wei, YANG Zhaosheng. Shortest path improved algorithm based on GIS under large-scale disaster[J]. Journal of traffic and transportation engineering, 2011, 11(4): 123-126.

[9]陳京榮. 交通網(wǎng)絡(luò)路徑選擇及應(yīng)用研究[D]. 蘭州: 蘭州交通大學(xué), 2009: 1-43. CHEN Jingrong. Research on route choice and its application in traffic networks[D]. Lanzhou: Lanzhou Jiaotong University, 2009: 1-43.

[10]GANTER B, Wille R. Formal concept analysis: mathematical foundations[M]. New York: Springer, 1999.

[11]王樹(shù)禾. 圖論[M]. 北京: 科學(xué)出版社, 2009.

[12]BONDY JA. Graph theory[M]. Berlin: Springer Press, 2008.

[13]劉桂珍，陳慶華. 擬陣[M]. 長(zhǎng)沙: 國(guó)防科技大學(xué)出版社, 1994.

[14]吉慶兵. 二元擬陣碼及其對(duì)偶碼[J]. 重慶師范學(xué)院學(xué)報(bào):自然科學(xué)版, 2001, 18(4): 48-50. JI Qingbing. Binary matroid codes and their dual codes [J]. Journal of Chongqing normal university:natural science edition, 2001, 18(4): 48-50.

[15]馬對(duì)霞, 林姿瓊, 祝峰. 擬陣在網(wǎng)絡(luò)安全中應(yīng)用[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2015, 36(8): 1858-1860. MA Duixia, LIN Ziqiong, ZHU Feng. Application of matroids on network security[J]. Journal of Chinese computer systems, 2015, 36(8): 1858-1860.

[16]毛華. 擬陣與概念格的關(guān)系[J]. 數(shù)學(xué)進(jìn)展, 2006, 35(3): 361-365. MAO Hua. The relation between matroid and concept Lattice[J]. Advances in mathematics, 2006, 35(3): 361-365.

[17]毛華, 李斌. 等價(jià)關(guān)系約束屬性的形式概念分析[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46 (36): 158-160. Mao Hua, LI Bin. Formal concept analysis of attributes by equivalent relation[J]. Computer engineering applications, 2010, 46(36): 158-160.

[18]李立峰, 劉三陽(yáng), 羅清君. 弦二部圖的概念格表示[J]. 電子學(xué)報(bào), 2013, 41(7): 1385-1388.

LI Lifeng, LIU Sanyang, LUO Qingjun. Representing chordal bipartite graph using concept lattice theory[J].Chinese journal of electronics, 2013, 41(7): 1385-1388.

[19]李立峰. 鏈圖的概念格表示[J]. 計(jì)算機(jī)科學(xué), 2014, 41(2): 264-266. LI Lifeng. Chain graph and their concept lattice representation[J]. Computer science, 2014, 41(2): 264-266.

[20]MAO Hua. A graph-theoretic method to representing a concept lattice[J]. Applied mathematics and information sciences, 2014, 8(2): 553-561.

[21]MAO Hua. Characterizing trees in property-oriented concept lattices[J]. Armenian journal of mathematics, 2016, 8(2): 86-95.

[22]王海英, 黃強(qiáng), 李傳濤, 等. 圖論算法及其MATLAB實(shí)現(xiàn)[M]. 北京: 北京航空航天大學(xué)出版社, 2010: 1-38.

[23]李娜. 形式概念分析中若干算法的改進(jìn)與實(shí)現(xiàn)[D]. 北京:中央民族大學(xué), 2007: 1-15. LI Na. Improvement and implementation of several algorithms about formal concept analysis[D]. Beijing: Minzu University of China, 2007: 1-15.

A constructive method of lattice using theKndiagram of binary matroid

MAO Hua， SHI Ming

(School of Mathematics and Information Science, Hebei University, Baoding 071002, China)

Because of the complexity of traffic networks, it is difficult to directly analyze and deal with them. If some travelers wish to determine their travel strategy based on their preferences and habits, they should have a clear understanding of their travel plan. To address this problem, a traffic network,Knmodel, was established in this study. It was used to elucidate how to transfer complex networks comprising loops or multiple edges to theKndiagram. With the assistance of formal concept analysis, the corresponding Hasse diagram of theKnmodel was provided. The Hasse diagram facilitates travelers to extract some attributes under certain preconditions, after which the travelers can easily continue their work. Hence, the study of theKndiagram revealed that a triangle circle would form under some effects of specific multiple attributes. Thus, combining with the standard definition of the matrix for binary matroids, a special formal context was obtained. According to the particularity of the formal context, an algorithm was proposed based on the binary matroids for theKndiagram. Utilizing an example, the feasibility of the proposed method was proven. Because the model is universal, the discussions of this research can be extended to other fields with similar formal context.

binary matroid; standard matrix representative;Kndiagram; bipartite graph; graph theory; concept lattice; formal context; Hasse diagram

10.11992/tis. 201704022

http://kns.cnki.net/kcms/detail/23.1538.TP.20170508.0922.010.html

2017-04-19. 網(wǎng)絡(luò)出版日期：2017-05-08.

國(guó)家自然科學(xué)基金項(xiàng)目(61572011).

史明. E-mail：ming1254610676@163.com.

TP18

A

1673-4785(2017)03-0333-08

毛華，女，1963年生，教授，博士后，美國(guó)《數(shù)學(xué)評(píng)論》評(píng)論員,河北省工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)理事,主要研究方向?yàn)橛?jì)算機(jī)數(shù)學(xué)及其應(yīng)用、擬陣?yán)碚摗㈦x散數(shù)學(xué)。已發(fā)表學(xué)術(shù)論文90余篇，其中被SCI、EI檢索20余篇。

史明，女，1989年生，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化、圖論、擬陣?yán)碚?、概念格。已發(fā)表學(xué)術(shù)論文2篇。