یک رویکرد جدید برای تحلیل حساسیت مساله درخت فراگیرکمینه

مساله درخت فراگیرکمینه یکی از مسایل مشهور، بنیادی و پرطرف دار در نظریه گراف و شبکه ها بوده که کاربردهای فراوانی در حوزه های مختلف دارد. برای حل این مساله الگوریتم های کارا و جذابی از قبیل الگوریتم کروسکال، پریم، سولین و غیره ارایه شده است. دراین مقاله، تحلیل حساسیت این مساله از قبیل اثر کاهش یا افزایش وزن کمان بر وزن و درخت فراگیرکمینه بررسی می شود. بعبارت بهتر،هدف این است که دامنه تغییرات مجاز وزن هر کمان طوری محاسبه شود بطوریکه ساختار اصلی جواب در این مساله تغییر نکند. برای این منظور،از رویکرد جذاب ایجاد دور استفاده شده است. در این رویکرد، کلیه محاسبات و عملیات ریاضی موردنیاز، بصورت مقایسه و ساده انجام می شود این مهم باعث افزایش سرعت اجرای رویکرد و حل می شود. مهمترین ویژگی های این مقاله، کارایی رویکرد ایجاد دور و پیاده سازی جذاب آن می باشد.درپایان، روش های تحلیل حساسیت در قالب یک مثال نمونه، گام به گام پیاده سازی شده اند.

کلیدواژه ها:

تحلیل حساسیت ، تحلیل حساسیت جریان های شبکه ، تحلیل حساسیت درخت فراگیرکمینه ، رویکرد ایجاد دور ، الگوریتم پریم ، کاهش یا افزایش وزن کمان