fa مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن تخصصي Special پژوهشي Research <span style="font-size:11pt"><span style="line-height:normal"><span style="text-autospace:none"><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">مساله درخت فراگیر ماکس + سام، یک درخت فراگیر</span></span><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:2.0pt">T^*</span></span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar=""> را در گراف</span></span><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:3.0pt"> G </span></span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">پیدا می‌کند که دارای مینیمم وزن ترکیبی</span></span><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:7.0pt"> max w(e)+Sum c(e)&nbsp; </span></span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">است و در آن </span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">w(e)</span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar=""> وزن و </span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">c(e)</span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar=""> هزینه یال</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt">e ͼE&nbsp; </span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">می‌باشند. این مساله &nbsp;در زمان </span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">O(mlog n)&nbsp;</span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar=""> حل می‌شود که در آن</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:2.0pt"> m </span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">تعداد یال‌ها و&nbsp;</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:2.0pt"> n </span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">تعداد رئوس گراف می‌باشد. در مساله درخت فراگیر ماکس + سام معکوس یک درخت فراگیر مفروض از گراف</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt"> G </span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">که یک درخت فراگیر ماکس + سام بهینه نیست‌، در نظر گرفته می‌شود. سپس بردار وزن</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt">w&nbsp;</span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar=""> به</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt"> w̅ </span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">اصلاح می‌شود به‌طوری‌که درخت مفروض به یک درخت فراگیر ماکس + سام بهینه تبدیل گردد. هدف این است که هزینه تغییرات</span></span><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">||</span><span style="top:3.0pt">w̅-w||</span><span style="top:7.0pt"> </span></span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">تحت فاصله همینگ مینیمم شود. </span></span><span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">در این مقاله هدف ارایه یک روش جدید برای حل مساله درخت فراگیر ماکس + سام معکوس تحت فاصله همینگ وزن‌دار نوع جمعی با اصلاح بردار وزن نوع تنگنا می‌باشد‌.</span></span> <span lang="FA" style="font-size:12.0pt"><span b="" style="font-family:" zar="">ابتدا مساله را فرمول‌بندی کرده و سپس یک الگوریتم ترکیبیاتی با زمان اجرای&nbsp;</span></span><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:7.0pt"> </span></span></span><span style="position:relative"><span style="top:7.0pt">O(mlog n)</span></span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar="">برای حل آن پیشنهاد می‌شود. در آخر یک مثال عددی برای نشان دادن کارایی روش پیشنهادی ارایه می‌شود.</span></span><span lang="FA" style="font-size:12.0pt"><span style="font-family:"B Zar""></span></span></span></span></span></span></span></span> <span style="font-size:11pt"><span style="line-height:normal"><span style="text-autospace:none"><span calibri="" style="font-family:">The max+sum spanning tree problem is to find a spanning tree&nbsp;</span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:2.0pt">T^*</span></span></span></span></span></span></span><span calibri="" style="font-family:"> which makes the combined &nbsp;weight &ldquo;</span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="font-family:XBNiloofar"><span style="position:relative"><span style="top:7.0pt">max w(e)+Sum c(e)</span></span></span></span></span></span></span><span calibri="" style="font-family:"> time&rdquo; as small as possible, in which a weight w(e) and a cost c(e) are prescribed for each </span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt">e ͼT</span></span></span></span></span></span><span calibri="" style="font-family:">. The problem can be solved in&nbsp;</span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">O(mlog n)&nbsp;</span></span><span style="font-size:12.0pt"><span b="" style="font-family:" zar=""> </span></span></span></span></span></span><span calibri="" style="font-family:"> time. In an inverse max+sum spanning tree problem,T₀is a given spanning tree of G, which is not an optimal max+sum spanning tree. Then we modify the weight vector w to&nbsp;</span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:3.0pt">w̅</span></span></span></span></span></span><span calibri="" style="font-family:"> so that T₀ becomes a max+sum spanning tree. The goal is to minimize the modification cost&nbsp;</span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">||</span><span style="top:3.0pt">w̅-w||</span></span></span></span></span></span><span calibri="" style="font-family:">under Hamming distance. This paper presents a new solution algorithm for the inverse max+sum spanning tree problem under weighted sum-type Hamming distance&nbsp; by modifying the max-weight vector with time complexity of </span><span style="direction:rtl"><span style="unicode-bidi:embed"><span calibri="" style="font-family:"><span dir="LTR" style="font-size:12.0pt"><span style="position:relative"><span style="top:7.0pt">O(mlog n)&nbsp;</span></span></span></span></span></span><span calibri="" style="font-family:">. First, we formulate the problem and then present a new solution algorithm for the problem under investigation. Finally, we present a numerical example to illustrate the efficiency of the algorithm.</span></span></span></span> مساله درخت ماکس + سام‌, بهینه‌سازی معکوس‌, فاصله همینگ Max+Sum Spanning Tree Problem, Inverse Optimization, Hamming Distance 77 91 http://jamlu.lahijan.iau.ir/browse.php?a_code=A-11-1210-2&slc_lang=fa&sid=1 B. Azad Hampa بهاره آزاد همپا bahareazad945@yahoo.com 10031947532846009463 10031947532846009463 No Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran دانشگاه صنعتی سهند، گروه ریاضی کاربردی، تبریز F. Baroughi فهیمه باروقی baroughi@sut.ac.ir 10031947532846009464 10031947532846009464 Yes Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran دانشگاه صنعتی سهند، گروه ریاضی کاربردی، تبریز