ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH
Publish place: Iranian Journal of Fuzzy Systems، Vol: 15، Issue: 2
Publish Year: 1397
نوع سند: مقاله ژورنالی
زبان: English
View: 111
This Paper With 20 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJFS-15-2_007
تاریخ نمایه سازی: 17 خرداد 1401
Abstract:
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.
Keywords:
Authors
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
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :