سنگ ریزه بهینه: یافتن بهترین پیکربندی

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