The tree structure of a closed G-V fuzzy matroid

Abstract

In this paper, the judgment of fuzzy bases of a closed G-V fuzzy matroid is studied and a necessary and sufficient condition of judging fuzzy bases is presented. Based on the results, an intuitive tree structure of a closed G-V fuzzy matroid is proposed and some of its properties are obtained.

Keywords

Fuzzy sets matroids fuzzy matroids fuzzy bases tree structure

1 Introduction

The concept of fuzzy matroid was firstly introduced by Goetschel and Voxman (G-V fuzzy matroid for short) in [1]. Many correlative notions which extend those in crisp matroids have been introduced, such as fuzzy base, fuzzy circuit, fuzzy rank function, fuzzy dual matroid, fuzzy matroid sum, fuzzy matroid product, etc., and their properties have been also studied [2 –17].

Recently, Shi introduced a new approach for the fuzzification of matroids and presented the concept of an (L, M)-fuzzy matroid and then proved that a perfect [0,1]-matroid is equivalent to a G-V fuzzy matroid [18, 19]. Shi et al. also studied the bases axioms, circuits axioms and the rank functions of fuzzifying matroids or perfect [0, 1]-matroids [20 –22]. Xiu and Pang studied the base axioms and subbase axioms in M-fuzzifying convex spaces [23 –25]. Al-Hawary introduced the notions of fuzzy feasible sets and studied some fuzzy greedoid [26]. He also studied the properties of fuzzy regular-flats, fuzzy C-flats, fuzzy alternative-sets and furtherly introduced the notions of fuzzy C-matroids and fuzzy closure matroids which are new methods for the fuzzifying of matroids [27 –30].

However, so far, we don’t find any results of an intuitive structure of a G-V fuzzy matroid in the literature. For this purpose, an intuitive structure of a closed G-V fuzzy matroid has been considered in this paper. Through studying the judgment of fuzzy bases of a closed G-V fuzzy matroid, based on Theorem 2.2 in [9], we present a more precise necessary and sufficient condition for judging fuzzy bases. Combined with the conditions and some theories of Graph Theory [34], we propose an intuitive tree structure of a closed G-V fuzzy matroid and study its properties.

The contents are arranged as follows. In Section 2, some fundamental results are presented. In Section 3, the judgment of fuzzy bases is studied and a tree structure of a closed G-V fuzzy matroid and closed regular G-V fuzzy matroid are proposed, respectively. Finally, some properties of the tree structure are studied in Section 4.

2 Preliminaries

In this section, some fundamental notions and results on matroids, fuzzy sets, G-V fuzzy matroids and fuzzy bases based on G-V fuzzy matroids are introduced. Most of them are cited from [1–4 , 31–33].

Definition 2.1. Let E be a finite set and let I be a nonempty family of subsets of E satisfying:

φ ∈ I.

If X ∈ I, and Y ⊆ X, then Y ∈ I.

If X, Y ∈ I, and |X| < |Y|(where |X| denotes the cardinality of X), then there exists W ∈ I, such that X ⊂ W ⊆ X ∪ Y.

Then we call the pair M = (E, I) a (crisp) matroid, I a system of independent sets on E. For each subset X ⊆ E is called an independent set of M if X ∈ I, otherwise, X is called a dependent set of M. Any member of I that has maximal cardinality is called a basis of M. That is B is a basis of M if B ∈ I, but there isn’t a B′ ⊃ B, such that B′ ∈ I.

The following notation will be used in this paper.

If E is a finite set, then a fuzzy set μ on E is a mapping μ : E → [0, 1]. We denote the family of all fuzzy sets on E by F (E). If μ, ν ∈ F (E), then

supp μ = {x ∈ E|μ (x) >0},

m (μ) = inf {μ (x) |x ∈ supp μ},

R⁺ (μ) = {μ (x) |μ (x) >0, ∀ x ∈ E},

C_r (μ) = {x ∈ E|μ (x) ≥ r}, where r ∈ [0, 1],

μ ∨ ν = max {μ, ν}, μ ∧ ν = min {μ, ν}.

If μ, ν ∈ F (E), then we write μ ≤ ν if μ (x) ≤ ν (x) for each x ∈ E.

We write μ < ν if (1) μ ≤ ν; (2) μ (x) < ν (x) for some x ∈ E.

If E is a finite set, we denote the “cardinality” of a fuzzy set μ ∈ F (E) by |μ| = ∑_x∈Eμ (x). We say that μ is an elementary fuzzy set if |R⁺ (μ) | = 1.

Definition 2.2. Let E be a finite set and that ψ ⊆ F (E) is a nonempty family of fuzzy sets satisfying:

(Fψ1) If μ ∈ ψ, ν ∈ F (E), and μ < ν, then ν ∈ ψ.

(Fψ2) If μ, ν ∈ ψ and |supp μ|< | supp ν|, then there exists ω ∈ ψ such that

μ < ω ≤ μ ∨ ν.

m (ω) ⩾ min {m (μ), m (ν)}.

Then the pair M = (E, ψ) is called a G-V fuzzy matroid on E, and ψ the family of independent fuzzy sets of M. Let μ ∈ F (E), we say that μ is an independent fuzzy set of M if μ ∈ ψ, otherwise, μ is a dependent fuzzy set of M. A fuzzy basis of M is a maximal member μ in ψ(where μ is said to be maximal in ψ if whenever ν ∈ ψ and μ ≤ ν then μ = ν).

Remark 2.1. Let M = (E, ψ) is a G-V fuzzy matroid.

For each r, 0 < r ≤ 1, let M_r = (E, I_r) be a crisp matroid on E(where I_r = {C_r (μ) | ∀ μ ∈ ψ}). Since E is a finite set, there is at most a finite number of matroids that can be defined on E. Thus there is a finite sequence 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1 such that

I_s ≠ φ, if 0 < s ≤ r_n; I_s = φ, if s > r_n.

If r_i < s, t < r_i+1, then I_s = I_t, i = 0, 1, ⋯, n - 1.

If r_i < s < r_i+1 < t < r_i+2, then I_t ⊂ I_s, i = 0, 1, ⋯, n - 2.

The sequence 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1 is called the fundamental sequence of M. For any i (i = 1, 2, ⋯, n), let ${\bar{r}}_{i} = \frac{1}{2} (r_{i - 1} + r_{i})$ , then the decreasing sequence of matroids $M_{\bar{r_{1}}} \supset M_{\bar{r_{2}}} \supset \dots \supset M_{\bar{r_{n}}}$ is called the M-induced matroid sequence of M = (E, ψ).

Suppose that 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1 is the fundamental sequence of M = (E, ψ). Then M is closed if I_r = I_{r
_i+1}(where I_r = {C_r (μ) | ∀ μ ∈ ψ}) whenever r_i < r ≤ r_i+1 (i = 1, 2, ⋯, n).

Suppose that 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1 is the fundamental sequence of M = (E, ψ). Let μ ∈ F (E). Then

M is closed if and only if for any μ ∈ ψ, there exists a basis ν ∈ ψ such that μ ≤ ν.

μ ∈ ψ if and only if for any β ∈ R⁺ (μ), we have C_β (μ) ∈ I_β.

If μ ∈ ψ is a basis of M, then R⁺ (μ) ⊆ {r₁, r₂, ⋯, r_n}, and for any r₁ ≤ r ≤ m (μ), we have C_r (μ) = C_m(μ) (μ) is a basis of (E, I_r).

Let E be a finite set, and let 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1 be a finite sequence. Suppose that (E, I_r
₁), (E, I_r
₂) …, (E, I_{r
_n}) is a sequence of matroids on E such that I_{r
_i-1} ⊃ I_{r
_i} (where i = 2, 3, ⋯, n). For each r, let I_r = I_{r
_i} if r_i-1 < r ≤ r_i(i = 1, 2, ⋯, n), and let I_r = φ if r_n < r ≤ 1.

Suppose further that ψ = {μ ∈ F (E) |C_r (μ) ∈ I_r, ∀r, 0 < r ≤ 1}, then M = (E, ψ) is a G-V closed fuzzy matroid and the M-induced matroid sequence is M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} (where for i = 1, 2, ⋯, n, M_{r
_i} = (E, I_{r
_i})).

Definition 2.3. Let M = (E, ψ) be a G-V fuzzy matroid with the fundamental sequence 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1. M = (E, ψ) is said to be regular if whenever r_i < r_j and B is a basis of M_{r
_i} = (E, I_{r
_i}), there is a basis A of M_{r
_j} = (E, I_{r
_j}) such that A ⊆ B.

Remark 2.2. (1) Let M = (E, ψ) be a G-V closed fuzzy matroid. M = (E, ψ) is a closed regular G-V fuzzy matroid if and only if all bases of M = (E, ψ) have the same cardinality.

(2) Let M = (E, ψ) be a closed regular G-V fuzzy matroid with the fundamental sequence 0 = r₀ < r₁ < r₂ < ⋯ < r_n ≤ 1. Let μ ∈ F (E). If μ is a fuzzy basis of M, then R⁺ (μ) = {r₁, r₂, ⋯, r_n}. Moreover, for any i (i = 1, 2, ⋯, n), C_{r
_i} (μ) is a basis of (E, I_{r
_i}).

3 The tree structure of a closed G-V fuzzy matroid

In this section, we study the relationship of the set B of all the fuzzy bases and the family ψ of independent fuzzy sets of G-V fuzzy matroids and present a more precise necessary and sufficient condition of judging fuzzy bases based on Theorem 2.2 in [9]. Furthermore, we propose a tree structure of closed G-V fuzzy matroids and that of closed regular G-V fuzzy matroids.

3.1 The judgment of fuzzy bases of a closed G-V fuzzy matroid

Theorem 3.1. Let M = (E, ψ) be a closed G-V fuzzy matroid on E. B ≠ φ is the set of all the fuzzy bases of M. Let ψ^* = {ν|ν ≤ μ and μ ∈ B}. Then ψ = ψ^*.

Proof. Suppose M = (E, ψ) is a closed G-V fuzzy matroid. Then by Remark 2.1 (3), for any ω ∈ ψ, there exists μ ∈ B such that ω ≤ μ. It follows that ω ∈ ψ^*. It implies that, ψ ⊆ ψ^*.

On the other hand, for any ω ∈ ψ^*, there exists μ ∈ B ⊆ ψ such that ω ≤ μ. It follows that ω ∈ ψ. So ψ^* ⊆ ψ.

Therefore, ψ = ψ^*.

Corollary 3.1. Let B₁ ≠ φ and B₂ ≠ φ is the set of all the fuzzy bases of M₁ = (E, ψ₁) and M₂ = (E, ψ₂). If B₁ = B₂, then $ψ_{1} = {ν | ν \leq μ, μ \in B_{1}} = {ν | ν \leq μ, μ \in B_{2}} = ψ_{2} .$

From Theorem 3.1 and Corollary 3.1, we can learn that the set of all the fuzzy bases of a closed G-V fuzzy matroid is uniquely determined. A necessary and sufficient condition of judging fuzzy bases is studied as follows.

Theorem 3.2. Let M = (E, ψ) be a closed G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1. Let μ ∈ F (E). Suppose that M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} is the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n). Then μ is a fuzzy basis of M if and only if μ satisfies:

The set A₁ = supp μ is a basis of matroid (E, I_{r
₁}).

There exists a sequence A₂, ⋯, A_n-1, A_n(A_i ∈ I_{r
_i}) which satisfies A₁ ⊇ A₂ ⊇ ⋯ ⊇ A_n-1 ⊇ A_n and A_i is a maximal subset of A_i-1(i = 2, 3, ⋯, n) such that μ (x) = r_n for any x ∈ A_n, and μ (x) = r_i for any x ∈ A_i ∖ A_i+1, i = 1, 2, ⋯, n - 1.

Proof. Necessity. Suppose that μ is a fuzzy basis of M = (E, ψ).

By Remark 2.1 (3), R⁺ (μ) ⊆ {r₁, r₂, ⋯, r_n} and A₁ = supp μ = C_m(μ) (μ) is a basis of matroid (E, I_{r
₁}).

Let A_i = C_{r
_i} (μ)(i = 2, 3, ⋯, n). Then C_{r
_i} (μ) ∈ I_{r
_i}. By the hypothesis, we have C_{r
₁} (μ) ⊇ C_{r
₂} (μ) ⊇ ⋯ ⊇ C_{r
_n-1} (μ) ⊇ C_{r
_n} (μ). It follows that A₁ ⊇ A₂ ⊇ ⋯ ⊇ A_n-1 ⊇ A_n.

Assume that there exists a set A_i in I_{r
_i} (i = 2, 3, ⋯, n) such that A_i is not a maximal subset of A_i-1 in I_{r
_i-1}. Then there exists a set B in I_{r
_i} such that B is a maximal subset of A_i-1 and B ⊃ A_i.

If i = 2, let $ω (x) = {\begin{matrix} r_{1}, & x \in A_{1} ∖ B \\ r_{2}, & x \in B ∖ A_{2} \\ μ (x), & x \in A_{2} \end{matrix},$ and if i = 3, 4, ⋯, n, let $ω (x) = {\begin{matrix} r_{j}, & x \in A_{j} ∖ A_{j + 1} (j = 1, 2, \dots, i - 2) \\ r_{i - 1}, & x \in A_{i - 1} ∖ B \\ r_{i}, & x \in B ∖ A_{i} \\ μ (x), & x \in A_{i} \end{matrix}$

Then μ < ω and C_{r
_i} (ω) = B ∈ I_{r
_i}. And for any j (j = 1, 2, ⋯, i - 1), there is C_{r
_j} (ω) = A_j ∈ I_{r
_j}, for any j (j = i + 1, i + 2, ⋯, n), there is C_{r
_j} (ω) = C_{r
_j} (μ) ∈ I_{r
_j}. Thus by Remark 2.1 (3), ω ∈ ψ, which contradicts that μ is a fuzzy basis of M.

Sufficiency. From the two conditions, it is obvious that R⁺ (μ) ⊆ {r₁, r₂, ⋯, r_n} and for any r_i ∈ R⁺ (μ), we have C_{r
_i} (μ) = A_i ∈ I_{r
_i}(i = 1, 2, ⋯, n). It follows that μ ∈ ψ.

Assume that μ is not a fuzzy basis of M. Since μ ∈ ψ, there exists a fuzzy basis ω of M such that μ < ω and m (μ) ≤ m (ω) and supp μ⊆ supp ω.

Case 1 supp μ = supp ω. Since ω is a fuzzy basis of M, then A₁ = supp μ = supp ω is a basis of matroid (E, I_{r
₁}). Because A₁ ⊇ A₂ ⊇ ⋯ ⊇ A_n-1 ⊇ A_n and A_i is a maximal subset of A_i-1(A_i ∈ I_{r
_i}, i = 2, 3, ⋯, n), by the Necessity, we have ω (x) = r_n for any x ∈ A_n and ω (x) = r_i for any x ∈ A_i ∖ A_i+1 (i = 1, 2, ⋯, n - 1). Then for any x ∈ supp μ = supp ω, we have μ (x) = ω (x), that is μ = ω, which contradicts the assumption that μ < ω.

Case 2 supp μ ⊂ supp ω. Since ω is a fuzzy basis of M, then C_m(ω) (ω) = supp ω is a basis of matroid (E, I_{r
₁}). From condition (1), C_m(μ) (μ) = supp μ is also a basis of matroid (E, I_{r
₁}). Then supp μ = supp ω, which is in contradiction with supp μ ⊂ supp ω.

Therefore, μ is a fuzzy basis of M.

From Theorem 3.2, we can easily obtain the following corollary.

Corollary 3.2. Let M = (E, ψ) be a closed regular G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1. Suppose further that M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} is the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n). Let μ ∈ F (E). Then μ is a fuzzy basis of M if and only if μ satisfies:

There exists a sequence A₁, A₂, ⋯, A_n-1, A_n which satisfies A₁ ⊇ A₂ ⊇ ⋯ ⊇ A_n-1 ⊇ A_n and A_i is a basis of M_{r
_i} = (E, I_{r
_i})(i = 1, 2, ⋯, n) such that μ (x) = r_n for any x ∈ A_n and μ (x) = r_i for any x ∈ A_i ∖ A_i+1, i = 1, 2, ⋯, n - 1.

3.2 The tree structure of a closed G-V fuzzy matroid

Based on Theorem 3.2, we propose a tree structure of a closed G-V fuzzy matroid as follows.

Let M = (E, ψ) be a closed G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1 and M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} is the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n).

Suppose that there are m bases in matroid M_{r
₁} = (E, I_{r
₁}). For any basis $A_{1}^{j}$ (j = 1, 2, ⋯, m) of matroid (E, I_{r
₁}), by Theorem 3.2, there exists a sequence $A_{2, 1}^{j}, \dots, A_{n - 1, 1}^{j}, A_{n, 1}^{j}$ $(A_{i, 1}^{j} \in I_{r_{i}}, i = 2, 3, \dots, n)$ satisfying $A_{i, 1}^{j}$ is a maximal subset of $A_{i - 1, 1}^{j}$ (i = 2, 3, ⋯, n) and $A_{1, 1}^{j} \supseteq A_{2, 1}^{j} \supseteq \dots \supseteq A_{n - 1, 1}^{j} \supseteq A_{n, 1}^{j}$ .

The sequence $A_{1}^{j}, A_{2, 1}^{j}, \dots, A_{n - 1, 1}^{j}, A_{n, 1}^{j}$ (called $A_{1}^{j}$ -induced set sequence, j = 1, 2, ⋯, m) can be constructed a branch of a tree. Because $A_{i, 1}^{j}$ is not the only maximal subset of $A_{i - 1, 1}^{j}$ (i = 2, 3, ⋯, n) in I_{r
_i}, there are many sequences induced by $A_{1}^{j}$ which can be constructed many branches of a tree. Thus we can construct a tree with those branches (Fig. 1). $A_{1}^{j}$ is called the root vertex of the tree and $A_{i - 1, 1}^{j}$ (i = 2, 3, ⋯, n) are called the branch vertexes of the tree. $A_{n, k}^{j}$ (k = 1, 2, ⋯, t_n) are called the leaves of the tree. Because there are m bases in matroid M_{r
₁} = (E, I_{r
₁}), we can construct m trees with the set sequences induced by each basis $A_{1}^{j}$ (j = 1, 2, ⋯, m) of M_{r
₁} = (E, I_{r
₁}). These trees can form a forest.

Fig. 1.

The tree structure of a closed G-V fuzzy matroid.

Each tree can be divided into n levels. The sets in the first level (r₁ level) are the bases of matroid M_{r
₁} = (E, I_{r
₁}) and the sets in the i - th level (r_i level) are not only the independent sets of matroid M_{r
_i} = (E, I_{r
_i}) but also the maximal subsets of the corresponding set in the (i - 1) - th level. By Theorem 3.2(2), for each sequence discussed above $A_{1}^{j}, A_{2, 1}^{j}, \dots, A_{n, 1}^{j}$ which is a branch of some tree, let μ (x) = r_n if $x \in A_{n, 1}^{j}$ and let μ (x) = r_i if $x \in A_{i, 1}^{j} ∖ A_{i + 1, 1}^{j} (i = 1, 2, \dots, n - 1)$ . Then μ is a fuzzy basis of a closed G-V fuzzy matroid M = (E, ψ) by the sufficiency of Theorem 3.2.

On the other hand, let μ be a fuzzy basis of a closed G-V fuzzy matroid M = (E, ψ), by the necessity of Theorem 3.2, supp μ = C_{r
₁} (μ) is a basis of matroid M_{r
₁} = (E, I_{r
₁}) and supp μ = C_{r
₁} (μ) ⊇ C_{r
₂} (μ) ⊇ ⋯ ⊇ C_{r
_n-1} (μ) ⊇ C_{r
_n} (μ) and C_{r
_i} (μ) ∈ I_{r
_i} (i = 1, 2, ⋯, n) is a maximal subset of C_{r
_i-1} (μ). Therefore, the sequence C_{r
₁} (μ), C_{r
₂} (μ), ⋯, C_{r
_n-1} (μ), C_{r
_n} (μ) is corresponding to a branch of some tree. By Theorem 3.2, a branch of a tree is uniquely determined by the fuzzy basis a closed G-V fuzzy matroid. Thus the tree structure of a closed G-V fuzzy matroid can be defined as follows.

Definition 3.1. The constructed trees by Theorem 3.2 are called the tree structure of a closed G-V fuzzy matroid M = (E, ψ) based on G-V fuzzy matroid, denoted by T (E, ψ)(T for short).

Obviously, the branch and the leaf are one-to-one corresponding.

Remark 3.1. From Theorem 3.2 and The construction process of the tree structure of a closed G-V fuzzy matroid, we can learn that a branch of the tree structure and a fuzzy basis of a closed G-V fuzzy matroid are one-to-one corresponding. For a closed G-V fuzzy matroid, the number of fuzzy basis is equal to the number of leaves of the tree structure.

Example 3.1. Let E = {1, 2, 3, 4}, I₁ = {φ, {1}, {2}, {1, 2}}, $\begin{matrix} I_{\frac{1}{2}} = {φ, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, \\ {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}}, \end{matrix}$ $\begin{matrix} I_{\frac{1}{3}} = {φ, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, \\ {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, \\ {2, 3, 4} . \end{matrix}$

Then (E, I₁), $(E, I_{\frac{1}{2}})$ , $(E, I_{\frac{1}{3}})$ are all crisp matroids, and $I_{\frac{1}{3}} \supset I_{\frac{1}{2}} \supset I_{1}$ . Let $I_{r} = {\begin{matrix} I_{\frac{1}{3}}, & if 0 < r \leq \frac{1}{3}, \\ I_{\frac{1}{2}}, & if \frac{1}{3} < r \leq \frac{1}{2}, \\ I_{1}, & if \frac{1}{2} < r \leq 1, \end{matrix}$

and let ψ = {μ ∈ F (E) |C_r (μ) ∈ I_r, r ∈ (0, 1]}. Then by Remark 2.1 (4), M = (E, ψ) is a closed G-V fuzzy matroid and its tree structure is shown in Fig. 2.

From Fig. 2, there are six leaves in the tree structure which contains four trees. Then by Remark 3.1, there are six bases of the closed G-V fuzzy matroid M = (E, ψ) and they are as follows:

Fig. 2.

The tree structure of Example 3.1.

$\begin{matrix} μ_{1} (x) = {\begin{matrix} 1, & x = 1 \\ 1, & x = 2 \\ \frac{1}{2}, & x = 3 \\ 0, & x = 4 \end{matrix}, & μ_{2} (x) = {\begin{matrix} 1, & x = 1 \\ 1, & x = 2 \\ 0, & x = 3 \\ \frac{1}{2}, & x = 4 \end{matrix}, \\ μ_{3} (x) = {\begin{matrix} 1, & x = 1 \\ 0, & x = 2 \\ \frac{1}{2}, & x = 3 \\ \frac{1}{2}, & x = 4 \end{matrix}, & μ_{4} (x) = {\begin{matrix} 0, & x = 1 \\ 1, & x = 2 \\ \frac{1}{2}, & x = 3 \\ \frac{1}{3}, & x = 4 \end{matrix}, \\ μ_{5} (x) = {\begin{matrix} 0, & x = 1 \\ 1, & x = 2 \\ \frac{1}{3}, & x = 3 \\ \frac{1}{2}, & x = 4 \end{matrix}, & μ_{6} (x) = {\begin{matrix} 0, & x = 1 \\ \frac{1}{3}, & x = 2 \\ \frac{1}{2}, & x = 3 \\ \frac{1}{2}, & x = 4 \end{matrix} . \end{matrix}$

3.3 The tree structure of a closed regular G-V fuzzy matroid

There are the same results in a closed regular G-V fuzzy matroid as those in a closed G-V fuzzy matroid.

Let M = (E, ψ) be a closed regular G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1 and M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} is the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n).

Suppose that there are m bases in matroid M_{r
₁} = (E, I_{r
₁}). For any basis $A_{1}^{j}$ (j = 1, 2, ⋯, m) of matroid M_{r
₁} = (E, I_{r
₁}), by Definition 2.3 and Remark 2.2 and Corollary 3.2, there exists a sequence $A_{2, 1}^{j}, \dots, A_{n - 1, 1}^{j}, A_{n, 1}^{j}$ ( $A_{i, 1}^{j} \in I_{r_{i}},$ i = 2, 3, ⋯, n) satisfying $A_{1}^{j} \supseteq A_{2, 1}^{j} \supseteq \dots \supseteq A_{n - 1, 1}^{j} \supseteq A_{n, 1}^{j}$ and i = 1, 2, ⋯, n - 1 is not only a maximal subset of $A_{i - 1, 1}^{j}$ but also a basis of A_n ≠ φ. The sequence $A_{1}^{j}, A_{2, 1}^{j}, \dots, A_{n - 1, 1}^{j}, A_{n, 1}^{j}$ (called $A_{1}^{j}$ -induced set sequence, j = 1, 2, ⋯, m) can be constructed a branch of a tree. Because $A_{i, 1}^{j}$ is not the only maximal subset of $A_{i - 1, 1}^{j}$ (i = 2, 3, ⋯, n) in I_{r
_i}, there are many sequences induced by $A_{1}^{j}$ which can be constructed many branches of a tree. These trees are called the tree structure of a closed regular G-V fuzzy matroid and the tree structure satisfies Remark 3.1.

Example 3.2. Let E = {1, 2, 3}, I₁ = {φ, {1}, {2}}, $I_{\frac{1}{2}} = {φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}$ .

Then (E, I₁) and $(E, I_{\frac{1}{2}})$ are all crisp matroids, and $I_{\frac{1}{2}} \supset I_{1}$ . Let $I_{r} = {\begin{matrix} I_{\frac{1}{2}}, & if 0 < r \leq \frac{1}{2}, \\ I_{1}, & if \frac{1}{2} < r \leq 1, \end{matrix}$

and let ψ = {μ ∈ F (E) |C_r (μ) ∈ I_r, r ∈ (0, 1]}. Then by Remark 2.1 (4) and Remark 2.2, M = (E, ψ) is a closed regular G-V fuzzy matroid and its tree structure is shown in Fig. 3.

From Fig. 3, there are two leaves in the tree structure which contains one tree. Then by Remark 3.1, there are two bases for the G-V fuzzy matroid M = (E, ψ) as follows.

Fig. 3.

The tree structure of Example 3.2.

$\begin{matrix} μ_{1} (x) = {\begin{matrix} 1, & x = 1 \\ \frac{1}{2}, & x = 2 \\ \frac{1}{2}, & x = 3 \end{matrix}, & μ_{2} (x) = {\begin{matrix} \frac{1}{2}, & x = 1 \\ 1, & x = 2 \\ \frac{1}{2}, & x = 3 \end{matrix} \end{matrix} .$

4 The properties of the tree structure for a closed G-V fuzzy matroid

In this section, the properties of the tree structure for a closed G-V fuzzy matroid are considered.

Theorem 4.1. Let M = (E, ψ) be a closed G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1. Suppose further that M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} is the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n). Then each basis of induced matroid (E, I_{r
_i}) (i = 1, 2, ⋯, n) is in r_i level of the tree structure.

Proof. The proof will be by induction on i. When i = 1. Since each basis of matriod M_{r
₁} = (E, I_{r
₁}) is the root of each tree in the tree structure, then they are in r₁ level.

Suppose now that the theorem holds whenever i = k. When i = k + 1, for any basis A_k+1 of matroid M_{r
_k+1} = (E, I_{r
_k+1}), since (E, I_{r
_k+1}) ⊂ (E, I_{r
_k}), then A_k+1 ∈ I_{r
_k}. It follows that there exists a basis A_k of (E, I_{r
_k}) such that A_k+1 ⊆ A_k. Obviously, A_k+1 is a maximal subset of A_k in I_{r
_k+1}. It implies that A_k+1 is in r_k+1 level of the tree structure.

But the converse of Theorem 4.1 doesn’t hold. From Example 3.1, the basis {1, 2} of matroid (E, I₁) is in r₁ level, the bases {1, 2, 3}, {1, 2, 4} and {1, 3, 4} of matroid $(E, I_{\frac{1}{2}})$ are all in $r_{\frac{1}{2}}$ level, and the bases {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} of matroid $(E, I_{\frac{1}{3}})$ are all in $r_{\frac{1}{3}}$ level. But {2, 3}, {2, 4}, {3, 4} which are not the bases of matroid $(E, I_{\frac{1}{2}})$ are also in $r_{\frac{1}{2}}$ level, and {1}, {2}, φ which are not the bases of matroid $(E, I_{\frac{1}{3}})$ are also in $r_{\frac{1}{3}}$ level.

Corollary 4.1. Let M = (E, ψ) be a closed regular G-V fuzzy matroid on E with the fundamental sequence 0 = r₀ < r₁ < ⋯ < r_n ≤ 1 and M_{r
₁} ⊃ M_{r
₂} ⊃ ⋯ ⊃ M_{r
_n} be the M-induced matroid sequence (where M_{r
_i} = (E, I_{r
_i}), i = 1, 2, ⋯, n). Then each basis of (E, I_{r
_i}) is in r_i level of the tree structure and the sets in each level of the tree structure are all the basis of matroid (E, I_{r
_i}), i = 1, 2, ⋯, n.

From Example 3.2, all the bases {1} and {2} of matroid (E, I₁) are in r₁ level, the only basis {1, 2, 3} of matroid $(E, I_{\frac{1}{2}})$ is in $r_{\frac{1}{2}}$ level. On the other hand, the sets in r₁ and $r_{\frac{1}{2}}$ level are bases of (E, I₁) and $(E, I_{\frac{1}{2}})$ , respectively.

Corollary 4.2. The sets in the same level of the tree structure for a closed regular G-V fuzzy matroid have the same cardinality. The fuzzy bases of a closed regular G-V fuzzy matroid have the same cardinality.

Theorem 4.2. Let T be the tree structure of a closed G-V fuzzy matroid M = (E, ψ). B_i(i = 1, 2, ⋯, n) is the set of all the sets in r_i level of the tree structure T. Then I_{r
_i} = {X|X ⊆ A, A ∈ B_i} (where (E, I_{r
_i}) is the M-induced matroid).

Proof. For any Y ∈ I_{r
_i}, by the properties of the independent set, there exists a basis A of (E, I_{r
_i}) such that Y ⊆ A. By Theorem 4.1, all the bases of the M-induced matroid (E, I_{r
_i}) (i = 1, 2, ⋯, n) are in r_i level of the tree structure T, It follows that there exists i (i = 1, 2, ⋯, n) such that A ∈ B_i. It implies that Y ∈ {X|X ⊆ A, A ∈ B_i}. Thus, I_{r
_i} ⊆ {X|X ⊆ A, A ∈ B_i}. On the other hand, for any Y ∈ {X|X ⊆ A, A ∈ B_i}, there exists a set A in r_i (i = 1, 2, ⋯, n) level of the tree structure T such that Y ⊆ A. By Theorem 3.2, A ∈ I_{r
_i}, then Y ∈ I_{r
_i}. It implies that {X|X ⊆ A, A ∈ B_i} ⊆ I_{r
_i}. Thus I_{r
_i} = {X|X ⊆ A, A ∈ B_i}.

Remark 4.1. For the discussions above, we have

Let T be the tree structure of a closed G-V fuzzy matroid M = (E, ψ). Suppose that B_i is the set of all the maximal subsets in r_i level of the tree structure. Then all the bases of matroid (E, I_{r
_i})(i = 1, 2, ⋯, n) belong to B_i.

Let T be the tree structure of a closed regular G-V fuzzy matroid M = (E, ψ). Suppose that B_i is the set of all the sets in r_i level of the tree structure. Then the set of all the bases of matroid (E, I_{r
_i})(i = 1, 2, ⋯, n) is equal to B_i.

Theorem 4.3. Let T be the tree structure with n levels of a closed G-V fuzzy matroid M = (E, ψ). Suppose that a set sequence A₁, A₂, ⋯, A_n (A_i is in i - th level) of the tree structure satisfies A_n ≠ φ and A₁ ⊃ A₂ ⊃ ⋯ ⊃ A_n. For any x ∈ A_n, let k_n = μ (x) and for any x ∈ A_i ∖ A_i+1 (i = 1, 2, ⋯, n - 1), let k_i = μ (x). Then 0 = k₀, k₁, k₂, ⋯, k_n is the fundamental sequence of the closed G-V fuzzy matroid M = (E, ψ).

Proof. Let 0 < r₁ < r₂ < ⋯ < r_n ≤ 1 be the fundamental sequence of the closed G-V fuzzy matroid M = (E, ψ). By the assumption and Theorem 3.2, μ is a fuzzy basis of M. Thus R⁺ (μ) ⊆ {r₁, r₂, ⋯, r_n}. Suppose that a sequence A₁, A₂, ⋯, A_n satisfies A_n ≠ φ and A₁ ⊃ A₂ ⊃ ⋯ ⊃ A_n. It follows that A_i ∖ A_i+1 ≠ φ(i = 1, 2, ⋯, n - 1). Then k_i = μ (x) ≠0 for any i(i = 1, 2, ⋯, n - 1) and R⁺ (μ) = {k₁, k₂, ⋯, k_n}. Thus {k₁, k₂, ⋯, k_n} ⊆ {r₁, r₂, ⋯, r_n}. It implies that {k₁, k₂, ⋯, k_n} = {r₁, r₂, ⋯, r_n}.

Therefore, k₀, k₁, k₂, ⋯, k_n is the fundamental sequence of M.

5 Conclusion

In this paper, based on the study of fuzzy bases, a precise necessary and sufficient condition of judging fuzzy bases of a closed G-V fuzzy matroid and an intuitive tree structure of a closed G-V fuzzy matroid are proposed and some of its properties are studied. The tree structure can represent a closed G-V fuzzy matroid because of the one-to-one corresponding between a tree structure and the set of the fuzzy basis of a closed G-V fuzzy matroid. Therefore, the idea of the tree structure for a G-V fuzzy matroid will make G-V fuzzy matroid apply to combinatorial optimization problems.

Footnotes

Acknowledgments

The authors would like to thank the unknown reviewers for their valuable comments and suggestions.

This work was supported by the National Natural Science Foundation of China (Grant Nos. 11671001 and 61472056), the Natural Science Foundation Project of CQ CSTC of China (Grant Nos. cstc2015jcyjA00034), and the Project of Humanities and Social Sciences planning fund of Ministry of Education of China (18YJA630022).

References

Goetschel and

Voxman , Fuzzy matroids, Fuzzy Sets and Systems 27 (1988), 291–302.

Goetschel and

Voxman , Bases of fuzzy matroids, Fuzzy Sets and Systems 31 (1989), 253–261.

Goetschel and

Voxman , Fuzzy circuits, Fuzzy Sets and Systems 32 (1989), 35–43.

Goetschel and

Voxman , Fuzzy matroids and a greedy algorithm, Fuzzy Sets and Systems 37 (1990), 201–213.

Goetschel and

Voxman , Fuzzy matroid structures, Fuzzy Sets and Systems 41 (1991), 343–357.

Goetschel and

Voxman , Fuzzy rank functions, Fuzzy Sets and Systems 42 (1991), 245–258.

Goetschel and

Voxman , Spanning properties for fuzzy matroids, Fuzzy Sets and Systems 51 (1992), 313–321.

Goetschel and

Voxman , Fuzzy matroid sums and a greedy algorithm, Fuzzy Sets and Systems 52 (1992), 189–200.

D.-Y.

Wu ,

Y.-H.

Li ,

Yu and

Li , The judgment of fuzzy bases for closed fuzzy matroids, Fuzzy Systems and Mathematics 20(5) (2006), 54–58. (In Chinese).

10.

S.-G.

Li ,

Xin and

Y.-L.

Li , Closure axioms for a class of fuzzy matroids and co-towers of matroids, Fuzzy Sets and Systems 158 (2007), 1246–1257.

11.

X.-N.

Li and

S.-G.

Li , Characterizations of closed fuzzy matroids, Fuzzy Systems and Mathematics 21(5) (2007), 48–52. (In Chinese).

12.

Y.-H.

Li ,

Y.-B.

Liu and

Q.-X.

Shi , Rank of fuzzy circuits, Journal of Southwest China Normal University (Natural Science Edition) 34(3) (2009), 21–23. (In Chinese).

13.

Y.-H.

Li ,

D.-Y.

Wu and

X.-M.

Zhang , Necessary and sufficient conditions of fuzzy circuit for closed fuzzy matroids, Journal of Chong Qing University (Natural Science Edition) 30(6) (2007), 137–139. (In Chinese).

14.

Y.-H.

Li ,

C.-D.

Y and

D.-Y.

Wu , The research of algorithm of fuzzy circuit for closed fuzzy matroids, Pure and Applied Mathematics 24(1) (2008), 155–160. (In Chinese).

15.

Y.-H

Li ,

S.-D.

Xian and

Qiu , An improved algorithm of fuzzy circuit for closed fuzzy matroids, Presented at 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery 1 (2011), 68–70.

16.

Y.-L.

Li ,

G.-J.

Zhang and

L.-X.

Lu , Axioms for bases of closed regular fuzzy matroids, Fuzzy Sets and Systems 161 (2010), 1711–1725.

17.

X.-N.

Li ,

S.-Y.

Liu and

S.-G.

Li , Connectedness of refined Goetschel-Voxman fuzzy matroids, Fuzzy Sets and Systems 161 (2010), 2709–2723.

18.

F.-G.

Shi , A new approach to the fuzzification of matroids, Fuzzy Sets and Systems 160 (2009), 696–705.

19.

F.-G.

Shi , (L, M)-fuzzy matroids, Fuzzy Sets and Systems 160 (2009), 2387–2400.

20.

C.-E.

Huang and

F.-G.

Shi , Bases of [0,1]-matroids, Hacettepe Journal of Mathematics and Statistics 39(2) (2014), 233–240.

21.

Yao and

F.-G.

Shi , Bases axioms and circuits axioms for fuzzifying matroids, Fuzzy Sets and Systems 161 (2010), 3155–3165.

22.

Xin and

F.-G.

Shi , Rank functions for closed and perfect [0, 1]-matroids, Hacettepe Journal of Mathematics and Statistics 39(1) (2010), 31–39.

23.

Z.-Y.

Xiu and

Pang *, Base axioms and subbase axioms in M-fuzzifying convex structures, Iranian Journal of Fuzzy Systems 15(2) (2018), 75–87.

24.

Bin , Stratified L-ordered filter spaces, Quaestiones Math-ematicae 40(5) (2017), 661–678.

25.

Z.-Y.

Xiu and

Pang *, A degree approach to special mappings between L-fuzzifying convex spaces, Journal of Intelligent and Fuzzy Systems 35(1) (2018), 705–716.

26.

T.A.

Al-Hawary , Fuzzy greedoids, Int J Pure Appl Math 70(3) (2011), 285–295.

27.

T.A.

Al-Hawary , On fuzzy matroids, Inter J Math Cobin 1 (2012), 13–21.

28.

T.A.

Al-Hawary , Fuzzy C-flats, Fasciculi Mathematici 50 (2013), 5–15.

29.

Al-Hawary , Fuzzy flats, Indian J Mathematics 55(2) (2013), 223–236.

30.

Al-Hawary , Fuzzy closure matroids, Matematika 32(1) (2016), 69–74.

31.

Whitney , On the abstract properties of linear dependence, American Journal of Mathematics 57(3) (1935), 509–533.

32.

D.J.A.

Welsh , Matroid Theory, Academic Press, London, 1976.

33.

White , Theory of Matroid, Cambridge University Press, Cambridge, 1986.

34.

Reinhard , Graph Theory, Springer, New York, 2005.