# Preference Graph of Potential Method as a Fuzzy Graph

Authors: Siti Salwana Mamat; Siti Rahmah Awang; Tahir Ahmad
Journal: Advances in Fuzzy Systems
 (2020)

---

## Abstract

An autocatalytic set (ACS) is a graph. On the other hand, the Potential Method (PM) is an established graph based concept for optimization purpose. Firstly, a restricted form of ACS, namely, weak autocatalytic set (WACS), a derivation of transitive tournament, is introduced in this study. Then, a new mathematical concept, namely, fuzzy weak autocatalytic set (FWACS), is defined and its relations to transitive PM are established. Some theorems are proven to highlight their relations. Finally, this paper concludes that any preference graph is a fuzzy graph Type 5.


---

## Body

## 1. Introduction

Graph theory is rapidly moving into diverse fields such as chemistry, engineering, computer science, and operations research [1–3]. Graph has been used to model interconnections between natural and man-made systems. Dey and Pal [4] and Dey et al. [5] used graph-coloring technique to classify traffic accidental zones. Dey et al. [6, 7] solved fuzzy shortest path problems with interval Type 2 fuzzy arc lengths of a graph. Wuest et al. [8] utilized a graph to determine quality of a manufacturing program.Two structures of interest in this study are ACS and PM where both are graphs. Each one of them contains a set of vertices and a set of edges. However, the ACS is a graph such that each vertex has at least an incoming link, whereas the PM, on the contrary, must always have a vertex with a missing incoming link. The relation between these two mathematical structures has not been explored yet. Therefore, the anticipated relation is studied and presented in this paper.Firstly, a weak form of ACS, namely, weak autocatalytic set (WACS), is introduced to serve as a “bridge” between ACS and PM. The study is later expanded to the case of PM with uncertainty connections between its vertices, i.e., fuzzy edges. The idea has led to a new ACS, namely, fuzzy weak autocatalytic set (FWACS).The paper is organized as follows. Section2 provides some basic concepts and definitions associated with this study. The WACS is introduced in Section 3 and some features of WACS are presented in this section. Section 4 elaborates ACS and PM and their relation. The fuzzification of WACS is described in Section 5. Finally, the conclusion of this paper is presented in Section 6.


## 2. Preliminaries

Generally, a graph represents a relationship between objects visually. These objects are represented by vertices and their relations by edges (see Figure1).Figure 1
Königsberg bridge problem [9]. (a) The town of Königsberg. (b) Schematic representation of the area with the bridges. (c) Euler’s representation of the problem.
(a)
(b)
(c)The formal definition of a graph is given in Definition1. An example of a graph with four vertices V=v1,v2,v3,v4 is illustrated in Figure 2.Figure 2
A graph with four vertices.Definition 1.
(see [10]). A graph is a pair of sets V,E where V is the set of vertices and E is the set of edges.
Furthermore, another way to represent a graph is by its adjacency matrix. The definition of an adjacency matrix for a given graph is as follows.Definition 2.
(see [10]). An adjacency matrix of a graph G=V,E with n vertices is an n×n matrix denoted by A=aij, where aij=1 if E contains a directed edge j,i. It is an arrow pointing from vertex j to vertex i, and aij=0 otherwise.
An adjacency matrix for the graph in Figure2 is(1)A=0001100010000100.
In 1965, Lotfi Zadeh introduced a revolutionized mathematical concept, namely. fuzzy set. A fuzzy set is a refined version of a crisp set (classical set). The membership value of an element of a crisp set is 0 or 1. However, a fuzzy set employs membership value between 0 and 1 [11]. Formally, a fuzzy set A of universe X is defined by its membership function μAX as follows:(2)μAx:X0,1,such that μxA=1 if x is totally in A; μAx=0 if x is not in A; and 0<μAx<1 if x is partly in A.
Figure3 shows a membership function of a fuzzy set.
These two concepts (graph and fuzzy set) have given “birth” to a new mathematical structure, namely, fuzzy graph. Definition3 indicates that vertices and edges are both fuzzy. In other words, the vertices and edges have values between 0 and 1. Figure 4 illustrates a fuzzy graph.Figure 3
An example of a fuzzy set.Figure 4
An example of a fuzzy graph.Definition 3.
(see [12]). A fuzzy graph G=σ,μ is a pair of functions σ:S⟶0,1 and μ:S×S⟶0,1∍∀x,y∈S,μx,y≤σx∧σy.
An adjacency matrix of a fuzzy graph is defined as follows:Definition 4.
(see [12]). An adjacency matrix, A of a fuzzy graph G=V,σ,μ, is an n×n matrix defined as A=aij such that aij=μvj,vi.
The adjacency matrix for the fuzzy graph in Figure4 is(3)A=0010.20.400000.700000.50.
Blue et al. [13] further introduced five types of fuzzy graphs, i.e., taxonomy of fuzzy graphs. They argued that fuzziness can occur in several ways, namely:Type 1: fuzzy set of graphsType 2: crisp vertices and fuzzy edgesType 3: crisp vertices and edges but with fuzzy connectivityType 4: fuzzy vertices and crisp edgesType 5: crisp graph with fuzzy weight
Later, Tahir et al. [14] formalized these five types of fuzzy graphs as follows:Type 1:GF1=G1F,G2F,…,GnF where fuzziness is on GiF for i=1,2,…,nType 2:GF2=V,EF where the edges are fuzzyType 3:GF3=V,EtF,hF where both the vertices and edges are crisp but the edges have fuzzy heads and tailsType 4:GF4=VF,E where the vertices are fuzzyType 5:GF5=V,EwF where both the vertices and edges are crisp but the edges have fuzzy weights
In the following subsection, a brief review on a new mathematical concept called fuzzy autocatalytic set is presented.


### 2.1. Fuzzy Autocatalytic Set (FACS)

The concept of autocatalysis was originated in chemistry, in particular, for the description of catalytically interaction between molecules [15–17]. Further, Jain and Krishna [18] formalized the concept of an autocatalytic set (ACS) as a directed graph in which its vertices represent species and its edges represent catalytic interactions among them. The formal definition of an ACS is given as follows.Definition 5.
(see [18]). An autocatalytic set is a subgraph, each of whose vertices has at least one incoming link from vertices belonging to the same subgraph.
Some examples of ACSs are illustrated in Figure5. The simplest ACS is a vertex with 1-cycle.
The merger of fuzzy graph and autocatalytic set has led to the idea of fuzzy autocatalytic set (FACS) by Tahir et al. [14]. The formal definition of FACS is laid as follow.Figure 5
Some examples of ACS.Definition 6.
(see [14]). A fuzzy autocatalytic set is a subgraph each of whose vertices has at least one incoming link with membership value, μei∈0,1,∀ei∈E, from any other vertices belonging to the same subgraph.
An example of FACS is given in Figure6.
In the same paper, Tahir et al. [14] proved the following theorems regarding fuzzy graph and FACS.Figure 6
A FACS.Theorem 1. (see [14]).
Every crisp graph is a fuzzy graph.Theorem 2. (see [14]).
Every autocatalytic set is a fuzzy graph.Theorem 3. (see [14]).
Every fuzzy autocatalytic set is also a fuzzy graph.The relation between crisp graph, fuzzy graph, ACS, and FACS is depicted in Figure7.In general, graphs have been widely used to model various systems [19]. Graphs have been used in decision-making problems such as in industry, government, healthcare, business, and education [20]. In the next subsection, a decision-making technique called Potential Method is reviewed.Figure 7
The relation of ACS and FACS to fuzzy graph.


### 2.2. Potential Method

Potential Method is a method in decision-making process which utilizes graph. The graph is called preference. The preference graph was developed by Lavoslav Čaklović in 2002 to model pairwise comparisons between alternatives. In general, supposeV is a set of alternatives in which some preferences are being considered. If an alternative u is preferred over alternative v (denoted as u≻v), it can be presented as a directed edge from vertex v to vertex u (see Figure 8). The edge is denoted by u,v.Figure 8
Alternativeu is preferred over alternative v.If the preference is described with an intensity (e.g. equal, weak, moderate, strong, or absolute preference), then the directed edge fromv to u has a value, namely, weight, and is denoted by Fu,v. In case of an equal preference (denoted by u∼v), then Fu,v=0, and the direction of the edge is irrelevant; i.e., edge u,v can be replaced by v,u.Čaklović [21] added that a preference graph has neither loops nor parallel edges. It contains at most n2 edges [22]. The formal definition of a preference graph is given in Definition 7 as follows.Definition 7.
(see [23]). A preference graph is a triple G=V,A,F where V is a set of n∈ℕ vertices (representing alternatives), A⊆V×V is a set of directed edges, and F:A⟶ℝ is a preference flow which maps each edge u,v to the corresponding intensity, Fu,v.
Two examples of potential graph are illustrated in Figure9.
Directed graphs have appeared in connection with various optimization problems, in particular, tournament problems [24, 25]. The description of a tournament problem by means of a graph is described in the following subsection.Figure 9
Examples of potential graphs.


### 2.3. Tournament

Suppose thatn players compete in a round robin tournament whereby each player competes with all other players. In other words, for every pair of players u and v, either u beats v or v beats u and no draw is allowed [26].The outcome of a tournament can be represented by a directed graph [27, 28]. Thus, for each pair of vertices u and v in a tournament graph, there is a directed edge from u to v or from v to u, but not both. The formal definition of a tournament in form of a graph is given as follows.Definition 8.
(see [26]). A tournament graph with n vertices is a pair T=V,E where V=v1,v2,…,vn is a set of vertices and E⊂V2 is a set of ordered pairs called directed edges, so that for every two distinct vertices vi and vj either vi,vj∈E or vj,vi∈E.
Some examples of tournament graphs are illustrated in Figure10.
Kendall and Smith [29] introduced a procedure to compare between three objects A,B,C that can be represented by a triangle called triad. The orientation of edges of a triad is discussed by Harary and Moser [27], Tversky [30], and Gass [31]. The transitivity for a triad is categorized as two types, simply as transitive and intransitive. They are elaborated in the following subsections.Figure 10
Examples of tournament graphs.


#### 2.3.1. Transitivity

Consider a set of objectsA,B,C. A respondent may choose B from the pair A,B and A from the pair A,C and prefer B from B,C. His choices can be ordered as B,A,C as shown in Figure 11. The resultant orientation is said to be a transitive [27, 29].Figure 11
Transitive (acyclic).On the other hand, an intransitive orientation occurs when the respondent selectsB from the pair A,B, A from the pair A,C, and C from the pair B,C as illustrated in Figure 12. An intransitive orientation produces a cycle [29].Figure 12
Intransitive (cyclic).However, only the transitive orientation is considered and discussed in this paper.


#### 2.3.2. Transitive Tournament

An orientation of a tournament is called transitive whenevera⟶b and b⟶c; then a⟶c. In other words, if ab and bc are edges in T, then ac is also an edge in T (see Figure 13).Figure 13
A transitive orientation.A graph which contains no cycle of any length is called an acyclic graph.Definition 9.
(see [32]). A directed graph is called a directed acyclic graph if it does not contain any directed cycles.
Therefore, a transitive tournament is an acyclic graph if it contains no cycles as stated by Theorem4 as follows.Theorem 4. (see [27]).
A tournament is transitive if and only if it contains no cycles.An acyclic graph is categorized as weakly connected and defined by Skiena [33] and Préa [34] as follows.Definition 10.
(Skiena [33]). The nodes in a weakly connected digraph must all have either in-degree or out-degree of at least 1.Definition 11.
(Préa [34]). The relation which defines the weak connectivity of a directed graph if there exists a path from vertex x to vertex y or from y to x and it is not transitive.
Furthermore, there are several definitions for transitive tournament as documented in Harary and Moser [27] and Moon and Pullman [35]. However, all of them are equivalent. The following theorem lists some properties of a transitive tournament whose scores s1,s2,…,sn are in nondecreasing order.Theorem 5. (see [27]).
Given a tournamentT, the following are equivalent:(1)
T is transitive(2)
T contains no oriented cycle(3)
The score sequence ofT is 0,1,2,…,n−2,n−1(4)
T contains nn−1n−2/6 transitive triples(5)
T has exactly one Hamiltonian pathA transitive tournament has exactly a sink and a source [31]. A source is a vertex with zero in-degree; i.e., indv=0. A vertex v is called a sink if all n−1 edges ended at v. A sink is a vertex with zero out-degree; i.e., outdv=0. Figure 14 shows a transitive 4-tournament. It has no cycle, i.e., acyclic. Vertices B and D are the source and sink, respectively.A transitive tournament contains a source, i.e., a vertex with no incoming link. It is not an ACS by Definition5. In other words, a transitive tournament is “not a full pledge ACS.” The condition has led to a new “weak version” of ACS as described in detail in the following section.Figure 14
A transitive 4-tournament.


## 2.1. Fuzzy Autocatalytic Set (FACS)

The concept of autocatalysis was originated in chemistry, in particular, for the description of catalytically interaction between molecules [15–17]. Further, Jain and Krishna [18] formalized the concept of an autocatalytic set (ACS) as a directed graph in which its vertices represent species and its edges represent catalytic interactions among them. The formal definition of an ACS is given as follows.Definition 5.
(see [18]). An autocatalytic set is a subgraph, each of whose vertices has at least one incoming link from vertices belonging to the same subgraph.
Some examples of ACSs are illustrated in Figure5. The simplest ACS is a vertex with 1-cycle.
The merger of fuzzy graph and autocatalytic set has led to the idea of fuzzy autocatalytic set (FACS) by Tahir et al. [14]. The formal definition of FACS is laid as follow.Figure 5
Some examples of ACS.Definition 6.
(see [14]). A fuzzy autocatalytic set is a subgraph each of whose vertices has at least one incoming link with membership value, μei∈0,1,∀ei∈E, from any other vertices belonging to the same subgraph.
An example of FACS is given in Figure6.
In the same paper, Tahir et al. [14] proved the following theorems regarding fuzzy graph and FACS.Figure 6
A FACS.Theorem 1. (see [14]).
Every crisp graph is a fuzzy graph.Theorem 2. (see [14]).
Every autocatalytic set is a fuzzy graph.Theorem 3. (see [14]).
Every fuzzy autocatalytic set is also a fuzzy graph.The relation between crisp graph, fuzzy graph, ACS, and FACS is depicted in Figure7.In general, graphs have been widely used to model various systems [19]. Graphs have been used in decision-making problems such as in industry, government, healthcare, business, and education [20]. In the next subsection, a decision-making technique called Potential Method is reviewed.Figure 7
The relation of ACS and FACS to fuzzy graph.


## 2.2. Potential Method

Potential Method is a method in decision-making process which utilizes graph. The graph is called preference. The preference graph was developed by Lavoslav Čaklović in 2002 to model pairwise comparisons between alternatives. In general, supposeV is a set of alternatives in which some preferences are being considered. If an alternative u is preferred over alternative v (denoted as u≻v), it can be presented as a directed edge from vertex v to vertex u (see Figure 8). The edge is denoted by u,v.Figure 8
Alternativeu is preferred over alternative v.If the preference is described with an intensity (e.g. equal, weak, moderate, strong, or absolute preference), then the directed edge fromv to u has a value, namely, weight, and is denoted by Fu,v. In case of an equal preference (denoted by u∼v), then Fu,v=0, and the direction of the edge is irrelevant; i.e., edge u,v can be replaced by v,u.Čaklović [21] added that a preference graph has neither loops nor parallel edges. It contains at most n2 edges [22]. The formal definition of a preference graph is given in Definition 7 as follows.Definition 7.
(see [23]). A preference graph is a triple G=V,A,F where V is a set of n∈ℕ vertices (representing alternatives), A⊆V×V is a set of directed edges, and F:A⟶ℝ is a preference flow which maps each edge u,v to the corresponding intensity, Fu,v.
Two examples of potential graph are illustrated in Figure9.
Directed graphs have appeared in connection with various optimization problems, in particular, tournament problems [24, 25]. The description of a tournament problem by means of a graph is described in the following subsection.Figure 9
Examples of potential graphs.


## 2.3. Tournament

Suppose thatn players compete in a round robin tournament whereby each player competes with all other players. In other words, for every pair of players u and v, either u beats v or v beats u and no draw is allowed [26].The outcome of a tournament can be represented by a directed graph [27, 28]. Thus, for each pair of vertices u and v in a tournament graph, there is a directed edge from u to v or from v to u, but not both. The formal definition of a tournament in form of a graph is given as follows.Definition 8.
(see [26]). A tournament graph with n vertices is a pair T=V,E where V=v1,v2,…,vn is a set of vertices and E⊂V2 is a set of ordered pairs called directed edges, so that for every two distinct vertices vi and vj either vi,vj∈E or vj,vi∈E.
Some examples of tournament graphs are illustrated in Figure10.
Kendall and Smith [29] introduced a procedure to compare between three objects A,B,C that can be represented by a triangle called triad. The orientation of edges of a triad is discussed by Harary and Moser [27], Tversky [30], and Gass [31]. The transitivity for a triad is categorized as two types, simply as transitive and intransitive. They are elaborated in the following subsections.Figure 10
Examples of tournament graphs.


### 2.3.1. Transitivity

Consider a set of objectsA,B,C. A respondent may choose B from the pair A,B and A from the pair A,C and prefer B from B,C. His choices can be ordered as B,A,C as shown in Figure 11. The resultant orientation is said to be a transitive [27, 29].Figure 11
Transitive (acyclic).On the other hand, an intransitive orientation occurs when the respondent selectsB from the pair A,B, A from the pair A,C, and C from the pair B,C as illustrated in Figure 12. An intransitive orientation produces a cycle [29].Figure 12
Intransitive (cyclic).However, only the transitive orientation is considered and discussed in this paper.


### 2.3.2. Transitive Tournament

An orientation of a tournament is called transitive whenevera⟶b and b⟶c; then a⟶c. In other words, if ab and bc are edges in T, then ac is also an edge in T (see Figure 13).Figure 13
A transitive orientation.A graph which contains no cycle of any length is called an acyclic graph.Definition 9.
(see [32]). A directed graph is called a directed acyclic graph if it does not contain any directed cycles.
Therefore, a transitive tournament is an acyclic graph if it contains no cycles as stated by Theorem4 as follows.Theorem 4. (see [27]).
A tournament is transitive if and only if it contains no cycles.An acyclic graph is categorized as weakly connected and defined by Skiena [33] and Préa [34] as follows.Definition 10.
(Skiena [33]). The nodes in a weakly connected digraph must all have either in-degree or out-degree of at least 1.Definition 11.
(Préa [34]). The relation which defines the weak connectivity of a directed graph if there exists a path from vertex x to vertex y or from y to x and it is not transitive.
Furthermore, there are several definitions for transitive tournament as documented in Harary and Moser [27] and Moon and Pullman [35]. However, all of them are equivalent. The following theorem lists some properties of a transitive tournament whose scores s1,s2,…,sn are in nondecreasing order.Theorem 5. (see [27]).
Given a tournamentT, the following are equivalent:(1)
T is transitive(2)
T contains no oriented cycle(3)
The score sequence ofT is 0,1,2,…,n−2,n−1(4)
T contains nn−1n−2/6 transitive triples(5)
T has exactly one Hamiltonian pathA transitive tournament has exactly a sink and a source [31]. A source is a vertex with zero in-degree; i.e., indv=0. A vertex v is called a sink if all n−1 edges ended at v. A sink is a vertex with zero out-degree; i.e., outdv=0. Figure 14 shows a transitive 4-tournament. It has no cycle, i.e., acyclic. Vertices B and D are the source and sink, respectively.A transitive tournament contains a source, i.e., a vertex with no incoming link. It is not an ACS by Definition5. In other words, a transitive tournament is “not a full pledge ACS.” The condition has led to a new “weak version” of ACS as described in detail in the following section.Figure 14
A transitive 4-tournament.


## 2.3.1. Transitivity

Consider a set of objectsA,B,C. A respondent may choose B from the pair A,B and A from the pair A,C and prefer B from B,C. His choices can be ordered as B,A,C as shown in Figure 11. The resultant orientation is said to be a transitive [27, 29].Figure 11
Transitive (acyclic).On the other hand, an intransitive orientation occurs when the respondent selectsB from the pair A,B, A from the pair A,C, and C from the pair B,C as illustrated in Figure 12. An intransitive orientation produces a cycle [29].Figure 12
Intransitive (cyclic).However, only the transitive orientation is considered and discussed in this paper.


## 2.3.2. Transitive Tournament

An orientation of a tournament is called transitive whenevera⟶b and b⟶c; then a⟶c. In other words, if ab and bc are edges in T, then ac is also an edge in T (see Figure 13).Figure 13
A transitive orientation.A graph which contains no cycle of any length is called an acyclic graph.Definition 9.
(see [32]). A directed graph is called a directed acyclic graph if it does not contain any directed cycles.
Therefore, a transitive tournament is an acyclic graph if it contains no cycles as stated by Theorem4 as follows.Theorem 4. (see [27]).
A tournament is transitive if and only if it contains no cycles.An acyclic graph is categorized as weakly connected and defined by Skiena [33] and Préa [34] as follows.Definition 10.
(Skiena [33]). The nodes in a weakly connected digraph must all have either in-degree or out-degree of at least 1.Definition 11.
(Préa [34]). The relation which defines the weak connectivity of a directed graph if there exists a path from vertex x to vertex y or from y to x and it is not transitive.
Furthermore, there are several definitions for transitive tournament as documented in Harary and Moser [27] and Moon and Pullman [35]. However, all of them are equivalent. The following theorem lists some properties of a transitive tournament whose scores s1,s2,…,sn are in nondecreasing order.Theorem 5. (see [27]).
Given a tournamentT, the following are equivalent:(1)
T is transitive(2)
T contains no oriented cycle(3)
The score sequence ofT is 0,1,2,…,n−2,n−1(4)
T contains nn−1n−2/6 transitive triples(5)
T has exactly one Hamiltonian pathA transitive tournament has exactly a sink and a source [31]. A source is a vertex with zero in-degree; i.e., indv=0. A vertex v is called a sink if all n−1 edges ended at v. A sink is a vertex with zero out-degree; i.e., outdv=0. Figure 14 shows a transitive 4-tournament. It has no cycle, i.e., acyclic. Vertices B and D are the source and sink, respectively.A transitive tournament contains a source, i.e., a vertex with no incoming link. It is not an ACS by Definition5. In other words, a transitive tournament is “not a full pledge ACS.” The condition has led to a new “weak version” of ACS as described in detail in the following section.Figure 14
A transitive 4-tournament.


## 3. Weak Autocatalytic Set (WACS)

This section presents the WACS. A WACS is derived from transitive tournament. It is defined formally as follows.Definition 12.
A WACS is a non-loop subgraph in which it has a vertex with no incoming link.
Figure15 illustrates some examples of WACS.
New features of WACS are deduced. These features are inspired from the work of Skiena [33] and Préa [34] on weak connectivity. The following theorem is an immediate consequence of Definition 10 and 11.Figure 15
Examples of WACS.Theorem 6.
Every WACS is a weak connected graph.Proof.
LetG=V,E be a WACS. Therefore, by Definition 12, G contains a vertex which has no parallel edge, say, from u to v or from v to u. Every node in G has either out-degree or in-degree of at least 1. Therefore, every WACS is a weak connected digraph by Definition 10 and Definition 11.Consequently, a WACS has no Hamiltonian cycle. This particular feature leads to the following theorem.Theorem 7.
Every WACS must have at least a path, which is not closed.Proof.
LetG=V,E be a WACS. A closed path begins and ends at the same vertex. Since a WACS has a vertex with no incoming link, it produces an open path. Therefore, every WACS has at least a path which is not closed.
The graph in Figure16 shows a WACS with three vertices and not closed.
A graph can be represented in form of a matrix i.e. adjacency matrix (see Definition2). An adjacency matrix for the graph in Figure 14 is A=0110000001001110.
In a WACS, the entries of main diagonal of its adjacent matrix are all zeros. It contains a zero row, which shows that there exists a vertex with no incoming link. Hence, every WACS can be mapped to a square matrix as presented in the following theorem.Figure 16
A WACS with path, which is not closed.Theorem 8.
LetGV,E be a WACS defined by Gk=0wheni=jandei∉Eμei∈0,1wheni≠jandei∈E for k=1,2,…,n. Consider G=Gk:k=1,2,…,n be a finite set of WACS and let MFn×n=aijn×n:aij∈0,1withaii=0 be a square matrix. Define f:G⟶MFn×n∍fGk=aij. Then f is a bijective function.Proof.
(i)
Let
G
V
,
E
=
G
′
V
′
,
E
′
⟹
V
=
v
1
,
v
2
,
…
,
v
n
=
v
1
′
,
v
2
′
,
…
,
v
n
′
=
V
′
and
E
=
μ
v
j
,
v
i
i
,
j
=
1,2
,
…
,
n
=
μ
v
j
′
,
v
i
′
i
,
j
=
1,2
,
…
,
n
=
E
′
⟹
μ
v
j
,
v
i
=
a
i
j
=
a
i
j
′
=
μ
v
j
′
,
v
i
′
⟹
a
i
j
=
a
i
j
′
∴
f
is a well
−
define function
.
(ii)
f
is onto since for
a
i
j
∈
M
F
n
×
n
,
∃
G
k
∍
f
G
k
=
a
i
j
and
a
i
j
=
μ
v
i
,
v
j
for
v
i
,
v
j
∈
G
k
(iii)
Suppose
f
G
1
V
,
E
=
f
G
2
V
,
E
a
i
j
=
a
i
j
′
⟹
v
j
,
v
i
=
v
j
′
,
v
i
′
⟹
v
i
=
v
i
′
and
v
j
=
v
j
′
,
∀
i
,
j
=
1,2
,
…
,
n
⟹
G
1
V
,
E
=
G
2
V
,
E
.
∴
f
is one to oneIn general, a WACS withn vertices contains a vertex with no multiple edges. Consequently, the vertex will have n−1 edges. However, the other n−1 vertices may have multiple edges. The following theorem proves that a finite set of vertices for WACS produces a finite set of edges.Theorem 9.
IfGV,E is a WACS and V=n, then E≤n−12.Proof.
LetGV,E be a WACS and V=v1,v2,v3,…,vn. There exist a vertex with no incoming link and V=n. The most possible edges for G is(4)E≤v1,v2v1,v3v1,v4⋯v1,vnv2,v3v2,v4⋯v2,vnv3,v4⋯v3,vn⋱⋮vn−1,vn∪vn,vn−1vn,vn−2vn−1,vn−2vn,vn−3vn−1,vn−3vn−2,vn−3⋰⋮⋮⋮vn,v1vn−1,v1vn−2,v1⋯v2,v1\v1,vn,v2,vn,v3,vn,…,vn−1,vn
Hence,(5)En≤∑j=2nv1,vj+∑j=3nv2,vj+∑j=4nv3,vj+⋯+2+1+1+2+⋯+∑j=4nvj,v3+∑j=3nvj,v2+∑j=2nvj,v1−∑i=1n−1vi,vn.
Consequently,(6)E≤n2+n2−n−1=2n2−n−1=2n!2!n−2!−n−1=n!n−2!−n−1=nn−1n−2!n−2!−n−1=n2−2n+1=n−1n−1=n−12.
Therefore,E≤n−12
Hence, a WACS withn vertices has number of edges at most n−12.The following subsection establishes the relation between transitive tournament and WACS.


### 3.1. Transitive Tournament as a WACS

A tournament consists of pairwise comparisons between objects. The procedure for the comparisons is discussed in Kendall [24] and David [25]. The most possible number of edges for a tournament graph is formalized in Theorem 10 as follows.Theorem 10.
The most possible edges for a tournament graphTV,E with n vertices is n2.Proof.
SupposeTV,E is a tournament graph with n vertices.
All its possible edges can be written as a setE such that(7)E=v1,v2v1,v3v1,v4⋯v1,vnv2,v3v2,v4⋯v2,vnv3,v4⋯v3,vn⋱⋮vn−1,vn,and the number of edges of E is(8)En=v1,v2v1,v3v1,v4⋯v1,vnv2,v3v2,v4⋯v2,vnv3,v4⋯v3,vn⋱⋮vn−1,vn,En≤∑j=2nv1,vj+∑j=3nv2,vj+∑j=4nv3,vj+⋯+2+1.
In particular,(9)En=n−1+n−2+⋯+2+12En=n−1+n−2+⋯+2+1+n−1+n−2+⋯+2+1=n−1+n−2+⋯+2+1+1+2+⋯+n−2+n−1=n+n+n+⋯+n=nn−1.
Thus,
E
n
=
n
n
−
1
/
2
=
n
2.
Such that
v
i
,
v
j
means
v
i
,
v
j
or
v
j
,
v
i.
Hence, the most possible number of edges forTV,E is n2.A comparison number of edges between WACS and transitive tournament is established, namely the number of edges produced by a tournament is less than the number of edges produced by a WACS with respect to a given graph. The following lemma is needed.Lemma 1.
n
2
<
n
−
1
2
for
n
>
1.Proof.
(10)
n
2
=
n
!
2
!
n
−
2
!
=
n
n
−
1
n
−
2
!
2
!
n
−
2
!
=
n
n
−
1
2
!
=
n
n
−
1
2
=
n
2
n
−
1
<
n
−
1
n
−
1
for
n
>
1
since
n
2
=
n
−
1
+
1
2
=
n
−
1
2
+
1
2
<
n
−
1
+
1
2
whenever
n
>
1
=
n
−
1
2
Therefore,n2<n−12.Consequently, the relation between a transitive tournament and a WACS is established by the following theorem.Theorem 11.
Every transitive tournament is a WACS.Proof.
Firstly, a transitive tournament is guaranteed to have a vertex with no incoming link by Theorem4 as well as no loops by Theorem 5. Furthermore, it contains n2 number of edges. Theorem 9 and Theorem 10 guarantee that the possible maximum number of edges produced by a WACS is n−12 for the same number of n vertices. Therefore, the number of edges for a transitive tournament will not exceed the number of edges of a WACS by Lemma 1. Thus, every transitive tournament is a WACS by Definition 12.Figure17 depicts the relation between transitive tournament and ACS.The aim of this paper is to establish the relation between ACS and PM. In the following section, the preference graph of Potential Method (PM) is reviewed. In this work, we use the term “potential graph” in short to refer the preference graph of the Potential Method. A brief definition of PM are presented in Section2.2. There are two types of orientation as pointed in Section 2.3.1. In this paper, we consider the transitive orientation for the potential graph.Figure 17
Transitive tournament is a WACS.


## 3.1. Transitive Tournament as a WACS

A tournament consists of pairwise comparisons between objects. The procedure for the comparisons is discussed in Kendall [24] and David [25]. The most possible number of edges for a tournament graph is formalized in Theorem 10 as follows.Theorem 10.
The most possible edges for a tournament graphTV,E with n vertices is n2.Proof.
SupposeTV,E is a tournament graph with n vertices.
All its possible edges can be written as a setE such that(7)E=v1,v2v1,v3v1,v4⋯v1,vnv2,v3v2,v4⋯v2,vnv3,v4⋯v3,vn⋱⋮vn−1,vn,and the number of edges of E is(8)En=v1,v2v1,v3v1,v4⋯v1,vnv2,v3v2,v4⋯v2,vnv3,v4⋯v3,vn⋱⋮vn−1,vn,En≤∑j=2nv1,vj+∑j=3nv2,vj+∑j=4nv3,vj+⋯+2+1.
In particular,(9)En=n−1+n−2+⋯+2+12En=n−1+n−2+⋯+2+1+n−1+n−2+⋯+2+1=n−1+n−2+⋯+2+1+1+2+⋯+n−2+n−1=n+n+n+⋯+n=nn−1.
Thus,
E
n
=
n
n
−
1
/
2
=
n
2.
Such that
v
i
,
v
j
means
v
i
,
v
j
or
v
j
,
v
i.
Hence, the most possible number of edges forTV,E is n2.A comparison number of edges between WACS and transitive tournament is established, namely the number of edges produced by a tournament is less than the number of edges produced by a WACS with respect to a given graph. The following lemma is needed.Lemma 1.
n
2
<
n
−
1
2
for
n
>
1.Proof.
(10)
n
2
=
n
!
2
!
n
−
2
!
=
n
n
−
1
n
−
2
!
2
!
n
−
2
!
=
n
n
−
1
2
!
=
n
n
−
1
2
=
n
2
n
−
1
<
n
−
1
n
−
1
for
n
>
1
since
n
2
=
n
−
1
+
1
2
=
n
−
1
2
+
1
2
<
n
−
1
+
1
2
whenever
n
>
1
=
n
−
1
2
Therefore,n2<n−12.Consequently, the relation between a transitive tournament and a WACS is established by the following theorem.Theorem 11.
Every transitive tournament is a WACS.Proof.
Firstly, a transitive tournament is guaranteed to have a vertex with no incoming link by Theorem4 as well as no loops by Theorem 5. Furthermore, it contains n2 number of edges. Theorem 9 and Theorem 10 guarantee that the possible maximum number of edges produced by a WACS is n−12 for the same number of n vertices. Therefore, the number of edges for a transitive tournament will not exceed the number of edges of a WACS by Lemma 1. Thus, every transitive tournament is a WACS by Definition 12.Figure17 depicts the relation between transitive tournament and ACS.The aim of this paper is to establish the relation between ACS and PM. In the following section, the preference graph of Potential Method (PM) is reviewed. In this work, we use the term “potential graph” in short to refer the preference graph of the Potential Method. A brief definition of PM are presented in Section2.2. There are two types of orientation as pointed in Section 2.3.1. In this paper, we consider the transitive orientation for the potential graph.Figure 17
Transitive tournament is a WACS.


## 4. Transitive Potential Graph

The following example is obtained from Čaklović and Kurdija [23] with some additional information to illustrate a transitive orientation for the potential graph.Example 1.
Leta,b,candd be preference items. Assume the following preferences over a,b,c,andd.(i)
a is preferred to b by 1.(ii)
a is better than c by 2.(iii)
a is preferred to d by 4.(iv)
b is better than c by 1.(v)
b is better than d by 3.(vi)
c is more preferred to d by 2
In short, the preferences area≻b,a≻c,a≻d,b≻c,b≻d,andc≻d with intensities of 1, 2, 4, 1, 3, and 2, respectively. The following are the edges of the preferences:(i)
Edgea,b with flow Fa,b=1(ii)
Edgea,c with flow Fa,c=2(iii)
Edgea,d with flow Fa,d=4(iv)
Edgeb,c with flow Fb,c=1(v)
Edgeb,d with flow Fb,d=3(vi)
Edgec,d with flow Fc,d=2
The transitive potential graph is illustrated in Figure18. The vertices represent the preference items a,b,c, and d. The intensity value for an edge represents the strength between two preference items.
Clearly, any transitive potential graph contains no cycle of any length. This situation leads to the following theorem.Figure 18
Transitive potential graph.Theorem 12.
A potential graph is transitive if and only it contains no cycles.Proof.
⟹ Assume a potential graph G is transitive but contains a cycle v1,v2,…,vn,v1. For n=2,G contains parallel arcs v1v2 and v2v1, thus contradicting G being a potential graph. Further, for n≥3, v1v2 and v2v3 are arcs; transitivity implies v1v3 is an arc. Now we know that v1v3 is an arc, and since v3v4 is an arc, again transitivity implies v1v4 is an arc. We reason like this, n−2 times to conclude that v1vk is an arc. However, vkv1 is also an arc of the digraph since it is part of the cycle. Thus, G contains parallel arcs v1vk and vkv1, contradicting G being a potential graph.
⟸ Assume a potential graph G contains no cycle. Suppose G contains arcs uv and vw. We know u≠w since G contains no parallel arcs. The potential graph cannot have wu as an arc because if it did, it would contain the cycle u,v,w,u. Since it is a potential graph and u≠w, either uw or wu is an arc. Thus, uw is an arc. Hence, G is transitive.Some examples of transitive potential graphs are shown in Figure19.Thus, a transitive potential graph is indeed a WACS and presented in the following theorem.Figure 19
Examples of transitive potential graphs.Theorem 13.
Every transitive potential graph is a WACS.Proof.
A transitive potential graph has neither loops nor parallel edges. It is a weak connected graph by Theorem6. Hence, it contains no cycle of any length as indicated by Theorem 12. Thus, it produces an open path by Theorem 7. Therefore, by Definition 12 every transitive potential graph is a WACS.Potential graph usually arises from optimization or multicriteria problem. Hence, such transformed problem can be studied as a special graph, namely, WACS, rigorously. A WACS is a crisp graph since its edges are either 0 or 1. The following section discusses the relation of WACS and fuzzy graph.


### 4.1. Weak Autocatalytic Set as Fuzzy Graph

The concept of fuzzy graph is the fuzzification of the crisp graph using fuzzy set. A fuzzy graph is a replication of a crisp graph [36]. Theorem 14 proves that WACS is a special case of a fuzzy graph.Theorem 14.
Every WACS is a fuzzy graph.Proof.
Every crisp graph is a fuzzy graph by Theorem1. Therefore, every WACS is also a fuzzy graph since WACS is just a special kind of a crisp graph.A WACS is a crisp graph. All crisp graphs are fuzzy but not the other way around. Therefore the converse of the above theorem is not true.The following theorem is an immediate consequence of Theorem14.Theorem 15.
Every transitive potential graph is a fuzzy graph.Proof.
Every transitive potential graph is a WACS by Theorem13. Hence, every WACS is a fuzzy graph by Theorem 14. Consequently, every transitive potential graph is a fuzzy graph.The converse of Theorem15 is not true by similar argument as Theorem 14 earlier; i.e., all crisp graphs are fuzzy but not the other way around.In the following section, a new concept called fuzzy weak autocatalytic set is outlined.


## 4.1. Weak Autocatalytic Set as Fuzzy Graph

The concept of fuzzy graph is the fuzzification of the crisp graph using fuzzy set. A fuzzy graph is a replication of a crisp graph [36]. Theorem 14 proves that WACS is a special case of a fuzzy graph.Theorem 14.
Every WACS is a fuzzy graph.Proof.
Every crisp graph is a fuzzy graph by Theorem1. Therefore, every WACS is also a fuzzy graph since WACS is just a special kind of a crisp graph.A WACS is a crisp graph. All crisp graphs are fuzzy but not the other way around. Therefore the converse of the above theorem is not true.The following theorem is an immediate consequence of Theorem14.Theorem 15.
Every transitive potential graph is a fuzzy graph.Proof.
Every transitive potential graph is a WACS by Theorem13. Hence, every WACS is a fuzzy graph by Theorem 14. Consequently, every transitive potential graph is a fuzzy graph.The converse of Theorem15 is not true by similar argument as Theorem 14 earlier; i.e., all crisp graphs are fuzzy but not the other way around.In the following section, a new concept called fuzzy weak autocatalytic set is outlined.


## 5. Fuzzy Weak Autocatalytic Set

The fuzzification of WACS has led to a new structure, namely, fuzzy weak autocatalytic set (FWACS). The definition of FWACS is formalized in Definition13. An example of a FWACS is shown in Figure 20.Figure 20
A FWACS.Definition 13.
A fuzzy weak autocatalytic set (FWACS) is a WACS such that every edgeei has a membership value, μei∈0,1forei∈E.
A WACS is a crisp graph and it is a special type of FWACS as presented in Theorem16.Theorem 16.
Every WACS is a FWACS.Proof.
Every crisp graph is a fuzzy graph by Theorem1. Thus, every ACS is a special case of FACS; hence every WACS is FWACS.Furthermore, the following theorem is an immediate consequence of Theorem16.Theorem 17.
Every FWACS is a fuzzy graph.Proof.
Theorem1 established that every crisp graph is a fuzzy graph. Every FACS is also a fuzzy graph by Theorem 3, which immediately implies every FWACS is fuzzy graph.There are 5 types of crisp graph as documented in Blue et al. [13]. Every crisp graph is a fuzzy graph and the converse is not true. Not all crisp graphs are autocatalytic sets. Clearly, the converse of Theorem 17 is not true either.We have proven that a transitive potential graph is a WACS and a special case of fuzzy graph. The next section introduces preferences flow on edges.


### 5.1. Fuzzy Edges of Transitive Potential Graph

Consider the potential graph in Figure18. The adjacency matrix for the graph is(11)A=0111001100000010.The transformation of the preference flows to fuzzy membership values is described in the next subsection.


#### 5.1.1. Membership Value of Fuzzy Edge via Linear Transformation

The preference flows interval of Example1 is transformed to fuzzy membership values linearly as illustrated in Figure 21.Figure 21
Linear transformation of preference flows.In Example1, the interval [0, 4] is used to indicate the strength of alternatives. Table 1 lists the transformed intensity preference to fuzzy membership values.Table 1
Fuzzy membership value of preference scale.
Preference scale
Intensity preference of potential method
Fuzzy number
Equal
0
0
Weak
1
0.25
Fairly strong
2
0.5
Very strong
3
0.75
Absolute
4
1The crisp and fuzzy graphs of Example1 are illustrated in Figure 22.Figure 22
Crisp and fuzzy graphs of Example1. (a) Transitive potential graph. (b) FWACS.
(a)
(b)The same color and thickness of each edge in the crisp graph (see Figure22(a)) indicate that the connectivity among vertices is considered the same. The value 1 is assigned when there is an edge between two vertices. If there is no edge, the value 0 is given.Figure22(b) illustrates the fuzzy graph. The edges have different “strengths” which are determined by their membership values. Furthermore, the greater the membership value, the stronger the connection between two vertices of the graph. Hence, different thickness and color of an edge represent the strength connection of its vertices.Thus, the adjacency matrix for the FWACS is(12)A=00.250.51000.250.750000000.50.In the following subsection, we present the relation between transitive potential graph and FWACS.


### 5.2. Transitive Potential Graph as FWACS

The relation between transitive potential graph and FWACS can be observed immediately. The relation is formalized in the following theorem.Theorem 18.
Every transitive potential graph is a FWACS.Proof.
Theorem13 proves that a transitive potential graph is a WACS. A transitive potential graph is a fuzzy graph by Theorem 14. The edges are fuzzy with membership values of [0, 1]. Therefore, every transitive potential graph is a FWACS by Definition 13.Every FWACS is a fuzzy graph by Theorem17. But the converse of Theorem 15 is not true; i.e. a fuzzy graph is not necessarily a transitive potential graph. Consequently, the converse of Theorem 18 is not true either.


### 5.3. Preference Graph as Fuzzy Graph Type 5

As a matter of fact, the general version of Theorem18 can be deduced directly from the recent definition of preference graph (see Definition 7) introduced by Čaklović and Kurdija [23].Theorem 19.
Every preference graph is a fuzzy graph Type 5.Proof.
LetGV,A,F be a preference graph as defined by Definition 7. Consider the preference flow F:A⟶ℝ as given in Definition 7. The ℝ is homeomorphic to (0, 1), i.e. ℝ≅0,1 [37]. But then, 0,1⊂0,1; hence the preference flow F can be written as F:A⟶0,1⊂0,1 since ℝ≅0,1. Consequently, GV,A,F is now a fuzzy graph Type 5 as categorized by Blue et al. [13] and Tahir et al. [14].A fuzzy graph Type 5 is a crisp graph with fuzzy weights for its edges defined in Blue et al. [13]. On the other hand, a preference graph is a triple G=V,A,F where V is a set of n∈ℕ vertices (representing alternatives), A⊆V×V is a set of directed edges, and F:A⟶ℝ is a preference flow which maps each edge u,v to the corresponding intensity, Fu,v, as stated in Definition 7. However, fuzzy graph Type 5 is more general than preference graph since the former can accommodate directed or undirected edges. Hence, it is quite obvious that every preference graph is a fuzzy graph Type 5 and not the converse.Figure23 summarizes the relation between ACS, WACS, FACS, and FWACS.Figure 23
A schematic diagram to illustrate the relation between preference and fuzzy graphs.


## 5.1. Fuzzy Edges of Transitive Potential Graph

Consider the potential graph in Figure18. The adjacency matrix for the graph is(11)A=0111001100000010.The transformation of the preference flows to fuzzy membership values is described in the next subsection.


### 5.1.1. Membership Value of Fuzzy Edge via Linear Transformation

The preference flows interval of Example1 is transformed to fuzzy membership values linearly as illustrated in Figure 21.Figure 21
Linear transformation of preference flows.In Example1, the interval [0, 4] is used to indicate the strength of alternatives. Table 1 lists the transformed intensity preference to fuzzy membership values.Table 1
Fuzzy membership value of preference scale.
Preference scale
Intensity preference of potential method
Fuzzy number
Equal
0
0
Weak
1
0.25
Fairly strong
2
0.5
Very strong
3
0.75
Absolute
4
1The crisp and fuzzy graphs of Example1 are illustrated in Figure 22.Figure 22
Crisp and fuzzy graphs of Example1. (a) Transitive potential graph. (b) FWACS.
(a)
(b)The same color and thickness of each edge in the crisp graph (see Figure22(a)) indicate that the connectivity among vertices is considered the same. The value 1 is assigned when there is an edge between two vertices. If there is no edge, the value 0 is given.Figure22(b) illustrates the fuzzy graph. The edges have different “strengths” which are determined by their membership values. Furthermore, the greater the membership value, the stronger the connection between two vertices of the graph. Hence, different thickness and color of an edge represent the strength connection of its vertices.Thus, the adjacency matrix for the FWACS is(12)A=00.250.51000.250.750000000.50.In the following subsection, we present the relation between transitive potential graph and FWACS.


## 5.1.1. Membership Value of Fuzzy Edge via Linear Transformation

The preference flows interval of Example1 is transformed to fuzzy membership values linearly as illustrated in Figure 21.Figure 21
Linear transformation of preference flows.In Example1, the interval [0, 4] is used to indicate the strength of alternatives. Table 1 lists the transformed intensity preference to fuzzy membership values.Table 1
Fuzzy membership value of preference scale.
Preference scale
Intensity preference of potential method
Fuzzy number
Equal
0
0
Weak
1
0.25
Fairly strong
2
0.5
Very strong
3
0.75
Absolute
4
1The crisp and fuzzy graphs of Example1 are illustrated in Figure 22.Figure 22
Crisp and fuzzy graphs of Example1. (a) Transitive potential graph. (b) FWACS.
(a)
(b)The same color and thickness of each edge in the crisp graph (see Figure22(a)) indicate that the connectivity among vertices is considered the same. The value 1 is assigned when there is an edge between two vertices. If there is no edge, the value 0 is given.Figure22(b) illustrates the fuzzy graph. The edges have different “strengths” which are determined by their membership values. Furthermore, the greater the membership value, the stronger the connection between two vertices of the graph. Hence, different thickness and color of an edge represent the strength connection of its vertices.Thus, the adjacency matrix for the FWACS is(12)A=00.250.51000.250.750000000.50.In the following subsection, we present the relation between transitive potential graph and FWACS.


## 5.2. Transitive Potential Graph as FWACS

The relation between transitive potential graph and FWACS can be observed immediately. The relation is formalized in the following theorem.Theorem 18.
Every transitive potential graph is a FWACS.Proof.
Theorem13 proves that a transitive potential graph is a WACS. A transitive potential graph is a fuzzy graph by Theorem 14. The edges are fuzzy with membership values of [0, 1]. Therefore, every transitive potential graph is a FWACS by Definition 13.Every FWACS is a fuzzy graph by Theorem17. But the converse of Theorem 15 is not true; i.e. a fuzzy graph is not necessarily a transitive potential graph. Consequently, the converse of Theorem 18 is not true either.


## 5.3. Preference Graph as Fuzzy Graph Type 5

As a matter of fact, the general version of Theorem18 can be deduced directly from the recent definition of preference graph (see Definition 7) introduced by Čaklović and Kurdija [23].Theorem 19.
Every preference graph is a fuzzy graph Type 5.Proof.
LetGV,A,F be a preference graph as defined by Definition 7. Consider the preference flow F:A⟶ℝ as given in Definition 7. The ℝ is homeomorphic to (0, 1), i.e. ℝ≅0,1 [37]. But then, 0,1⊂0,1; hence the preference flow F can be written as F:A⟶0,1⊂0,1 since ℝ≅0,1. Consequently, GV,A,F is now a fuzzy graph Type 5 as categorized by Blue et al. [13] and Tahir et al. [14].A fuzzy graph Type 5 is a crisp graph with fuzzy weights for its edges defined in Blue et al. [13]. On the other hand, a preference graph is a triple G=V,A,F where V is a set of n∈ℕ vertices (representing alternatives), A⊆V×V is a set of directed edges, and F:A⟶ℝ is a preference flow which maps each edge u,v to the corresponding intensity, Fu,v, as stated in Definition 7. However, fuzzy graph Type 5 is more general than preference graph since the former can accommodate directed or undirected edges. Hence, it is quite obvious that every preference graph is a fuzzy graph Type 5 and not the converse.Figure23 summarizes the relation between ACS, WACS, FACS, and FWACS.Figure 23
A schematic diagram to illustrate the relation between preference and fuzzy graphs.


## 6. Conclusion

This paper has introduced a novel definition of weak version of ACS, namely, WACS. The WACS is originally derived from transitive tournament which serves as a “bridge” between PM and ACS. The WACS has offered some new insights into PM. Furthermore, the FWACS is defined for PM with uncertainty where the edges are fuzzy. Finally, we proved that any preference graph of PM is a fuzzy graph Type 5.In short, the major thrust of this paper is to materialize the framework proposed by Čaklović [21, 22] for PM. The developed FWACS is able to handle multicriteria decision making (MCDM) of uncertainty problems. Some of them can be found in Siti Salwana et al. [38].



---

*Source: 8697890-2020-02-19.xml*