ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH

  • سال انتشار: 1397
  • محل انتشار: مجله سیستم های فازی، دوره: 15، شماره: 2
  • کد COI اختصاصی: JR_IJFS-15-2_007
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 132
دانلود فایل این مقاله

نویسندگان

Hui Li

School of Information and Engineering, Wuchang University of Technology, Wuhan, ۴۳۰۲۲۳, China

Bo Zhang

School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, ۴۳۰۰۷۳, China

Jin Peng

Institute of Uncertain Systems, Huanggang Normal University, Huang- gang, ۴۳۸۰۰۰, China

چکیده

Uncertain graphs are employed to describe graph models with indeterministicinformation that produced by human beings. This paper aims to study themaximum matching problem in uncertain graphs.The number of edges of a maximum matching in a graph is called matching numberof the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable.Different from that in a deterministic graph, it is more meaningful to investigate the uncertain measure that an uncertain graph is k-edge matching (i.e., the matching number is greater than or equal to k).We first study the properties of the matching number of an uncertain graph, and then give a fundamental formula for calculating the uncertain measure. We further prove that the fundamental formula can be transformedinto a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form.Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm.

کلیدواژه ها

Uncertainty theory, Uncertain measure, Maximum matching, Matching number, Uncertain graph

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.