The Connectivity of the Covering Approximation Space

Abstract

As a covering approximation space, its connectivity directly reflects a relationship, which plays an important role in data mining, among elements on the universe. In this paper, we study the connectivity of a covering approximation space and give its connected component. Especially, we give three methods to judge whether a covering approximation space is connected or not. Firstly, the conception of the maximization of a family of sets is given. Particularly, we find that a covering and its maximization have the same connectivity. Second, we investigate the connectivity of special covering approximation spaces. Finally, we give three methods of judging the connectivity of a covering approximation space from the viewpoint of matrix, graph and a new covering.

1 Introduction

At the Internet age, data collected and stored are enormous and inexact. Then, there are many puzzles in data intelligence processing, such as how to take effective ways to cope with the uncertainty of ubiquitous information. So how to solve such bottleneck problem becomes an important issue in computer science and industry. In order to deal with this issue, researchers have developed many techniques such as rough set theory [9], fuzzy set theory [21], computing with words [13], and granular computing [8].

Rough set theory was proposed by Pawlak [10] in 1982 as a tool for dealing with the vagueness and granularity in information system. It is built on equivalence relation [11]. However, the data in powerful computer systems and storage media are complex and redundant in the information-based society. Thus equivalence relation imposes restrictions and limitations on many practical applications. Therefore, Pawlak’s rough sets has been extended to the covering-based rough set theory [22, 23], relation-based rough sets [12, 19, 20], fuzzy rough sets [3, 18]. That is to say, Pawlak’s approximation space is extended to generalization approximation space.

However, covering approximation space is a class of generalization approximation space. In addition, covering is a common data structure and is used to describe overlapping information blocks in information systems. Therefore, it is important to investigate the covering approximation space. For a covering approximation space $(U, \mathcal {C})$, where U is a universe and $\mathcal {C}$ is a covering of U, it is called connected if x is connected to y for each pair x, y $\in$ U, namely, there exist $K_{1}$, $K_{2}$, $\cdots$, $K_{n}$ $\in$ $\mathcal {C}$ such that x $\in$ $K_{1}$, y $\in$ $K_{n}$ and $K_{i}$ $\cap$ $K_{i+1}$ $\ne$ $\emptyset$, for any x, y $\in$ U, $i =1, 2, \cdots , n$. That is to say, the relationship between elements of universe relates to connectivity of this covering approximation space.

In this paper, we mainly investigate the connectivity of the covering approximation space and give three methods to judge its connectivity in terms of matrix, graph and a new covering. In order to study expediently, we firstly give a new covering, namely, the maximization of a covering. Particularly, a covering and its maximization are proved to have the same connectivity. So we study the connectivity of a covering approximation space through maximization of this covering. Second, we explore the connectivity of some special covering approximation spaces. Finally, we give three approaches to judge the connectivity of a covering approximation space by matrix, graph and a new covering. It is the core of this paper.

The remainder of this paper is organized as follows. In Sect. 2, we review some basic definitions and related conclusions about covering approximation space and graph theory. The conception of maximization of a covering and its properties are given in Sect. 3. Section 4 studies the connectivity of the special covering approximation spaces. The most important work is Sect. 5. This section gives three methods to judge the connectivity of a covering approximation space. Finally, we conclude this paper in Sect. 6.

2 Preliminaries

Covering is often used to describe overlapping information blocks in information systems. Graph theory is an intuitive and visible mathematical model. In this section, we introduce the basic definitions and related results about covering and graph theory.

2.1 Covering Approximation Space

In this subsection, we give the basic concepts of the covering approximation space.

Definition 1

(Covering [2]). Let U be a universe of discourse, $\mathcal {C}$ a family of subsets of U. If $\mathcal {C}$ is a family of nonempty subsets of U, and $\cup \mathcal {C}$ $= U$, $\mathcal {C}$ is called a covering of U.

Definition 2

(Covering approximation space [2]). Let U be a nonempty set, $\mathcal {C}$ a covering of U. The pair $(U, \mathcal {C})$ is called a covering approximation space.

The minimal description is an important concept in a covering approximation space.

Definition 3

(Minimal description [24]). Let $(U, \mathcal {C})$ be a covering approximation space and $x \in U$. The family of sets $Md_{\mathcal {C}}(x)$ $=$ $\{C$ $\in$ $\mathcal {C}$ | x $\in C$ $\wedge$ $(\forall$ S $\in$ $\mathcal {C}$ $\wedge$ x $\in$ S $\wedge$ S $\subseteq$ C $\Rightarrow$ C $=$ $S)\}$ is called the minimal description of x. When there is no confusion, we omit the subscript $\mathcal {C}$.

In the same way, we give the definition of maximal description.

Definition 4

(Maximal description [14]). Let $(U, \mathcal {C})$ be a covering approximation space and x $\in$ U. The family of sets $Maxd_{\mathcal {C}}(x)$ $=$ $\{C$ $\in$ $\mathcal {C}$ | x $\in$ C $\wedge$ $(\forall$ S $\in$ $\mathcal {C}$ $\wedge$ C $\subseteq$ S $\Rightarrow$ C $=$ $S)\}$ is called the maximal description of x. When there is no confusion, we omit the subscript $\mathcal {C}$.

In the following definitions, we introduce two types of coverings.

Definition 5

(Unary [25]). $\mathcal {C}$ is unary if |Md(x)| $= 1$ for all $x \in U$.

Definition 6

(Pointwise-covered [25]). $\mathcal {C}$ is called a pointwise-covered covering, if for any K $\in$ $\mathcal {C}$ and x $\in$ K,  K $\subseteq$ $\cup$ Md(x).

The connectivity of covering approximation space has been used in medical diagnosis [5]. We will introduce the connected covering approximation space.

Definition 7

[5]. Let $(U, \mathcal {C})$ be a covering approximation space.

(1) Let x, y $\in U$. x is called to be connected to y if there are $K_{1}$, $K_{2}$, $\cdots$, $K_{n} \in \mathcal {C}$ such that $x \in K_{1}$, $y \in K_{n}$ and $K_{i} \cap K_{i+1} \ne \emptyset$ for each $i = 1, 2,\cdots , n - 1$.

(2) $(U, \mathcal {C})$ is called connected if x is connected to y for each pair $x, y \in U$.

2.2 Graph Theory

Graph is an important tool at the area of mathematics. It has been employed to find rough set reducts [6]. In this subsection, we present the basic concepts of graph theory.

Definition 8

(Graph [17]). A set of elements and a relation between them is called a graph. Specifically, graph is a pair (V,  E), there V is called the vertex set of the graph, E is a unordered pair from the element of V, is called the edge set of the graph. We say that $G'$ $=$ $(V'$, $E')$ is a subgraph of G $=$ (V, E) if $V'$ $\subset$ V and $E'$ $\subset$ E.

Definition 9

 [1]. (1) Chain(Walk): Let u and v are two vertexes of the graph. The chain of the graph is a series of finite vertexes and edges $u_{0}$ $e_{1}$ $u_{1}$ $\cdots$ $u_{n-1}$ $e_{n}$ $u_{n}$ $(u=u_{0}$, $v=u_{n})$, is called $u-v$ chain, where $u_{i-1}$ and $u_{i}$, are placed adjacent to $e_{i}(1\le i\le n)$, are two endpoint of the $e_{i}$.

(2) Path: The chain is called a path, if the internal point of chain is different.

(3) Connected graph: If there is a path between u and v, there u and v are two different vertexes of the graph, then the graph is connected, otherwise, the graph is not connected. The maximum connected subgraph is called a connected component.

Definition 10

(Bigraph [17]). A bigraph (or bipartite graph) $G = (V, E)$ is a graph whose vertices can be divided into two disjoint sets $V_{1}$ and $V_{2}$ such that every edge connects a vertex in $V_{1}$ to one in $V_{2}$. We often use G $=$ $(V_{1}$ $\cup$ $V_{2}$, E) to denote a bigraph.

3 Maximization of a Covering

Let $\mathcal {C}$ be a family of sets on universe U. If there exist two elements $K_{1}$, $K_{2}$ of $\mathcal {C}$, such that $K_{1}$ is a subset of $K_{2}$, then we omit $K_{1}$, and so on. Like that, we can get some new sets $\mathcal {C}'$. Then the elements of $\mathcal {C}'$ do not have this containment relationships. We call $\mathcal {C}'$ the maximization of $\mathcal {C}$. First, we give a symbol of set theory [7].

Let U be a finite universe and $\mathcal {A}$ be a family of subsets of U. Then

$Max(\mathcal {A})$ $=$ $\{X$ $\in$ $\mathcal {A}|$ For all Y $\in$ $\mathcal {A}$. If X $\subseteq$ Y, then X $=$ $Y\}$.

Definition 11

(Maximization of sets). Let $\mathcal {C}$ be a set of sets. $\mathcal {C}'$ is called the maximization of $\mathcal {C}$ if $\mathcal {C}'$ $=$ $Max(\mathcal {C})$.

Example 1

Let $\mathcal {C}$ $=${$\{a$, c, $d\}$, $\{a$, $b\}$, $\{c$, $d\}$, $\{f$, d, $b\}$, $\{a$, b, $f\}\}$ be a family of sets. Then the maximization of $\mathcal {C}$ is that $\mathcal {C}'$ $=${$\{a$, c, $d\}$ $\{f$, d, $b\}$, $\{a$, b, $f\}\}$.

If a family of sets are a covering on the universe U, then the maximization of these sets is still a covering.

Proposition 1

Let $\mathcal {C}$ $=$ $\{K_{1}$, $K_{2}$, $\cdots$, $K_{n}\}$ be a covering of the universe U and $\mathcal {C}'$ the maximization of $\mathcal {C}$. Then $\mathcal {C}'$ is also a covering of U.

Proof

Since $\mathcal {C}$ is a covering of U,  then $K_{i}$ $\ne$ $\emptyset$ $(i = 1$, 2, $\cdots$, n) and $\overset{n}{\underset{i=1}{\bigcup }}K_{i}$ $=$ U. According to Definition 11, K $\ne$ $\emptyset$, $\forall$ K $\in$ $\mathcal {C'}$. Since $\forall$ $K_{i}$ $\in$ $\mathcal {C}$ there must exist $K_{j}$ $\in$ $\mathcal {C'}$, such that $K_{i}$ $\subseteq$ $K_{j}$, so $U =$ $\overset{n}{\underset{i=1}{\bigcup }}K_{i}$ $\subseteq$ $\underset{j \in I}{\bigcup }$ $K_{j}$, and $\underset{j \in I}{\bigcup }K_{j}$ $\subseteq U$, then $\underset{j \in I}{\bigcup }$ $K_{j}$ $=$ U. Therefore $\mathcal {C'}$ is a covering of U.

The following proposition indicates that the process of maximizing can not change the connectivity of the covering approximation space.

Proposition 2

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}'$ the maximization of $\mathcal {C}$. $(U, \mathcal {C})$ is connected if and only if $(U, \mathcal {C'})$ is connected.

Proof

$\Rightarrow ):$ If $(U, \mathcal {C})$ is connected, then for any x, y $\in$ U, $\exists$ $K_{1}$, $\cdots$, $K_{m}$ $\in$ $\mathcal {C}$ such that $x \in K_{1},$ $y \in K_{m}$ and $K_{i}$ $\cap$ $K_{i+1} \ne \emptyset$ $(i = 1, 2, \cdots , m)$. Since $\mathcal {C}'$ the maximization of $\mathcal {C}$, thus there must exist $K_{1}',$ $\cdots ,$ $K_{m}'$ $\in$ $\mathcal {C'}$ such that $K_{i}$ $\subseteq$ $K_{i}'$. Therefore $x \in K_{1}$ $\subseteq$ $K_{1}',$ $y \in$ $K_{m}$ $\subseteq K_{m}'$ for any x, y $\in U$, and $K_{i}'$ $\cap$ $K_{i+1}'$ $\supseteq$ $K_{i}$ $\cap$ $K_{i+1}$ $\ne$ $\emptyset$. That is to say $(U, \mathcal {C'})$ is connected.

$\Leftarrow ):$ It is straightforward.

Proposition 3

Let $\mathcal {C}$ be a covering of the universe U and $\mathcal {C}'$ the maximization of $\mathcal {C}$. Then $Maxd_{\mathcal {C}}(x)$ $=$ $Maxd_{\mathcal {C'}}(x)$ for all x $\in$ U.

Proof

On one hand, for any K $\in$ $Maxd_{\mathcal {C}}(x)$, then x $\in$ K and $\forall$ S $\in$ $\mathcal {C}$, x $\in$ S $\wedge$ K $\subseteq S$ $\Rightarrow$ S $=$ K, thus K $\in$ $\mathcal {C'}$. According to Definition 11, S $\not$ $\subseteq$ K for all S $\in$ $\mathcal {C'}$. Therefore, K $\in$ $Maxd_{\mathcal {C'}}(x)$ i.e. $Maxd_{\mathcal {C}}(x)$ $\subseteq$ $Maxd_{\mathcal {C'}}(x)$. On the other hand, $\forall K'$ $\in$ $Maxd_{\mathcal {C'}}(x)$, then $\forall$ S $\in$ $\mathcal {C}$, x $\in$ S $\wedge$ $K'$ $\subseteq S$ $\Rightarrow$ S $=$ $K'$ based on Definition 11, that is to say $K'$ $\in$ $Maxd_{\mathcal {C}}(x)$, i.e. $Maxd_{\mathcal {C}}(x)$ $\supseteq$ $Maxd_{\mathcal {C'}}(x)$. To sum up, $Maxd_{\mathcal {C}}(x)$ $=$ $Maxd_{\mathcal {C'}}(x)$.

Proposition 4

Let $\mathcal {C}$ be a covering of the universe U and $\mathcal {C}'$ the maximization of $\mathcal {C}$. Then $Md_{\mathcal {C'}}(x)$ $=$ $Maxd_{\mathcal {C'}}(x)$.

Proof

$\forall K_{1},$ $K_{2} \in \mathcal {C}'$, if $K_{1}$ $\ne K_{2},$ then $K_{1}$ $\not \subseteq K_{2},$ hence $Md_{\mathcal {C'}}(x)$ $=$ $Maxd_{\mathcal {C'}}(x)$.

4 The Connectivity of Covering Approximation Space

The connected covering approximation space has been used in medical diagnosis [5]. Therefore, it is important and necessary to study the connectivity of a covering approximation space.

Proposition 5

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}'$ the maximization of $\mathcal {C}$. If $\mathcal {C'}$ is unary on U and $\mathcal {C}'$ $\ne$ $\{U\}$, then $(U, \mathcal {C})$ is not connected.

Proof

We only need to prove that $(U, \mathcal {C'})$ is not connected based on Proposition 2. If $\mathcal {C'}$ is unary on U and $\mathcal {C}'$ $\ne \{U\}$, then for all $x \in U,$ |Md(x)| $=$ 1. Thus we suppose $(U, \mathcal {C'})$ is connected, then $\forall x, y \in U$, there exists $K_{1},$ $\cdots ,$ $K_{m}$ $\in \mathcal {C'}$ such that $x \in K_{1},$ $y \in K_{m}$ and $K_{i} \cap K_{i+1} \ne \emptyset$ (1 $\le$ i $\le$ $m-1)$. Let $x'$ $\in$ $K_{1}$ $\cap$ $K_{2}$, thus $|Md(x')|$ $=$ 2. It is contradictory with |Md(x)| $=$ 1 for all $x \in U$. Therefore $(U, \mathcal {C'})$ is not connected. That is to say $(U, \mathcal {C})$ is not connected.

We only suppose that $\mathcal {C}'$ $\ne \{U\}$ in the Proposition 5. It is because that $\mathcal {C}'$ is connected when $\mathcal {C}'$ $= \{U\}$.

Proposition 6

Let $(U, \mathcal {C})$ be a covering approximation space. If $\mathcal {C'}$ is unary on U, then U|Md(x) $(x \in U)$ is a connected component of $(U, \mathcal {C})$.

Proof

Since $\mathcal {C'}$ is unary, then Md(x) $=$ Md(y) for any y $\in$ Md(x), thus $x \sim y$, and if $z \in$ $U - Md(x)$, then Md(x) $\cap$ Md(z) $=$ $\emptyset$, so $x \not \sim z$. That is to say U|Md(x) $(x \in U)$ is a connected component of $(U, \mathcal {C})$.

Proposition 7

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}'$ the maximization of $\mathcal {C}$. If $\mathcal {C'}$ is a partition on U and $\mathcal {C}'$ $\ne$ $\{U\}$, then $(U, \mathcal {C})$ is not connected.

Proof

Since $\mathcal {C'}$ is a partition, thus $\forall$ $K_{1}$, $K_{2}$ $\in$ $\mathcal {C}'$, $K_{1}$ $\cap$ $K_{2}$ $= \emptyset$, then x $\not \sim$ y, for any $x \in K_{1}$, $y \in K_{2}$. Therefore $(U, \mathcal {C})$ is not connected.

Proposition 8

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}'$ the maximization of $\mathcal {C}$. If $\mathcal {C'}$ $= \{K_{1}, \cdots , K_{m}\}$ is a partition, then $U|K_{i} (i=1, 2, \cdots , m)$ is connected component of $(U, \mathcal {C})$.

Proposition 9

Let $(U, \mathcal {C})$, a covering approximation space, be connected and $\mathcal {C}'$ the maximization of $\mathcal {C}$. Then there exists $x \in K$ for all $K \in \mathcal {C'}$, such that $|Md_{\mathcal {C'}}(x)|> 1$.

Proof

If $(U, \mathcal {C'})$ is connected, then we suppose that $|Md_{\mathcal {C'}}(x)|$ $= 1$ for all $x \in K$. Since $Md_{\mathcal {C'}}$ $=$ $Maxd_{\mathcal {C'}}$, hence $\forall$ $x \in K$, $\forall$ $y \in U - K$, thus x is not connected y, which is contradictory with $(U, \mathcal {C'})$ is connected. Therefore, there must exist $x \in K$ for all $K \in \mathcal {C'}$, such that $|Md_{\mathcal {C'}}(x)|$ $> 1$.

The reverse of Proposition 9 may not hold from the following a counterexample.

Example 2

Let $U = \{a, b, c, d, e, f\}$ be a universe and $K_{1}$ $=$ $\{a,$ $b\},$ $K_{2}$ $=$ $\{b,$ $c\},$ $K_{3}$ $=$ $\{f,$ $d\},$ $K_{4}$ $=$ $\{d,$ $e\},$ $\mathcal {C}$ $=$ $\{K_{1}$, $K_{2}$, $K_{3}$, $K_{4}\}$. There exist b $\in$ $K_{1}$, $K_{2}$ such that $|Md(b)| > 1$, and $d \in K_{3}, K_{4}$ such that $|Md(d)| > 1$, but $(U, \mathcal {C})$ is not connected.

5 Methods of Judging the Connectivity of a Covering Approximation Space

As a general covering approximation space, what we care is whether it is connected or not. In this section, we will explore the connectivity of the covering approximation space from the viewpoint of matrix, graph and a new covering.

5.1 From the Matrix Perspective

First,we give the matrix relating to the covering approximation space.

Definition 12

 [15] Let $(U, \mathcal {C})$ be a covering approximation space and $U =$ $\{u_{1}$, $u_{2}$, $\cdots$, $u_{n}\}$, $\mathcal {C}$ $=\{K_{1}$, $K_{2}$, $\cdots$, $K_{m}\}$. We define a matrix $A= (a_{ij})_{m\times n}$ as follows:

$a_{ij} =$ $\left\{ \begin{array}{ll} 1, &{} {u_{j} \in K_{i},} \\ 0, &{} {u_{j} \notin K_{i},} \end{array} \right.$

where $i = 1, 2, \cdots , m$; $j = 1, 2, \cdots , n$. Using $u_{j}$ labels the jth column and $K_{i}$ labels the ith row. A is called a matrix induced by $\mathcal {C}$.

Example 3

Let $U = \{a, b, c, d\}$ be a universe. $K_{1}$ $=$ $\{a, b\},$ $K_{2}$ $=$ $\{a,$ c,  $d\},$ $K_{3}$ $= \{b, c\},$ $K_{4}$ $= \{b, d\},$ $K_{5}$ $= \{c, d\},$ $\mathcal {C} = \{K_{1}, K_{2}, K_{3}, K_{4}, K_{5}\}$. Then $\mathcal {C'} \, = \, \{K_{1}, K_{2}, K_{3}, K_{4}\}$, hence the matrix $A_{ij}$ as follows:

$A_{ij} = \left( \begin{array}{cccc} 1 &{} ~~1 &{} ~~0 &{} ~~0 \\ 1 &{} ~~0 &{} ~~1 &{} ~~1 \\ 0 &{} ~~1 &{} ~~1 &{} ~~0 \\ 0 &{} ~~1 &{} ~~0 &{} ~~1 \\ \end{array} \right)$

If we denote all column vectors of the A as $\mathcal {A}$ $=$ $\{\alpha _{1}$, $\alpha _{2}$, $\cdots$, $\alpha _{n}\}$, then a family of vectors $\mathcal {A}$ can be regard as being composed of column vectors $\alpha _{j}(j = 1, 2, \cdots , n)$.

Remark 1

Let $\alpha _{j}$ $=$ $(a_{1j}$, $a_{2j}$, $\cdots$, $a_{mj})^{\top }$ be a column vector. Then we denote by $\Vert \alpha _{j}\Vert$ $=$ $a_{1j}$ $+$ $a_{2j}$ $+$ $\cdots$ $+$ $a_{mj}$, where j $=$ 1, 2, $\cdots$, n.

Definition 13

Let A be a matrix induced by $\mathcal {C}$ and $\mathcal {A}$ a set of all column vectors of A. Then we denote the maximization of the $\mathcal {A}$ by $\mathcal {A}_{max}$ as follows:

$\mathcal {A}_{max}$ $=$ $\{\alpha _{i}$ $\in$ $\mathcal {A}:$ $\forall$ $\alpha _{j}$ $\in$ $\mathcal {A}$, $\Vert \alpha _{i}\Vert$ $\ge$ $\Vert \alpha _{j}\Vert \}.$

Example 4

(Continued from Example 3). $\mathcal {A}_{max}$ $=$ $\{$ $\alpha _{2}$ $\}$, where $\alpha _{2}=$ $\left( \begin{array}{cccc} 1&0&1&1 \end{array} \right)$ $^{\top }$.

We take any one from $\mathcal {A}_{max}$, denoted as $\alpha$. If a row of $\alpha$ is 1, then we omit column vectors whose values are 1 in the same row with $\alpha$ and the vectors we have omitted until there do not exist column vectors such that their values are 1 in the same row.

Example 5

(Continued from Example 3).

Since $\Vert \alpha _{2}\Vert$ is the maximization of $\Vert \alpha _{i}\Vert (i = 1, \cdots , 4)$, hence we regard $\alpha _{2}$ as $\alpha$. Thus the first row of $\alpha$ is 1, so we omit $\alpha _{1}$ whose the first row is 1. Because the values of $\alpha _{3},$ $\alpha _{4}$ and $\alpha _{1}$ are 1 in the second row, we also omit $\alpha _{3},$ $\alpha _{4}$.

Definition 14

Let $(U, \mathcal {C})$ be a covering approximation space and A be a matrix induced by $\mathcal {C}$. The new matrix through the above process is called the simplification of A, denoted by Simp(A).

Proposition 10

Let $(U, \mathcal {C})$ be a covering approximation space, A be a matrix induced by $\mathcal {C}$ and $N_{(U, \mathcal {C})}$ the number of connected component of $(U, \mathcal {C})$. We denote the number of column vector of Simp(A) by $N_{Simp(A)}$, then $N_{(U, \mathcal {C})} =$ $N_{Simp(A)}$.

Proof

We suppose A $=$ $\left( \begin{array}{cccc} \alpha _{1} &{} \alpha _{2} &{} \cdots &{} \alpha _{n} \\ \end{array} \right)$, Simp(A) $=$ $\left( \begin{array}{cccc} \alpha _{1} &{} \alpha _{2} &{} \cdots &{} \alpha _{m} \\ \end{array} \right)$, $(m \le n)$. On one hand, for any $\alpha _{i}(1 \le i \le n, i \ne 1, \cdots , m)$ there exist $\alpha _{j}(j = 1, \cdots , m)$ such that $\alpha _{i}, \alpha _{j}$ have the same 1 in the same row, that is to say $a_{i} \sim a_{j}$ based on Definition 12. On the other hand, for any $\alpha _{l}, \alpha _{k}$ $(l, k = 1, \cdots , m)$, then $a_{l} \not \sim a_{k}$ based on Definition 14 and Definition 12. Therefore $N_{(U, \mathcal {C})} =$ $N_{Simp(A)}$.

Proposition 11

Let $(U, \mathcal {C})$ be a covering approximation space, A be a matrix induced by $\mathcal {C}$. Then Simp(A) only has one column vector if and only if $(U, \mathcal {C})$ is connected.

5.2 From the Graph Perspective

The following proposition is straightforward from the bigraph perspective [16].

Proposition 12

Let $(U, \mathcal {C})$ be a covering approximation space and G a bigraph induced by $\mathcal {C}$. $(U, \mathcal {C})$ is connected if and only if G is connected.

The above proposition gives a useful way to judge the connectivity of a covering approximation space. We will introduce another method through a general graph.

Definition 15

(Graph induced by $K_{i})$ . Let $\mathcal {C}$ $=$ $\{K_{1}$, $K_{2}$, $\cdots$, $K_{m}\}$ be a covering. We define the graph $G(K_{i})$ $=$ (V, E) induced by $K_{i}$ $=$ $\{x_{1}$, $x_{2}$, $\cdots$, $x_{l}\}$ $(i=1$, $\cdots$, m) as follows:

(1) V $=$ $\{v_{K_{i}}$, $v_{K_{i}}'\}$;

(2) E $=$ $\{x_{1}$, $x_{2}$, $\cdots$, $x_{l}\},$ where $x_{j}$ connects $v_{K_{i}}$ with $v_{K_{i}}',$ $j = 1, 2, \cdots , l$.

Example 6

Let $K =$ $\{u_{1}, u_{2}, u_{3}, u_{4}\}$, then the graph induced by K as shown in Fig. 1:

Fig. 1.

The graph induced by K.

Remark 2

Let $G_{1} = (V_{1}, E_{1})$, $G_{2} = (V_{2}, E_{2})$ be two graphs induced by $K_{1}$, $K_{2}$ respectively, where $V_{1} = \{v_{K_{1}}, v_{K_{1}}'\}$, $V_{2} = \{v_{K_{2}}, v_{K_{2}}'\}$. If $K_{1} \cap K_{2} \ne \emptyset$, then we denote as $v_{K_{1}}$ $=$ $v_{K_{2}}$ and $v_{K_{1}}'$ $=$ $v_{K_{2}}'$.

Definition 16

(Graph union [4]). Let $G(K_{1})$ $=$ $(V_{1},$ $E_{1}),$ $G(K_{2})$ $=$ $(V_{2},$ $E_{2})$ be two graphs induced by $K_{1}$ and $K_{2}.$ Then the union of $G(K_{1})$ and $G(K_{2})$ is defined as a graph $(V_{1}$ $+$ $V_{2},$ $E_{1}$ $+$ $E_{2}),$ denoted by $G(K_{1})$ $\cup$ $G(K_{2})$.

It is clearly that a covering approximation space can induce a graph from the following definition.

Definition 17

Let $(U, \mathcal {C})$ be a covering approximation space. The graph induced by $\mathcal {C}$ is called the graph induced by $(U, \mathcal {C})$, denoted by $G(\mathcal {C})$.

Example 7

Let $(U, \mathcal {C})$ be a covering approximation space and $U =$ $\{u_{1},$ $u_{2},$ $u_{3},$ $u_{4},$ $u_{5}\}$, $\mathcal {C}$ $=$ $\{\{u_{1}$, $u_{3}\},$ $\{u_{3},$ $u_{5}\},$ $\{u_{2},$ $u_{4}\}\}$. Then the graph induced by $\mathcal {C}$ as shown in the Fig. 2:

Proposition 13

Let $(U, \mathcal {C})$ be a covering approximation space and $G(\mathcal {C})$ a graph induced by $\mathcal {C}$. $G(\mathcal {C})$ is connected if and only if $(U, \mathcal {C})$ is connected.

Proof

It is straightforward based on the Definitions 15 and 16 and Remark 2.

Proposition 14

Let $(U, \mathcal {C})$ be a covering approximation space and $G(\mathcal {C})$ a graph induced by $\mathcal {C}$. Then the numbers of connected component of (U, $\mathcal {C})$ and the graph $G(\mathcal {C})$ are equal.

Fig. 2.

The graph induced by $\mathcal {C}$.

Example 8

(Continued from Example 7). Since the graph induced by $\mathcal {C}$ has two connected component from the Fig. 2, thus $N_{(U, \mathcal {C})} = 2$.

5.3 From Covering Perspective

In the following discussion, we will continue to simplify a covering in terms of a covering for herself. First, we give the notion of friends of an element.

Definition 18

 [26]. Let $(U, \mathcal {C})$ be a covering approximation space. For any $x \in U$, $\cup \{K: x\in K \wedge K \in \mathcal {C}\}$ is called the friends of x, denoted by Friends(x).

According to Definition 18, it is clear that $\{Friends(x): x \in U\}$ is a covering on the U, we denote by $\mathcal {C}_{1}$. We already know that $\mathcal {C}_{1}'$ is also a covering and both of them have the same connectivity in Sect. 3. Now, for every element x on U, we can get the friends of x in the covering approximation space $(U, \mathcal {C}_{1}')$. Then $\{Friends(x):$ $x \in$ $U\}$ is also a covering, denoted by $\mathcal {C}_{2} = \{Friends(x): x \in U\}$, then we get $\mathcal {C}_{2}'$. Following it until we get a partition $\mathcal {C}_{N}'$.

Example 9

Let $(U, \mathcal {C})$ be a covering approximation space. $\mathcal {C}$ $=$ $\{ C_{1}$, $C_{2}$, $C_{3}\}$, $C_{1}$ $=$ $\{a, c\}$, $C_{2}$ $=$ $\{a$, b, $d\}$, $C_{3}$ $=$ $\{b, e, f\}$. Since Friends(a) $=$ $\{a$, b, c, $d\}$, Friends(b) $=$ $\{a$, b, d, $e, f\}$, Friends(c) $=$ $\{a$, $c\}$, Friends(d) $=$ $\{a$, b, $d\}$, Friends(e) $=$ Friends(f) $=$ $\{b$, e, $f\}$. Thus $\mathcal {C}_{1}'$ $=$ {$\{a$, b, c, $d\}$, $\{a$, b, d, e, $f\}\}$. In the same way, we get $\mathcal {C}_{2}$ $=$ $\{U$, $\{a$, b, c, $d\}$, $\{a$, b, d, e, $f\}\}$, then $\mathcal {C}_{2}'$ $=$ $\{U\}$.

If $\mathcal {C}_{N}'$ is a partition induced by above process, then this partition is called the simplification of $\mathcal {C}$. It is provided in the following Definition 19.

Definition 19

Let $(U, \mathcal {C})$ be a covering approximation space. If $\mathcal {C}_{N}'$ is a partition induced by above process, then we call $\mathcal {C}_{N}'$ is the simplification of $\mathcal {C}$, denote by $\mathcal {C}_{N}'$.

The notion of simplification of a covering can help us to judge the connectivity of a covering approximation space from the following proposition.

Proposition 15

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}_{N}'$ the simplification of $\mathcal {C}$. Then $(U, \mathcal {C})$ is connected if and only if $\mathcal {C}_{N}'$ $=$ $\{ U \}$.

Proof

It is straightforward based on the process of the simplification of a covering.

Proposition 16

Let $(U, \mathcal {C})$ be a covering approximation space and $\mathcal {C}_{N}'$ the simplification of $\mathcal {C}$. Then an equivalence classes of $\mathcal {C}_{N}'$ is a connected component of $(U, \mathcal {C})$.

Proof

We suppose $\mathcal {C}_{N}'$ $=$ $\{ K_{1}, \cdots , K_{m} \}$, then $K_{i} \cap K_{j} = \emptyset (i, j = 1, \cdots , m)$ based on Definition 19. According to the process of the simplification of a covering, there must exist a covering $\mathcal {C}_{n}'$ and $z \in U$ such that $x \in Md_{\mathcal {C}_{n}'}(z)$ and $y \in Md_{\mathcal {C}_{n}'}(z)$ for any $x, y \in K_{i}(i = 1, \cdots , m)$. Since $(U, \mathcal {C})$ and $(U, \mathcal {C}_{n}')$ have the same connectivity, thus $x \sim y$. On the other hand, for any $x \in K_{i}$ and $y \in K_{j} (i \ne j)$, since $K_{i} \cap K_{j} = \emptyset$, thus $x \not \sim y$. Therefore an equivalence classes of $\mathcal {C}_{N}'$ is a connected component of $(U, \mathcal {C})$.

6 Conclusions

In order to improve the high-efficiency in data mining, we have studied the connectivity of the covering approximation space and given three methods to judge its connectivity. First, we have given a conception of maximization of a family of sets, so the maximization of a covering has been given. Then we have investigated the relationship between covering and its maximization. Especially, we give that a covering and its maximization have the same connectivity. Second, we have studied the connectivity of special covering approximation spaces. Finally, we have given three methods to judge the connectivity of a covering approximation space with the aid of matrix, graph and a new covering.