سنگ ريزه بهينه: يافتن بهترين پيكربندي

موضوعات بسياري در نظريه گراف وجود دارد كه مي توانند تحت عنوان «حركت اشياء حول يك گراف» قرار گيرند. براي مثال، در بهينه سازي شبكه، محموله ها با توجه به هزينه هاي تعلق گرفته به يال ها، از برخي رئوس (منابع) به برخي ديگر از رئوس (تقاضا) به نحوي منتقل مي شوند كه اين كار به ارزان ترين حالت انجام شود. يك حركت سنگ ريزه در گراف، شامل برداشتن دو سنگ ريزه از يك رأس گراف و سپس قرار دادن يك سنگ ريزه در رأس مجاور آن است. اگر يك توزيع (يا پيكربندي) از سنگ ريزه ها به ما اجازه دهد كه با اعمال مكررِ حركات سنگ ريزه، حداقل يك سنگ ريزه را به هر رأس حركت دهيم، آنگاه آن توزيع، يك سنگ ريزه از گراف ناميده مي شود. از اساسي ترين سوالات اين است كه چه تعداد سنگ ريزه مورد نياز است تا ضمانت كند كه هر پيكربندي با اين تعداد، مي تواند يك سنگ ريزه را روي هر رأس هدف مشخص قرار دهد. به كمترين تعداد سنگ كه اين شرط را برآورده كند، عدد سنگ ريزه گراف مي گويند و آنرا با نماد (G(π نشان مي دهند. براي جواب به اين سوال، اكثرا بدترين سناريو را در نظر مي گيريم كه عبارت است از بزرگ ترين پيكربندي كه نمي تواند هدف را حل كند. در اين مقاله بهترين سناريو را در نيز نظر مي گيريم، يعني كوچك ترين پيكربندي كه مي تواند هر هدفي را حل كند. عدد سنگ ريزه بهينه يك گراف G كه با نماد π نشان داده مي شود، برابر كوچكترين عدد m است به طوري كه پيكربندي C با اندازه m وجود دارد كه براي هر r يك راه حل است.