基于覆蓋粗糙集的超圖連通性

黃愛萍,黃鳳英

?

基于覆蓋粗糙集的超圖連通性

黃愛萍*,黃鳳英

（廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院，漳州363105）

作為圖論的推廣，超圖已被廣泛應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域。在此領(lǐng)域中，超圖常被用于模擬數(shù)據(jù)之間的結(jié)構(gòu)特征；又因為該領(lǐng)域中的數(shù)據(jù)通常表現(xiàn)為覆蓋的形式，而覆蓋粗糙集為此類數(shù)據(jù)的研究提供了系統(tǒng)的方法。鑒于此，本文將覆蓋粗糙集與超圖聯(lián)系起來，利用覆蓋粗糙集的方法研究了超圖的連通性。首先，由超圖誘導(dǎo)出一個覆蓋；其次，利用該覆蓋上的近似算子研究超圖的連通性。結(jié)果表明，覆蓋粗糙集為研究超圖提供的一種新的方法。

覆蓋粗糙集；超圖；超圖連通性

引言

圖是描述計算機科學(xué)，物理，數(shù)學(xué)等學(xué)科中問題及結(jié)構(gòu)的強有力工具。但因為只能模擬一些二元關(guān)系，這往往不能滿足人們模擬現(xiàn)實生活中遇到的一些復(fù)雜的問題或者數(shù)據(jù)。為了解決這一問題，C.Berge[1]于1960年將圖進行推廣，建立了超圖理論。此理論視集合為超邊，而超圖就是一族超邊的集合。相對圖，超圖能夠模擬更廣泛的關(guān)系。在最近的幾十年里，超圖已經(jīng)受到廣泛學(xué)者的關(guān)注[2-5]。

覆蓋是一類常見的數(shù)據(jù)結(jié)構(gòu)。作為處理這類數(shù)據(jù)的有效工具，覆蓋粗糙集[6]已經(jīng)受到越來越多學(xué)者的廣泛關(guān)注。比如，在理論上，近似算子模型的提出[7,8]、覆蓋公理系統(tǒng)的建立[9,10]、覆蓋約簡問題的研究[11-12]及其與其它學(xué)科的聯(lián)系[13,14]。在應(yīng)用上，覆蓋粗糙集已被廣泛用于屬性約簡[15]與規(guī)則提取[16]等多個領(lǐng)域。

由于超圖與覆蓋粗糙集均是建立在集合之上，因此本文將這兩者進行結(jié)合，利用覆蓋粗糙集研究超圖的連通性問題。首先，文章開頭將覆蓋近似空間與超圖聯(lián)系起來，有趣的是由不含孤立點的無向簡單超圖的頂點集與邊集組成的有序數(shù)組構(gòu)成一個覆蓋近似空間。其次，在此覆蓋近似空間上利用覆蓋近似算子和次覆蓋上近似算子給出了連通超圖的幾個等價刻畫。

本文的段落安排如下：第二節(jié)回顧了覆蓋粗糙集與超圖的一些基本概念；第三節(jié)為主要內(nèi)容，給出了連通超圖的幾個等價刻畫；第四節(jié)對本文進行總結(jié)并提出下一步研究的方向。

1 預(yù)備知識

為了便于討論，本節(jié)回顧有關(guān)于覆蓋粗糙集及超圖的一些基本概念。

1.1 覆蓋粗糙集

作為劃分的推廣，覆蓋更具普遍性和試用性。本小節(jié)首先介紹覆蓋的定義。

在覆蓋近似空間中，覆蓋上下近似是該空間中的兩個核心的概念。

緊接著，下述命題給出了上近似算子的一些性質(zhì)。對應(yīng)的關(guān)于下近似算子的性質(zhì)可根據(jù)對偶性得到。

1.2 超圖

超圖是模擬數(shù)據(jù)之間相關(guān)性的一種離散結(jié)構(gòu)。理論上，超圖的定義如下：

超圖中的邊可以是有向的或者無向的。若是所有的邊均是無向的，則稱此超圖為無向超圖。在此情況下，對于超圖中的任意兩個頂點（可相同），如果存在一條超邊包含它們，則稱這兩個頂點是相鄰的。孤立點是指那些不與中任意點（包含該點本身）相鄰的點，即設(shè),若，則稱為的孤立點。

圖1 例1中的超圖

2 主要內(nèi)容

本節(jié)將利用覆蓋粗糙集研究超圖的連通問題。首先我們建立起超圖與覆蓋之間的關(guān)系。

根據(jù)超圖的定義，不難將超圖的定義與覆蓋近似空間聯(lián)系起來。事實上只需要求超圖不含孤立點，那么這兩個概念就可互相等價。

由此，若無特殊說明，下文所討論的是不含孤立點的簡單超圖的連通性問題。接下來的命題從邊集的角度刻畫了連通超圖的特征。

基于上述命題，我們從超圖的邊出發(fā)給出連通超圖的一個等價刻畫。

證：根據(jù)命題3和連通超圖的定義，定理得證。

事實上，根據(jù)定理1，我們也可以從覆蓋上近似算子的角度刻畫連通超圖。

根據(jù)對偶性，連通超圖也可以用覆蓋下近似的角度來刻畫。

…

證：結(jié)合連通分支的定義與命題4，定理得證。

如果一個超圖是連通的，那么它只含有一個連通分支，反之亦然。因此根據(jù)定理3便可給出連通超圖的另一個等價刻畫。

圖3 例3中的超圖

根據(jù)上述定理，便可得到以下推論。

3 結(jié)束語

本文從覆蓋粗糙集的角度討論了不含孤立點的無向簡單超圖的連通性。對于這一問題的研究主要從覆蓋近似算子和次覆蓋上近似算子這兩個方面出發(fā)。盡管本文對超圖的性質(zhì)進行了研究，但還是有許多值得研究的問題：

(1) 超圖的誕生是為了模擬更復(fù)雜的系統(tǒng)。當它用于模擬模糊二元或者多元關(guān)系的時候，此時的超圖就是模糊超圖。那么如何用模糊粗糙集來研究模糊超圖？

(2) 現(xiàn)實生活中不少問題可被抽象為有向超圖，如離散事件系統(tǒng)。在這類系統(tǒng)中連通性起著非常重要的作用。因此有向超圖的強連通性也是值得進一步的研究的課題。

[1] BERGE C. Hypergraphs-combinatorics of finite sets[M].North-Holland Mathematical Library, 1989.

[2] Ouali M O, Fohlin H, Srivastav A. An approximation algorithm for the partial vertex cover problem in hypergraphs[J]. Journal of Combinatorial Optimization.2016,31:846-864.

[3] Huang Y, Verbraeck A, Seck M. Graph transformation based simulation model generation[J]. Journal of Simulation.2016,doi:10.1057/jos.2015.21.

[4] Sen M K, Dasgupta U. Hyperrelations and generalized hypergraphs[J]. International Journal of Machine Learning and Cybernetics.2013,4:565-574.

[5] Alon N, Yuster R. On a hypergraph matching problem[J]. Graphs and Combinatorics. 2005, 21: 377-384.

[7] Pomykala J A. Approximation operations in approximation space[J].Bulletin of the Polish Academy of Sciences, Mathematics. 1987, 35: 653-662.

[8] Yao Y, Yao B. Covering based rough set approximations[J]. Information Sciences.2012, 200: 91–107.

[9] Zhang Y L, Li C Q, Lin M L, Lin Y J. Relationshipsbetween generalized rough sets based on covering and reflexive neighborhood system[J]. Information Sciences. 2015, 319: 56-67.

[10] Zhang Y L, Luo M K. On minimization of axiom sets characterizing covering-based approximation operators[J]. Information Sciences. 2011, 181: 3032-3042.

[11] Zhu W. Relationship between generalized rough sets based on binary relation and covering[J]. Information Sciences. 2009, 179: 210-225.

[12] Zhu W. Relationship among basic concepts in covering-based rough sets[J]. Information Sciences. 2009, 179: 2478-2486.

[13] Huang A P, Zhu W. Connectedness of graphs and its application to connected matroids through covering-based rough sets[J]. Soft Computing. 2016, 20(5): 1841-1851.

[14] Huang A P, Zhao H, Zhu W. Nullity-based matroid of rough sets and its application to attribute reduction[J]. Information Sciences. 2014, 263: 153-165.

[15] Min F, Zhu W. Attribute reduction of data with error ranges and test costs[J], Information Sciences. 2012, 211:48-67.

[16] Zhang B W, Min F, Ciucci D, Representative-based classification through covering-based neighborhood rough sets, Applied Intelligence, 2015: 1573-7497.

Connectedness of Hypergraphs ThroughCovering-Based Rough Sets

HUANG Aiping, Huang Fengying

(School of Information Science and Technoalogy, Xiamen University Tan KahKee College, Zhangzhou 363105, China)

As a generalization of graphs, hypergraph are widely used in data data mining. In this field, a data structure is usually designed in the form of hypergraph. In data mining, the data are usually presented in the form of covering and covering-based rough sets provide a systematic approach to this type of representation. In this paper, we study the connectedness of hypergraphs through covering-based rough sets. We present an approach to inducing a covering by a hypergraph and then study the connectedness of the hypergraph from the viewpoint of covering approximation operators. The results show that this paper provides a new approach to studying hypergraphs.

covering-based rough set, hypergraph, hypergraph connectedness

1672-9129(2016)02-0011-04

TP3

A

2016-09-07；

2016-09-27。

國家自然科學(xué)基金 61379098。

黃愛萍(1988－)，女，碩士，講師，主要研究方向：數(shù)據(jù)挖掘，粗糙集，擬陣 (sxxhap@163.com)；黃鳳英(1989－)，女，碩士，講師，主要研究方向：數(shù)據(jù)分析，物聯(lián)網(wǎng)。

(*通訊作者電子郵箱：sxxhap@163.com)