ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH
Author(s):
Abstract:
Uncertain graphs are employed to describe graph models with indeterministic information that produced by human beings. This paper aims to study the maximum matching problem in uncertain graphs. The number of edges of a maximum matching in a graph is called matching number of 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 transformed into 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.
Article Type:
Research/Original Article
Language:
English
Published:
Iranian journal of fuzzy systems, Volume:15 Issue:2, 2018
Pages:
89 - 108
magiran.com/p1815870  
روش‌های دسترسی به متن این مطلب
اشتراک شخصی
در سایت عضو شوید و هزینه اشتراک یک‌ساله سایت به مبلغ 300,000ريال را پرداخت کنید. همزمان با برقراری دوره اشتراک بسته دانلود 100 مطلب نیز برای شما فعال خواهد شد!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی همه کاربران به متن مطالب خریداری نمایند!