# Connected Degree of Fuzzifying Matroids

Authors: Xiu Xin; Sheng Gang Li; Harish Garg; Heng Liu; Jingjing Zhao
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Polya’s plausible reasoning methods are crucial not only in discovery of mathematics results, modeling methods, and data processing methods but also in many practical problems’ solving. This paper exemplifies how to use Polya’s plausible reasoning methods to generalize the popularized notion of 2-connectedness of graphs to a more universal notion of the connected degree of fuzzifying matroids. We introduce the connectedness of fuzzifying matroids, which is generalized from 2-connectedness of graphs, connectedness of matroids, and 2-connectedness of fuzzy graphs. Moreover, the connected degree of fuzzifying matroids is presented by considering the fuzziness degree of connectedness. It is proved that a fuzzifying matroidM is connected, which is equivalent to its connectedness degree ConM is the biggest (i.e., ConM=1). This, together with other properties of the connected degree of fuzzifying matroids, demonstrates the rationality of the proposed notion. Finally, we describe the concepts of this paper through some examples.


---

## Body

## 1. Introduction

Whitney in his fundamental paper [1] defined a matroid as an abstract generalization of a graph and a matrix. One of the great beauties of the subject of the matroid theory is that there are so many equivalent descriptions of a matroid. Bases, circuits, rank function, or closure operator is also sufficient to uniquely determine the matroid besides independent sets [2, 3]. In addition, it is well known that matroids are of great significance in combinatorial optimization and are just the structure that can use the greedy algorithm to find the optimal solution of some problems [4, 5]. Combined with fuzzy set theory [6], some fuzzy concepts of a matroid are given. One is using a family of fuzzy sets instead of that of sets, a Goetschel–Voxman fuzzy matroid was proposed in [7] and was later on widely studied by the various researchers [8–16]. The other is using a mapping from 2E to 0,1 rather than a family of sets, a fuzzifying matroid was introduced by Shi, and it can also be determined uniquely by its fuzzifying rank function [17, 18]. Subsequently, some other equivalent descriptions of a fuzzifying matroid were discussed including base-map and circuit-map [19], three kinds of fuzzifying operators [20, 21], fuzzifying nullity [22]. Also, as its applications, a fuzzifying matroid is just the structure of the fuzzifying greedy algorithm for fuzzy optimization problems [23, 24]. Thus, Shi’s fuzzification method maintains matroids’ features.We know that there is an important connection between graphs and matroids. A graph (graphs in this paper are always loopless and without isolated vertices and have at least three vertices).G=V,E can induce a matroid E,ℐG which is called its cycle matroid and denoted by ℳG, where ℐG = {A⊆E:Adoes not contain any cycle ofG}. Motivated by analogies in graph theory, the connectedness of a matroid is defined. Here, ℳG is connected, which is equivalent to G is 2-connected; hence, the connectedness for matroids corresponds directly to the idea of 2-connectedness for graphs. It is natural to ask that is there fuzzifying matroid concept that corresponds directly to the idea of connectedness, or 2-connectedness, for fuzzy graphs?Our main aim is to give a concept of connectedness for fuzzifying matroids, which extends the corresponding notion for fuzzy graphs. We begin by recalling some basic notions and results to be used in this paper. In Section3, by using Polya’s plausible reasoning method, we show the course of discovering the notion of connected degree of fuzzifying matroids. In Section 4, we generalize the concept of 2-connectedness from matroids to fuzzifying matroids, which corresponds directly to the idea 2-connectedness for fuzzy graphs. In Section 5, we consider the fuzziness degree of connectedness for fuzzifying matroids. Using the degree to which a set is a separator, the notion of connected degree for a fuzzifying matroid is introduced. We show that the relationship between the connected degree of a fuzzifying matroid and the connectedness of its corresponding level matroids and investigate the connected degree for the dual of a fuzzifying matroid. We close the section with various examples to illustrate the concepts of this paper.


## 2. Preliminaries

In this paper, we shall denote byE a given finite set and by 2E the set of all subsets of E. Let A⊆2E and define MinA = {A∈A|Ais minimal inA}, OppA = {X⊆E|X∉A}, UppA = {X⊆E|there existsA∈A,A⊆X}.We begin with the definition of a matroid.Definition 1.
(cf. [2, 3]) A matroid ℳ is a finite set E and a collection ℐ of subsets of E (called independent sets) such that (I1)–(I3) are satisfied, denoted by ℳ=E,ℐ.(I1)ℐ≠∅;(I2)ℐ is a descending family;(I3) For any two elementsA,B∈ℐ with A<B, one element e∈B−A can be found so that A ∪ {e} belongs to ℐ.
It is important (for understanding the notion of fuzzifying matriod in the following Step5) to notice that a matroid can also be defined equivalently as a finite set E and a collection C of subsets of E (called circuits) satisfying three circuit axioms [2]: C1∅∉C; C2C is an antichain; C3 for any two different elements C1,C2∈C and e∈C1∩C2, one element C3∈C can be found to be included in C1∪C2 − {e}. Specifically, take a matroid E,ℐ (i.e., which means that ℐ satisfies (I1)–(I3)), then, Cℐ=MinOppℐ is the family of all circuits for it (i.e., Cℐ satisfies (C1)–(C3)); conversely, take a matroid E,C (i.e., C satisfies (C1)–(C3)), then ℐC=OppUppC is the family of all independent sets for it (i.e., ℐC satisfies (I1)–(I3)) and C=CℐC.
Moreover, ifE,ℐ is a matroid, its rank function ℛℐ is defined as a mapping from 2E to the set of natural numbers N by ℛℐA=max {|B‖B⊆A,B∈ℐ} and can uniquely determine the matroid [3].
Next, we present some other notations, notions, and results needed in this paper. As usual,0,1E denotes the collection of fuzzy subsets on E, where a fuzzy subset on E is a mapping from E to 0,1. If A∈0,1E and a∈0,1, we will often denote the set of x∈E satisfying Ax≥a and the set of x∈E satisfying Ax>a by Aa and Aa, respectively. Fuzzy natural numbers and their operations have been introduced [17, 22, 23, 25]. An antitone mapping λ from the set of natural numbers N to 0,1 is called a fuzzy natural number if λ0=1 and ∧ {λn|n∈ℕ} = 0. We will use N0,1 to denote the collection of fuzzy natural numbers. Let λ,μ be fuzzy natural numbers, their sum, written λ+μ is also a fuzzy natural numbers such that for every n∈N, λ+μn=∨ {λk∧μl|n=k+l}, their subtraction is given by λ−μ=∨ {ν∈N0,1|ν+μ≤λ}. If we regard a natural number m as a fuzzy natural number m¯ such that m¯n=1 for n≤m and m¯n=0 for n≥m+1, then, we can get following operational properties, for every a∈0,1, λ+μa=λa+μa and λ+μa=λa+μa.
In [17, 18], the definition of a fuzzifying matroid on E was given.Definition 2.
(cf. [17, 18]) A fuzzifying matroid M is a finite set E and a mapping II from 2E to 0,1 (called fuzzy family of independent sets) such that (FI1)–(FI3) are satisfied, written as M=E,II. For any two subsets A,B of E,(FI1)II∅=1;(FI2)IIA≥IIB if A⊆B;(FI3)∨e∈B−AII (A ∪ {e}) ≥ IIA∧IIB if A<B.
For a fuzzifying matroid, the following characterization theorem holds.Theorem 1 (cf. [17]).
IfII is a mapping from 2E to 0,1, then, E,II is a fuzzifying matroid, which is equivalent to each of the following statements.(1)
{E,IIa|a∈0,1} is a family of matroids;(2)
{E,IIa|a∈0,1} is a family of matroids.
It is also important to notice that a fuzzifying matroid can be defined equivalently as a pairE,ℂ, where ℂ is a mapping from 2E to 0,1 satisfying two axioms [19]: (FC1) for any a∈0,1, Minℂa satisfies circuits axioms (C1)–(C3); (FC2) for any subset C of E, ℂC=a≠0 implies C∈Minℂa. In fact, let E,II be a fuzziying matroid (i.e., II satisfies (FI1)–(FI3)), the mapping ℂII:2E⟶0,1 defined by for any subset C of E such that ℂIIC=1−∧ {a∈0,1|C∈CIIa}, not only is the circuit-map of E,II (i.e., ℂII satisfies (FC1)-(FC2)) but also MinℂIIa=CII1−a for any a∈0,1. Conversely, let E,ℂ be a fuzziying matroid (i.e., ℂ satisfies (FC1)-(FC2)), the mapping IIℂ:2E⟶0,1 defined by IIℂA=1−∨ {ℂB|B⊆A} ∀A∈2E satisfies (FI1)–(FI3)) and ℂ=ℂIIℂ.
The fuzzifying rank function was also defined.Definition 3.
(cf. [17, 23]). A mapping ℝII from 2E to N0,1 is called fuzzifying rank function of a given fuzzifying matroid E,II, if for any subset A of E and any natural number n such that ℝIIAn=∨ {IIB|B⊆A,B≥n}.Theorem 2 (cf. [17, 23]).
The fuzzifying rank functionℝII for a fuzzifying matroid E,II has the properties:(1)
ℝIIAa=ℛIIaA∀A∈2E,∀a∈0,1.(2)
ℝIIAa=ℛIIaA∀A∈2E,∀a∈0,1.
Furthermore, for any fuzziying matroidE,II (i.e., II satisfies (FI1)–(FI3)), its fuzzifying rank function ℝII possesses some features, shown as, for any two subsets A,B of E, (FR1) 0¯≤ℝIIA≤A¯; (FR2) A⊆B implies ℝIIA≤ℝIIB; (FR3) ℝIIA∩B+ℝIIA∪B≤ℝIIA+ℝIIB. Conversely, for a fuzzifying rank function ℝ:2E⟶N0,1 (i.e., ℝ satisfies (FR1)–(FR3)), the mapping IIℝ:2E⟶0,1 defined by IℝA=ℝAA∀A∈2E satisfies (FI1)–(FI3)) and ℝ=ℝIIℝ.Definition 4.
(cf. [25]) For any fuzzifying matroid M=E,II, a new mapping ℝII˜ from 2E to N0,1 is given by for any subset A of E such that ℝII˜A=A¯+ℝIIE−A−ℝIIE. It is proved that ℝII˜ satisfies (FR1)–(FR3)), and thus, IIℝII˜ satisfies (FI1)–(FI3)), denoted by II∗. Hence E,II∗ is a fuzzifying matroid, which is called the dual of M, written as M∗. In addition, the dual of M∗=E,II∗ is denoted by M∗∗=E,II∗∗.Theorem 3.
(cf. [25]) Suppose that E,II is a fuzzifying matroid, then, II∗∗=II is equivalent to each of the following statements:(1)
II∗a=IIa∗ for any element a in 0,1,(2)
II∗a=IIa∗ for any element a in 0,1.


## 3. The Course of Discovering the Notion of Connected Degree of Fuzzifying Matroids

We say that a graph is 2-connected if any two distinct edges are contained in a cycle. This notion (actually many others) is easy-to-understand to many students and practitioners. A natural question is that can they discover, starting from such a notion and its relevant results, some innovative things which are interesting, meaningful, or needed for themselves? This paper will exemplify a positive answer. Precisely, it will generalize (by using plausible reasoning method [26]) the notion of 2-connectedness of graphs to a very extended and useful notion (called connected degree of fuzzifying matroids) and present some properties of connected degree of fuzzifying matroids.We will sketch the course of discovering the notion of the connected degree of fuzzifying matroids which may be of reference value to both our research successors and out-of-the-box researchers.Step 1.
Find out a characterization 2-connectedness of graphs (from all) start from which the notion described can be generalized: for a graph, writtenG=V,E, we call that it is 2-connected if its any two distinct edges are contained in a cycle [2, 3], i.e., for any two different elements e1,e2 in E, one element C in CG (the set of all cycles of G) can be found to include e1 and e2, simultaneously.Step 2.
Since matroid concept can be regarded as a generalization of graph concept (for a graphG, the collection of its cycles is represented as CG, which is exactly the family of circuits for the cycle matroid ℳG of G, thus, ℳG can also denoted equivalently as E,CG. So, we can think of G as a matroid ℳG=E,CG), it is natural to generalize the notion of 2-connectedness from the class of graphs (written as G) to the class of matroids (written as M).Step 3.
It is also reasonable saying the special matroidℳG=E,CG is connected when G is 2-connected, i.e., for any two different elements e1,e2 in E, one element C in CG can be found to include e1 and e2 simultaneously (see Step 1). Generalization of this can be taken as a definition of connectedness of a matroid (see Step 4).Step 4.
We call that a matroidℳ=E,C is connected if, for any two different elements e1,e2 in E, one element C in C can be found to include e1 and e2 simultaneously [2, 3].Step 5.
As a matroid is a special fuzzifying matroid (for any matroidE,ℐ or E,C, we do not distinguish between E,ℐ and E,1ℐ and between E,C and E,1C, where 1ℐ and 1C are characteristic functions of ℐ and C, respectively), we naturally extend the notion of connectedness from the class of matroids to that of fuzzifying matroids (written as FM).Step 6.
It is reasonable saying the special fuzzifying matroidE,1C is connected when the corresponding matroid E,C is connected. In other words, for any {e1,e2} ⊆ E, ∨ {1CC|e1,e2∈C} = 1. Generalization of this can be taken as a definition of connectedness of a fuzzifying matroid (see Step 7).Step 7.
A fuzzifying matroidE,ℂ is called connected (or 2-connected) if for any {e1,e2} ⊆ E, ∨ {ℂC|e1,e2∈C⊆E} = 1 (see the following Theorem 4 for a characterization).Step 8.
Find out a characterization (i.e., the separator characterization) of the connectedness of matroids (from all) start from which the notion described can be generalized: A matroidℳ is disconnected if and only if (briefly, iff) a proper subset A of E can be found to be a separator of ℳ. Generalization of this can be taken as a definition of connected degree of a fuzzifying matroid (see Step 12).Step 9.
Recall and redescribe the definition of the separator (so that connectedness of a matroid can be generalized to connected degree of a fuzzifying matroid). Suppose thatℳ=E,C is a matroid, a subset A of E is called a separator of ℳ (in other words, the degree to which A is a separator of ℳ is equal to 1, denoted by SepA=1) iff for any C∈C there must be C⊆A or C⊆E−A, that is, C∉C whenever C is a subset of E not included in both A and E−A (i.e., ∧ {1−1CC|C is a subset of E not included in both A and E−A} = 1). Compare the values of SepA and ∧ {1−1CC|C is a subset of E not included in both A and E−A}, we get SepA = ∧ {1−1CC|C is a subset of E not included in both A and E−A}. It is natural to generalize the equation from a matroid to a fuzzifying matroid (see Step 10).Step 10.
Given a fuzzifying matroidM=E,ℂ and a subset A of E, we call that SepA = ∧ {1−ℂC|C is a subset of E not included in both A and E−A} is the degree to which A∈2E is a separator of M.Step 11.
A matroidℳ is disconnected (that is to say the connected degree of ℳ is equal to 0, denoted by Conℳ=0) if a proper subset A of E can be found to be a separator of ℳ (i.e., ∧ {1−SepA|A∈2E− {∅,E}} = 0). Compare the values of Conℳ and ∧ {1−SepA|A∈2E− {∅,E}}, we get Conℳ=∧ {1−SepA|A∈2E− {∅,E}}. It is natural to generalize the equality from a matroid to a fuzzifying matroid (see Step 12).Step 12.
Given a fuzzifying matroidM=E,ℂ, we call ConM=∧ {1−SepA|A∈2E− {∅,E}} is the connected degree of M.


## 4. Characterizations and Rationality of Connectedness of Fuzzifying Matroids

Although a fuzzifying matroid can be defined as both a pairE,II and a pair E,ℂ, we find that the circuit-map axioms (FC1)-(FC2) of a fuzzifying matroid is not a natural way to generalize the circuits axioms (C1)–(C3) of a matroid. Hence, in the subsequent discussion, we always suppose that a fuzzifying matroid and a matroid are pairs E,II and E,ℐ, respectively.The following Definition5, Theorem 4, and Corollary 1 (which characterize the connectedness of fuzzifying matroids, see Step 7 for the definition) show that the connectedness of fuzzifying matroids is in harmony with that of matroids.Definition 5.
AmappingℂII from 2E to 0,1 is the circuit-map of a given fuzzifying matroid E,II which is said to be connected if for any two elements e1,e2 in E such that ∨ {ℂIIC|e1,e2∈C⊆E} = 1.Theorem 4.
A fuzzifying matroidE,II is connected, which is equivalent to E,II0 is connected.Proof.
IfE,II is connected, then, for any two elements e1,e2 in E, a subset C of E can be found to satisfy ℂIIC=1 and include e1 and e2, and thus C∈MinℂII1=CII0 by the property of ℂII. This implies that E,II0 is connected. Conversely, if E,II0 is connected, then, for any two elements e1,e2 in E, one element C in CII0 can be found to include e1 and e2, and thus ℂIIC=1−∧ {a∈0,1|C∈CIIa} = 1 − 0 = 1. Hence, ∨ {ℂIIC|e1,e2∈C⊆E} = 1, which implies that E,II is connected.
Notice that, the fuzzifying matroidE,II induced by a fuzzy family of circuits is introduced [27], it has the following properties, for any two elements a,b in 0,1, a≤b implies CIIa⊆CIIb. Thus, Theorem 4 deduces the following corollary.Corollary 1.
A fuzzifying matroidE,II induced by a fuzzy family of circuits is connected if and only if E,IIa is connected ∀a∈0,1.
A fuzzy graph [28] G is a set of nodes V together with two fuzzy sets σ and μ on V and V×V, respectively, satisfied for any pair of elements x,y of V, μx,y≤σx∧σy, written as G=V,σ,μ. Graph G¯=V,1σ0,1μ0 is called the underline graph of G, and we identify that 1σ0 and 1μ0 are characteristic functions of σ0 and μ0, respectively. When σ and μ take no value in 0,1, G equals G¯ and so it is a graph, which implies that the class of fuzzy graphs contains that of graphs. Furthermore, the concept of connectedness can be extended from graphs to more general a fuzzy graphs. In one way, a fuzzy graph is 2-connected, which is defined as its underline graph is 2-connected. Actually, each fuzzy graph G=V,σ,μ can induce a fuzzifying matroid which is the set E of edges in G and a mapping IIG from 2E to 0,1 defined as for every subset A of E such that IIGA=∨ {a∈0,1|μacontainsAand any cycle ofV,μais not included in A}, called fuzzifying cycle matroid of G. Therefore, the notion of 2-connectedness for fuzzy graphs can be generalized to that of connectedness for their fuzzifying cycle matroids, and then to that of connectedness for more general fuzzifying matroids (see the following Theorem 5) which means the connectedness of fuzzifying matroids is also in harmony with 2-connectedness of fuzzy graphs.Lemma 1.
E,IIG and E,ℐG¯ are the fuzzifying cycle matroid and the cycle matriod, respectively, induced by a fuzzy graph G=V,σ,μ and its underline graph G¯, we have ℐG¯=IIG0.Proof.
∀A∈IIG0, i.e., IIGA>0, thus, a number a in 0,1 can be found such that μacontainsAand any cycle ofV,μais not included inA. Suppose that A contains a cycle of V,μ0, then A contains a cycle of V,μa since A⊆μa. There is a contradiction. Therefore, μ0 contains A and any cycle of V,μ0is not included inA, i.e., A∈ℐG¯.
∀A∈ℐG¯, i.e., μ0 contains A and any cycle of V,μ0 is not included in A. We can find a number a in (0,1) satisfying μ0=μa because the range of μ is a finite set. Hence, μa also contains A and any cycle of V,μa is not also included in A. This implies that IIGA≥a>0, we have A∈IIG0.
By Theorem4 and Lemma 1, we get the fuzzifying cycle matroid E,IIG is connected iff E,IIG0 is connected iff E,ℐG¯ is connected iff G¯ is 2-connected iff G is 2-connected. Hence, the following theorem holds.Theorem 5.
Fuzzifying cycle matroidE,IIG induced by a fuzzy graph G is connected, which is equivalent to G is 2-connected.


## 5. Connected Degree of Fuzzifying Matroids

Recall that the connected degree of a fuzzifying matroid is defined by using the notion of the degree to which a set is a separator (see Steps10 and 12). In this section, we study the connections between the notions of the degree to which a subset is a separator, connected degree, and connectedness of a fuzzifying matroid. We also obtain a generalization of a classical result on separators of matroids (see Theorem 7).Definition 6.
Define the degree to whichA∈2E is a separator of a given fuzzifying matroid E,II as SepA=∧ {1−ℂIIC|C is a subset of E not included in both A and E−A}.Theorem 6.
The following statements hold, see Definition6 for this symbol SepA.(1)
IfSepA>a, then, A is a separator of E,IIaa∈0,1.(2)
IfSepA=a, then, A is not a separator of E,IIaa∈0,1.(3)
IfSepA<aa∈0,1, uncertain.(4)
SepA=0 if and only if A is not a separator of E,II0.Proof.
(1)
Suppose thatA is not a separator of E,IIa, then, one element C∈CIIa can be found to be not included in both A and E−A; hence, ℂIIC≥1−a and then SepA≤a by the definitions of ℂII and SepA.(2)
Suppose thatSepA=a∈0,1, i.e., ∧ {1−ℂIIC|C is a subset of E not included in both A and E−A} = a≠1, then, 1−ℂIIC=a≠1 for some subset C of E not included in both A and E−A, which implies this subset C∈MinℂII1−a=CIIa. In other words, C∈CIIa for some subset C of E not included in both A and E−A, i.e., Ais not a separator ofE,IIa.(3)
Take a counter example. A finite setE = {e1,e2,e3} together with a mapping II from 2E to 0,1 defined as II∅=II ({e1}) = 1, II ({e2}) = II ({e3}) = 1/2, II ({e1,e2}) = II ({e1,e3}) = II ({e2,e3}) = II ({e1,e2,e3}) = 1/3, form a fuzzifying matroid. Then, CIIa=∅ (if 0≤a<1/3), {{e1,e2}, {e1,e3}, {e2,e3}} (if 1/3≤a<1/2), {{e2}, {e3}} (if 1/2≤a<1) by the definitions of IIa and Cℐ, and thus by the definition of ℂII, ℂIIC=0 (if C∈ {∅, {e1}, {e1,e2,e3}}), 1/2 (if C∈ {{e2}, {e3}}), 2/3 (if C∈ {{e1,e2}, {e1,e3}, {e2,e3}}). Let A = {e1}, by Definition 6, SepA=∧ {1−ℂIIC|C = {e1,e3}, {e1,e2}, {e1,e2,e3}} = 1−2/3∧1−2/3∧1−0=1/3<0.4<0.5. We can check that A is not a separator of E,II0.4 although it is a separator of E,II0.5.(4)
IfSepA=0, then, A is not a separator of E,II0 by (2). Conversely, if A is not a separator of E,II0, then, SepA≤0 by (1), i.e., SepA=0.
A classical result on separators of matroids: for any subsetA of E, it is a separator of a given matroid E,ℐ, which is equivalent to the rank function ℛℐ satisfies ℛℐA+ℛℐE−A=ℛℐE. Its promotion is as follows:Theorem 7.
The following conditions are equivalent, among them, symbolsSepA and ℝII refer to Definition 6 and Definition 3, respectively.(1)
SepA=1;(2)
A is a separator of E,IIa for each a∈0,1;(3)
ℝIIA+ℝIIE−A=ℝIIE;(4)
A is a separator of E,IIa for each a∈0,1.Proof.
1⇔2. If SepA=1, then, for each a∈0,1, SepA>a, thus, A is a separator of E,IIa by Theorem 6 (1). Conversely, if (2) holds, i.e., A is a separator of E,IIa for each a∈0,1. Assume that SepA=b≠1, then, A is not a separator of E,IIb by Theorem 6 (2), which contradicts (2). Hence, SepA=1.
By Theorem2 and the property of the addition of fuzzy natural numbers, we have
2⇔3. A is a separator of E,IIa for each a∈0,1⇔ℛIIaA+ℛIIaE−A=ℛIIaE for each a∈0,1⇔ℝIIAa+ℝIIE−Aa=ℝIIEa for each a∈0,1⇔ℝIIA+ℝIIE−Aa=ℝIIEa for each a∈0,1⇔ℝIIA+ℝIIE−A=ℝIIE.
3⇔4. ℝIA+ℝIE−A=ℝIIE⇔ℝIIA+ℝIIE−Aa=ℝIIEa for each a∈0,1⇔ℝIIAa+ℝIIE−Aa=ℝIIEa for each a∈0,1⇔ℛIIaA+ℛIIaE−A=ℛIIaE for each a∈0,1⇔A is a separator of E,IIa for each a∈0,1.Definition 7.
ConM=∧ {1−SepA|A∈2E− {∅,E}} is called connected degree of a given fuzzifying matroid M=E,II, where SepA is defined in Definition 6.
The connection between the connected degree of a fuzzifying matroid and the degree to which a subset is a separator is described in the following theorem.Theorem 8.
The following statements are true, where symbolsSepA and ConM are defined in Definition 6 and Definition 7, respectively.(1)
IfConM>a, then SepA≠1−a for each nonempty proper subset A of Ea∈0,1.(2)
IfConM=a, then SepA=1−a for some nonempty proper subset A of Ea∈0,1.(3)
IfConM<aa∈0,1, uncertain.(4)
ConM=0 if and only if SepA=1 for some nonempty proper subset A of E.(5)
ConM=1 if and only if SepA=0 for each nonempty proper subset A of E.Proof.
(1)
Suppose that there exists a nonempty proper subsetA of E such that SepA=1−a, then,ConM=∧ {1−SepA|A∈2E− {∅,E}} ≤ a.(2)
Suppose thatConM=a∈0,1, i.e., ∧ {1−SepA|A∈2E− {∅,E}} = a, then 1−SepA=a for some A∈2E− {∅,E}, that is, SepA=1−a for some nonempty proper subset A of E.(3)
Consider the fuzzifying matroidM in [27], it is a set E = {e1,e2,e3,e4,e5} and a mapping II from 2E to 0,1 defined as IIA=∨ {a∈0,1|A∈ℐa}. Here, ℐa is constant in 0,1/3 (resp., 1/3,1/2, 1/2,1), E,ℐ0, E,ℐ1/3, and E,ℐ1/2 are matroids with the families of circuits C0= {{e1,e3,e4}}, C1/3= {{e2,e3}, {e1,e2,e4}, {e1,e3,e4}}, and C1/2= {{e2,e3}, {e2,e4}, {e2,e5}, {e3,e4}, {e3,e5}, {e4,e5}}, respectively. Then, by the definition of ℂI, ℂIIC=1 (if C= {e1,e3,e4}), 2/3 (if C∈ {{e2,e3}, {e1,e2,e4}}), 1/2 (if C∈ {{e2,e4}, {e2,e5}, {e3,e4}, {e3,e5}, {e4,e5}}), and 0 (otherwise). Thus, by Definition 6, SepA=1 (if C∈ {∅,E}), 1/2 (if C∈ {{e5}, {e1,e2,e3,e4}}), 1/3 (if C∈ {{e2}, {e1,e3,e4,e5}, {e2,e5}, {e1,e3,e4}}), and 0 (otherwise). Therefore, by Definition 7, ConM=1/2<2/3<3/4. For a=2/3, Sep ({e2}) = 1/3=1−a although SepA≠1/4=1−b for b=3/4 and every nonempty proper subset A of E.(4)
IfConM=0, then, there exists a nonempty proper subset A of E such that SepA=1 by (2). Conversely, if SepA=1 for some nonempty proper subset A of E, then, ConM≤0 by (1), i.e., ConM=0.(5)
ConM=1⇔∧ {1−SepA|A∈2E− {∅,E}} = 1 ⇔1−SepA=1 (∀A∈2E− {∅,E}) ⇔SepA=0, (∀A∈2E− {∅,E}).
The following results show that the relationship between connected degree of a fuzzifying matroid and connectedness of its corresponding level matroids.Theorem 9.
The following statements are also true, among them, symbolConM refers to Definition 7, which is the connected degree of a fuzzifying matroid M=E,II.(1)
IfConM=a∈0,1, then, E,II1−b is not connected for any b>a. However, the converse is not true.(2)
IfConM=1 if and only if E,II0 is connected.Proof.
(1)
Suppose thatb>a=ConM, by Definition 7, there exists A∈2E− {∅,E} such that 1−SepA<b, and thus SepA>1−b; hence, Ais a separator inE,II1−b by Theorem 6. This implies that E,II1−b is not a connected matroid.Consider the fuzzifying matroidM=E,II defined in the proof of Theorem 8 (3). Obviously, three level matroids are all not connected. Take an a∈0,1 − {1/2}; then, E,II1−b is not connected for any b>a, but ConM=1/2≠a.(2)
It follows from Theorems6 (4) and 8 (5).
An immediate consequence of Theorems5 and 9 is the following Theorem 10 which shows the connections between the connected degree of a fuzzifying matroid and connectedness of a fuzzifying matroid.Theorem 10.
A fuzzifying matroidM is connected, which is equivalent to its connected degree ConM=1.
The rest of this section discusses the fuzzy analogs of the results: A separator in a matroid is also a separator in its dual, and the connectedness of a matroid is equivalent to that of its dual.Theorem 11.
The symbolsM and M∗ represent a fuzzifying matroid E,II and its dual E,II∗, if II∗∗=II, then, the following statements hold.(1)
Sep∗A=SepA for each A∈2E, where SepA and Sep∗A are the degrees to which A is a separator of M and M∗.(2)
ConM∗=ConM.(3)
M is connected, which is equivalent to M∗ is connected.Proof.
(1)
Suppose thatSepA=a, then, A is not a separator in E,IIa by Theorem 6 (2), so it is not in the dual matroid E,IIa∗, nor in E,II∗a by II∗∗=II and Theorem 3. By Theorem 6 (1), Sep∗A≤a, i.e., Sep∗A≤SepA. Conversely, SepA≤Sep∗A since II∗∗=II.(2)
It is an immediate consequence of (1) by the definition of connected degree for fuzzifying matroids.(3)
It is obvious by Theorem10 and (2).Remark 1.
The characterization of the disconnectedness for a given fuzzifying matroidM=E,II induced by a fuzzy family of circuits in [27] is as follows: M is disconnected if and only if there is a nonempty proper subset of A such that ℝIIA+ℝIIE−A=ℝIIE. From Theorems 7 and 8, it can also be characterized by the connected degree in this paper, M is disconnected if and only if ConM=0, that is, M is connected if and only if ConM≠0. From this, we can see the connected degree introduced in this paper unifies the connectedness in [27].
We now describe the concepts of this paper by various examples.Example 1.
A simple class of fuzzifying matroids are fuzzifying uniform matroids. It is a fuzzifying matroidE,II satisfying for any A,B∈2E, A=B implies IIA=IIB [29].
Consider the example that a fuzzifying uniform matroidM is a finite set E = {e1,e2,e3} and a mapping II from 2E to 0,1 defined as II∅=1, II ({e1}) = II ({e2}) = II ({e3}) = 0.5, II ({e1,e2}) = II ({e2,e3}) = II ({e1,e3}) = 0.3, II ({e1,e2,e3}) = 0.2. So, by the definition of circuit-map, ℂIIC=0 (if C∈ {∅}), 0.5 (if C∈ {{e1}, {e2}, {e3}}), 0.7 (if C∈ {{e1,e2}, {e1,e3}, {e2,e3}}), and 0.8 (if C∈ {{e1,e2,e3}}). By Definition 6, we have Sep ({e1}) = ∧ {1−ℂIC|C = {e1,e2}, {e1,e3}, {e1,e2,e3}} = 1−0.7∧1−0.7∧1−0.8=0.2. Similarly, we also have SepA=0.2 if A∈ {{e2}, {e3}, {e1,e2}, {e1,e3}, {e2,e3}}. Hence, ConM=∧ {1−SepA|A∈2E− {∅,E}} = 0.8.Example 2.
Another simple and more general class of fuzzifying matroids is fuzzifying paving matroids. It is a fuzzifying matroidE,II satisfying for any A,B∈2E, A<B implies IIA≥IIB [29].
Consider the fuzzifying matroidM=E,II given in the proof of Theorem 6 (3), which is a fuzzifying paving matroid rather than a fuzzifying uniform matroid. Similarly, we also have SepA=1/3 if A = {e2}, {e3}, {e1,e2}, {e2,e3} or {e1,e3}. Hence, ConM=∧ {1−SepA|A∈2E− {∅,E}} = 2/3.Example 3.
Similarly, we can use the examples of fuzzifying acyclic matroids and fuzzifying simple matroids introduced in [29] to illustrate the concepts of this paper, which are omitted here.Example 4.
The very important class of fuzzifying matroids are derived from fuzzy graphs, which have been discussed in Section4 in detail. In addition, we can also proved that IIGA=∧x∈Aμx (if A does not contain any cycle), 0 (otherwise). Note that when δe≡1 for any e∈V, a fuzzy graph is abbreviated to G=V,μ.
Consider the example that a fuzzifying cycle matroidE,IIG induced by G=V,μ in Figure 1, and record it as MG, where E= {e1,e2,e3,e4} is the edges set in V,μ and μe1=0.1, μe2=0.2, μe3=0.3, μe4=0.4. Then, IIGA=0 (if A∈ {{e1,e2,e3}, {e1,e2,e3,e4}}), 0.1 (if A∈ {{e1}, {e1,e2}, {e1,e3}, {e1,e4}, {e1,e3,e4}, {e1,e2,e4}}), 0.2 (if A∈ {{e2}, {e2,e3}, {e2,e4}, {e2,e3,e4}}), 0.3 (if A∈ {{e3}, {e3,e4}}), 0.4 (if A∈ {{e4}}), and 1 (if A∈ {∅}). By the definition of circuit-map, ℂIIGC=1 (if C∈ {{e1,e2,e3}}), 0.9 (if C∈ {{e1}}), 0.8 (if C∈ {{e2}}), 0.7 (if C∈ {{e3}}), 0.6 (if C∈ {{e4}}), and 0 (otherwise). By Definition 6, Sep ({e1,e2,e3}) = ∧ {1−ℂIGC|C = {e1,e4}, {e2,e4}, {e3,e4}, {e1,e2,e4}, {e1,e3,e4}, {e2,e3,e4}, {e1,e2,e3,e4}} = 1. Hence, ConMG=∧ {1−SepA|A∈2E− {∅,E}} = 0.Figure 1
The fuzzy graphV,μ.


## 6. Conclusions

This paper exemplifies an application of Polya’s plausible reasoning method (mainly analogous and generalization) in matriod theory, where we obtain some new results on 2-connectedness of fuzzifying matroids but just start from the 2-connectedness of graphs (a notion popularized for undergraduate students). We show some properties of connectedness and connected degree of fuzzifying matroids and the reasonability of the definition of connected degree and enrich the theory of fuzzifying matroids. The course of discovering the notion of connected degree of fuzzifying matroids and related results is given clearly and relatively understandably which may be benefiticial to mathematics enthusiasts and researchers in other areas who are interested to discover. There are also some work to be performed further. For example, (1) For the notion of connectedness, a fuzzy graph is either connected or not, we can consider the fuzziness degree of connectedness for a fuzzy graph analogously. (2) We can define and study connected degree of Goetschel–Voxman fuzzy matroids analogously; we can even define and study connected degree of0,1-matroids introduced in [18, 30] (a generalization of Goetschel–Voxman fuzzy matroids) analogously. (3) As we know, as an application of fuzzifying matroids, the fuzzifying greedy algorithm was presented in [23, 24], fuzzifying matroids are precisely the structures for which the very simple and efficient fuzzifying greedy algorithm works. Whether connectedness of fuzzifying matroids could be applied to some fuzzy combinatorial problems, we shall consider this problem in the future. Of course, applications in decision-making problems as in [31–34] should also be considered; (4) We are also extending our work to m-polar fuzzifying matroids by imitating reference [15].



---

*Source: 7811196-2022-05-02.xml*