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

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

graph pebbling number and model

there are many topics in graph theory that can be called ``moving objects around a graph. for example; in network optimization, shipments are transferred from some vertices (resources) to other vertices (demand) according to the costs allocated to the edges, so that this can be done in the cheapest way. a pebble motion in a graph involves removing two pebbles from the vertex of a graph and then placing a pebble at the adjacent vertex. if a distribution (or configuration) of pebbles allows us to move at least one pebble to each vertex by repeatedly applying pebble movements, then that distribution is called a pebble of the graph. one of the most basic questions is how many pebbles are needed to ensure that any configuration with this number can target a pebble at any particular target. the smallest number of stones that meet this condition is called the graph pebble number. in this paper, after examining the roots of the number theory of the pebble graph model, which in turn is a productive subject, we will study the pebble number for specific graphs and also consider an optimization approach to this subject called weight functions.