مدل و عدد سنگ‌ريزه گراف

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