势方法的模糊偏好图

抽象

自动催化集（ACS）是一个图。另一方面，势方法（PM）是一种基于图的优化概念。首先，本文引入了一个约束形式，即弱自催化集（WACS），它是传递竞赛的一个派生。然后，定义了一个新的数学概念，即模糊弱自催化集（FWACS），并建立了它与传递PM的关系。一些定理被证明突出了它们之间的关系。最后，本文得出结论：任何偏好图都是5型模糊图。

一。介绍

图论正迅速发展到不同的领域，如化学、工程、计算机科学和运筹学[1个–三]. 图被用来模拟自然系统和人为系统之间的相互联系。德伊和帕尔[4个]以及Dey等人。[5个]利用图着色技术对交通事故区域进行分类。Dey等人。[6个,7个]解决模糊最短路径问题的曲线图的间隔类型2模糊弧长。Wuest等。[八]所利用的图表确定的制造程序的质量。

在这项研究中有两个有趣的结构是ACS和PM，它们都是图。其中每个包含一组顶点和一组边。然而，ACS是这样一个图，每个顶点至少有一个传入链接，而PM则相反，必须始终有一个缺少传入链接的顶点。这两种数学结构之间的关系尚未得到探讨。因此，本文研究并提出了预期关系。

首先，ACS的弱势形态，即弱自催化集（WACS），引入作为ACS和PM之间的“桥梁”。这项研究后来扩大到PM与它的顶点，即模糊边缘之间的连接不确定性的情况下。这个想法导致了一个新的ACS，即模糊弱自催化集（FWACS）。

论文组织如下。部分2个提供与本研究相关的一些基本概念和定义。该WACS将在第出台三并介绍了WACS的一些特点。剖面图4个阐述ACS与PM及其关系。本节描述了WACS的模糊性5个。最后，本文的结论部分中提出6个。

2。预备工作

一般来说，图直观地表示了对象之间的关系。这些对象由顶点表示，它们之间的关系由边表示(见图)1个).

图的正式定义在定义中给出1个。具有四个顶点的图的一个例子 如图所示2个。

定义1。(见[10])。图是一对集合 在哪里是一组顶点和是一组边。
此外，另一种方式来表示的曲线图是由它的邻接矩阵。邻接矩阵的一个给定图中的定义如下。

定义2。(见[10])。的图的邻接矩阵 具有顶点是矩阵表示为在哪里如果包含有向边 。它是从顶点指向箭头到顶点 ,和否则。
图中图的邻接矩阵2个是 1965年，洛菲·扎德提出了一个革命性的数学概念，即。模糊集。fuzzy集是crisp集（经典集）的精化版本。脆集元素的成员值为0或1。然而，模糊集的隶属度值在0到1之间[11]. 形式上，一个模糊集宇宙是由它的隶属函数定义的如下: 这样μ 如果十完全是在一个;如果十不在一个；和如果十部分是在一个。
数字三显示模糊集的隶属函数。
这两个概念（图和模糊集）产生了一种新的数学结构，即模糊图。定义三指示顶点和边都是模糊的。换句话说，顶点和边的值介于0和1之间。数字4个示出了模糊图。

定义3。(见[12]). 模糊图 是一对函数和 。
一个模糊图的邻接矩阵的定义如下：

定义4。(见[12])。邻接矩阵，一个模糊图的 ,是一个矩阵定义为这样 。
对于图的模糊图的邻接矩阵4个是 Blue等人。[13]进一步导入五种类型的模糊的图，即，模糊图的分类学的。他们认为，模糊性可以在几个方面，即发生：类型1：模糊集图表类型2:清晰的顶点和模糊的边类型3：清晰的顶点和边，但具有模糊的连接性类型4：模糊顶点和清晰边类型5：脆图形模糊重量后来，塔希尔等。[14]形式化这些五种类型模糊图形如下：类型1： 其中，模糊性是对于类型2： 边缘模糊的地方类型3： 其中顶点和边都很清晰，但边有模糊的头和尾类型4： 顶点是模糊的类型五： 顶点和边都是脆的但边的权值是模糊的在接下来的小节中，我们将简要介绍一个新的数学概念，称为模糊自催化集。

2.1条。模糊自催化集

自催化的概念起源于化学，特别是用于催化相互作用的分子[之间的描述15–17]. 此外，耆那和克里希纳[18]将自催化集（ACS）的概念形式化为一个有向图，其顶点表示物种，其边表示物种之间的催化相互作用。ACS的形式定义如下。

定义5。(见[18])。自催化组是子图的每个其顶点具有属于同一子图的顶点的至少一个输入链接。
acs的一些例子如图所示5个。最简单的是ACS与1-周期的顶点。
模糊图与自催化集的结合，使Tahir等人产生了模糊自催化集(FACS)的概念。[14]. FACS的形式定义如下。

定义6。(见[14])。模糊自催化组是一个子图的每个其顶点具有隶属函数值的至少一个输入链路的， ,从属于同一子图的任何其他顶点。
FACS的一个例子在图中给出6个。
在相同的纸，塔希尔等。[14证明了以下关于模糊图和FACS的定理。

定理1。（见[14])。每个清晰的图都是一个模糊的图。

定理2（见[14])。每一套催化是一个模糊图。

定理3。（见[14])。每一个模糊集催化也是一个模糊的曲线图。

图中描述了crisp图、fuzzy图、ACS和FACS之间的关系7个。

在一般情况下，图形已被广泛应用于各种系统进行建模[19]. 图表已用于工业、政府、医疗保健、商业和教育等决策问题[20]. 在下一小节中，将回顾一种称为潜在方法的决策技术。

2.2。电位法

潜在方法是在决策过程的方法，其利用图。该图被称为偏好。偏好曲线是由LavoslavČaklović于2002年开发出替代品之间的两两比较的模型。在一般情况下，假设是一组，其中一些偏好正在考虑的替代方案。如果替代优先于替代方案（表示为 ),它可以呈现为从顶点的有向边到顶点（见图八).边缘表示为 。

如果优选的是的具有的强度所描述（例如相等的，弱，中等，强，或绝对优先级），则引导从边缘至有一个值，即重量，并用 。若偏好相同(用表示) ),然后与边缘的方向是不相关的;即，边缘 可以被替换 。

Čaklović[21]补充说的偏好图既没有环路，也不平行的边缘。它包含最多边缘[22]. 定义中给出了偏好图的形式定义7个如下。

定义7。(见[23])。甲偏好图表是一个三 在哪里是一套顶点（表示备选方案），是一组有向边，并是其中每个边缘映射的偏好流 达到相应的强度， 。
电位曲线图的两个例子在图中示出9个。
向图已经出现在各种优化问题的连接，特别是比赛的问题[24,25]。用一个图来描述一个竞赛问题，在下面的小节中进行描述。

2.3条。锦标赛

假设球员在一个循环赛中竞争，每个球员都与其他所有球员竞争。换句话说，对每一对选手来说和 ,要么节拍要么节拍没有平局允许[26]。

锦标赛的结果可用有向图表示[27,28]。因此，对于每一对顶点的和在比赛图中，有一条来自的有向边至或来自至 ,但不能同时使用。以图形的形式的比赛的正式定义如下给出。

定义8。(见[26]). 具有顶点是一对 在哪里 是一组顶点和是一组有序对被称为有向边，因此，每两个不同的顶点和要么 要么 。
一些锦标赛图的例子如图所示10。
肯德尔和史密斯[29]介绍了比较三个对象的过程 可以用一个叫做三和弦的三角形来表示。Harary和Moser讨论了空间坐标系边缘的方向[27]，特沃斯基[三十]，和盖斯[31]. 三和弦的及物性分为两类，即及物性和不及物性。它们在下面的小节中详细阐述。

2.3.1。及物

考虑一组对象 。答辩人可选用从所述一对 和从所述一对 更喜欢从 。他的选择可以是 如图所示11. 结果方向被称为传递的[27,29]。

在另一方面，一个不及取向发生申请人选择时从所述一对 , 从所述一对 ,和从所述一对 如图所示12。一个不及取向产生一个周期[29]。

然而，本文只考虑和讨论了及物性取向。

2.3.2条。传递竞赛

比赛的方向被称为传递时和 ;然后 。换句话说，如果和边缘在吗 ,然后也是一个优势（见图13).

不包含任何长度的循环的图称为无循环图。

定义9。(见[32])。有向图被称为向无环图，如果它不包含任何有向圈。
因此，一个传递比赛是一个非循环图，如果它不包含循环通过定理陈述4个如下。

定理4。（见[27])。当且仅当锦标赛不包含循环时，它才是可传递的。

摘要非循环图是一类弱连通图，由Skiena定义[33]还有普雷亚[34]如下所示。

定义10。（斯基纳）[33])。在弱连接有向图中的节点必须都具有无论是在度或出度至少为1的。

定义11。（普雷亚）[34]). 定义有向图的弱连通性的关系到顶点或来自至它是不可传递的。
此外，在Harary和Moser [27]和月亮和普尔曼[35]。然而，所有这些都是等价的。下面的定理列出了传递比赛成绩，其某些特性 都是非保密的。

定理5（见[27])。给定一个比赛 ,以下是等价的：（一） 是可传递的（二） 不包含面向周期（三）的得分顺序是 （四） 包含传递三元组（五） 恰好有一个哈密顿路径

可传递比赛正好具有一个水槽和一个源[31]。源极与入度为零的顶点;即， 。一个顶点被称为水槽在边缘结束 。信宿是具有零出度顶点;即， 。数字14显示一个可传递的4-锦标赛。它没有周期，即无环。顶点和是源和接收器，分别。

传递锦标赛包含一个源，即一个没有传入链接的顶点。从定义上讲，它不是ACS5个。换句话说，一个传递性的锦标赛“不是一个完全的ACS承诺”。该条件导致了新的ACS的“弱版本”，将在下一节中详细描述。

三。弱自催化装置

本节介绍WACS。WACS是由传递竞赛导出的。它的形式定义如下。

定义12。WACS是一个非循环子图，其中有一个顶点没有传入链接。
数字15示出WACS的一些例子。
推导了WACS的新特性。这些特征的灵感来源于斯基纳的作品[33]还有普雷亚[34]弱连接。下面的定理是定义的一个直接后果10和11。

定理6。每个WACS都是一个弱连通图。

证明。让 是WACS。因此，通过定义12,包含一个没有平行边的顶点，比如说，从至或来自至 。在每个节点至少有1的向外度或向内度。因此，根据定义，每个WACS都是弱连通有向图10和定义11。

因此，WACS没有哈密顿圈。这种特殊的功能，导致下面的定理。

定理7。每个wac必须至少有一个路径，该路径未关闭。

证明。让 做一个WACS。一条封闭的路径在同一个顶点开始和结束。由于WACS有一个顶点，没有传入链接，因此它产生一个开放路径。因此，每个wac至少有一条未闭合的路径。
图中的图形16显示带有三个顶点的水冷式空调系统，而不是关闭。
图可以用矩阵的形式表示，即邻接矩阵（见定义2个).图中图的邻接矩阵14是
在WACS中，相邻矩阵主对角线的元素都是零。它包含一个零行，这表明存在一个没有传入链接的顶点。因此，每个WACS都可以映射到一个方阵，如下面的定理所示。

定理8。让 被一个WACS由下式定义对于 。考虑 是一个有限的WACS集 方阵。定义 。然后是一个双射函数。

证明。（一） （ⅱ） （三）

一般来说顶点包含一个没有多条边的顶点。因此，顶点将边缘。然而,其他顶点可能有多个边缘。以下定理证明的有限集合为WACS顶点产生的有限集合的边缘。

定理9。如果 是WACS和 ,然后 。

证明。让 是WACS和 。存在一个顶点，没有收到的链接和 。对于最有可能的边缘克是 因此， 所以， 因此，
因此，与WACS顶点最多有个边 。

以下款规定传递锦标赛，WACS之间的关系。

3.1。作为WACS的传递性锦标赛

甲比赛由对象之间的成对比较。用于比较的过程在肯德尔[讨论24]还有大卫[25]. 竞赛图的最可能边数是在定理中形式化的10如下。

定理10。竞赛图的最可能边 具有顶点是

证明。假设 是一个带有顶点。

所有可能的边都可以写成一个集合这样 和的边的数量是 特别地， 。
。
因此，对于 是 。

建立了WACS与传递巡回赛的边数比较，即在给定的图上，巡回赛产生的边数小于WACS产生的边数。需要以下引理。

引理1。 。

证明。 因此， 。

因此，一个传递比赛和WACS之间的关系由下面的定理成立。

定理11。每个传递比赛是一个水冷式空调系统。

证明。首先，利用定理，保证了传递竞赛图的顶点不存在传入链接4个以及无环路由定理5个. 此外，它还包含边数。定理9个和定理10保证由WACS产生边缘的可能最大数目是对于相同数量的顶点。因此，传递巡回赛的边的数量将不超过引理WACS的边的数量1个。因此，每个传递赛事是由WACS定义12。

数字17描绘传递比赛和ACS之间的关系。

本文的目的是建立ACS与PM之间的关系。在接下来的章节中，我们将回顾势能法的偏好图。在这项工作中，我们使用术语“势图”简而言之指的是势方法的偏好图。本节给出了PM的简要定义2.2。有两种类型的定向如第指出2.3.1. 本文考虑势图的传递方向。

四。传递势图

下面的例子是从Čaklović和Kurdija [获得23]用一些附加信息来说明势图的传递方向。

实施例1。让是首选项。假设在接下来的喜好（一） 优选的是按1。（ⅱ） 比到2点。（三） 优选的是到4点。（ⅳ） 比按1。（五） 比到3点。（ⅵ） 更优选的是2总之，偏好强度分别为1、2、4、1、3和2。以下是首选项的边缘：（一）边缘 与流（ⅱ）边缘 与流（三）边缘 与流（ⅳ）边缘 与流（五）边缘 与流（ⅵ）边缘 与流的传递电位曲线示于图中所示18。顶点代表首选项 ,和 。边的强度值表示两个首选项之间的强度。
显然，任何传递潜在图形不包含任何长度的周期。这种情况导致了下面的定理。

定理12。一个潜在的图表是传递的，当且仅它不包含循环。

证明。 假设一个潜在的图表是传递的，但包含一个周期 。为了 包含平行弧和 ,因此，矛盾作为一个潜在的图表。此外，为了 , 和是弧；传递性意味着是一条弧线。现在我们知道了是一个弧线为圆弧，再传递性暗示是一条弧线。我们这样推理，是时候得出结论了为弧形。然而，也是有向图的弧，因为它是循环的一部分。从而，包含平行弧和 ,矛盾的作为一个潜在的曲线图。
假设一个潜在的图表不包含循环。假设包含圆弧和 。我们知道以来不包含平行弧。潜在的图表不能有作为一个弧，因为如果它这样做了，它将包含循环 。因为它是一个势图要么要么为弧形。从而，是一条弧线。因此，是传递的。

图中给出了一些传递势图的例子19。

因此，一个传递电位曲线的确是WACS并且在以下定理给出。

定理13。每个传递势图都是WACS。

证明。可传递电位曲线图既没有环路，也不平行的边缘。它是由定理弱连通图6个。因此，它不包含任何长度的周期由定理所指示12. 因此，它通过定理产生了一条开放路径7个. 因此，根据定义12每个传递势图都是WACS。

潜在的图形通常源自优化或者多目标的问题。因此，这样的变换的问题，可以研究作为一个特殊的图，即，WACS，严格。甲WACS是脆图表因为其边缘是0或1以下部分讨论WACS和模糊图之间的关系。

4.1。弱自催化设为模糊图

模糊图的概念是利用模糊集将脆图模糊化。模糊图是脆图的复制[36]。定理14证明了WACS是一个模糊图的一个特例。

定理14。每WACS是一个模糊的曲线图。

证明。每一个清脆的图是一个模糊图由定理1个. 因此，每个WACS也是一个模糊图，因为WACS只是一种特殊的清晰图。

WACS是一个清晰的图形。所有清晰的图形都是模糊的，但不是相反。因此，上述定理的逆命题是不成立的。

下面的定理是定理的直接后果14。

定理15。每个传递潜力图是一个模糊的曲线图。

证明。每个传递潜力图是由WACS定理13. 因此，根据定理，每个WACS都是一个模糊图14。因此，每一个传递潜力图是一个模糊的曲线图。

定理的逆15与定理的论证不一样14较早;即，所有的清脆图是模糊的，但不是周围的其他方式。

在下一节中，我们提出一个新的概念，称为模糊弱自催化集。

5个。模糊弱自催化集

WACS的模糊化导致了一种新的结构，即模糊弱自催化集（FWACS）。FWACS的定义是在定义中形式化的13。一个FWACS的一个例子显示在图20。

定义13。模糊弱自催化集（FWACS）是一个WACS，使得每个边有会员价值， 。
甲WACS是脆图和它是一种特殊类型的FWACS如定理提出16。

定理16。每个WACS都是FWACS。

证明。每一个清脆的图是一个模糊图由定理1个. 因此，每个ACS都是FACS的特例；因此每个WACS都是FWACS。

此外，下列定理是定理的直接结果16。

定理17。每个FWACS都是一个模糊图。

证明。定理1个建立每一个清晰的图形是一个模糊的曲线图。每个FACS也是一个模糊图由定理三，这意味着马上每FWACS是模糊图。

有作为记录在蓝等5种类型的脆图表。[13]。每一个清脆的图是一个模糊图和反之则不然。并非所有的清脆图是自催化集。显然，定理的逆17是不是真的要么。

我们已经证明，一个传递潜在图是一个水冷式空调系统和模糊图的一个特例。下一节介绍偏好流上边缘。

5.1条。传递势图的模糊边

考虑图中的势图18. 图的邻接矩阵是

首选项的变换流至在下一小节中描述了模糊隶属值。

5.1.1条。基于线性变换的模糊边缘隶属度

实例的偏好流区间1个如图所示变换为模糊隶属关系值线性21。

在例1个，间隔[0，4]用于指示备选方案的强度。桌子1个列出了转化力度偏好模糊隶属值。

清晰和模糊的图形的例子1个在图中示出22。

清晰图形中每一条边的颜色和厚度相同（见图22（甲）)表明顶点之间的连接性被认为是相同的。当两个顶点之间存在边时，将指定值1。如果没有边，则给出值0。

数字图22（b）说明了模糊图。边缘具有不同的“强度”，这取决于它们的成员值。此外，隶属度值越大，图的两个顶点之间的联系就越强。因此，边的不同厚度和颜色表示其顶点的强度连接。

因此，对于FWACS邻接矩阵是

在下面的小节中，我们给出了传递势图和FWACS之间的关系。

5.2。传递潜在的图表为FWACS

传递电位图形和FWACS之间的关系可以立即被观察到。该关系在下面的定理形式化。

定理18。每个传递潜力图是FWACS。

证明。定理13证明，一个传递潜在图是WACS。甲传递电位曲线图是一模糊图由定理14。边缘是与模糊的[0，1]的隶属函数值。因此，每一个传递潜力图是由FWACS定义13。

根据定理，每个FWACS都是一个模糊图17。但是定理的逆15是不正确的;也就是说，模糊图不一定是传递势图。因此，定理的逆命题18是不是真的要么。

5.3。偏好图作为模糊图类型5

事实上，定理的一般形式18可以直接从最近定义的偏好图(见定义7个)乔克洛维奇和库迪加介绍[23]。

定理19。每个偏好图都是5型模糊图。

证明。让 是一个由定义定义的偏好图7个。考虑偏好流如定义所示7个。该是(0,1)的同胚，即[37]。但是之后， ;因此偏好流可以写成以来 。所以， 现在是一个由Blue等人分类的模糊图类型5。[13]和塔希尔等。[14]。

模糊图类型5是一个清晰的图，其边的模糊权重在Blue等人中定义。[13]. 另一方面，偏好图是一个三元组 在哪里是一套顶点（表示备选方案），是一组有向边，并是其中每个边缘映射的偏好流 达到相应的强度， ,如定义所述7个。然而，模糊图类型5比偏好图更一般，因为前者可以容纳有向或无向边。因此，很明显，每个偏好图都是一个模糊图类型5，而不是相反。

数字23总结了ACS、WACS、FACS和FWACS之间的关系。

六，结论

本文提出了一种新的弱ACS定义，即WACS。WACS最初源于传递锦标赛，它是PM和ACS之间的“桥梁”。WACS为PM提供了一些新的见解。此外，对于边缘模糊的不确定PM，定义了FWACS。最后证明了PM的任何偏好图都是5型模糊图。

简言之，本文的主旨是实现采卡洛维奇提出的框架[21,22]下午。开发的FWACS能够处理不确定性问题的多准则决策（MCDM）。其中一些可在Siti Salwana等人中找到。[38]。

数据可用性

从Caklovic和Kurdija [获得的数据23] [https://doi.org/10.1016/j.ejor.2016.10.032]我们利用一些附加信息来支持关于传递势图及其与模糊图的关系的发现。

利益冲突

作者声明本论文的发表不存在利益冲突。

致谢

这项工作得到了马来西亚高等教育部基础研究资助计划(FRGS) 4F756投票支持，以及MyBrainSc奖学金的支持。