تعداد نشریات | 44 |
تعداد شمارهها | 1,473 |
تعداد مقالات | 12,039 |
تعداد مشاهده مقاله | 22,293,021 |
تعداد دریافت فایل اصل مقاله | 9,792,950 |
مدل و عدد سنگریزه گراف | ||
نشریه ریاضی و جامعه | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 22 اسفند 1401 | ||
نوع مقاله: مقاله پژوهشی | ||
شناسه دیجیتال (DOI): 10.22108/msci.2023.133617.1509 | ||
نویسندگان | ||
سعید علیخانی* ؛ فاطمه آقایی | ||
دانشگاه یزد | ||
چکیده | ||
موضوعات بسیاری در نظریه گراف وجود دارد که میتوانند تحت عنوان «حرکت اشیاء حول یک گراف» قرار گیرند. برای مثال، در بهینهسازی شبکه، محمولهها با توجه به هزینههای تعلق گرفته به یالها، از برخی رئوس (منابع) به برخی دیگر از رئوس (تقاضا) به نحوی منتقل میشوند که این کار به ارزانترین حالت انجام شود. یک حرکت سنگریزه در گراف، شامل برداشتن دو سنگریزه از یک رأس گراف و سپس قرار دادن یک سنگریزه در رأس مجاور آن است. اگر یک توزیع (یا پیکربندی) از سنگریزهها به ما اجازه دهد که با اعمال مکررِ حرکات سنگریزه، حداقل یک سنگریزه را به هر رأس حرکت دهیم، آنگاه آن توزیع، یک سنگریزه از گراف نامیده میشود. از اساسیترین سوالات این است که چه تعداد سنگریزه مورد نیاز است تا ضمانت کند که هر پیکربندی با این تعداد، میتواند یک سنگریزه را روی هر رأس هدف مشخص قرار دهد. به کمترین تعداد سنگ که این شرط را برآورده کند، عدد سنگریزه گراف میگویند. در این مقاله، پس از بررسی ریشههای نظریه اعدادِ مدل گراف سنگریزه که به نوبه خود موضوع پرباری است، عدد سنگریزه را برای گرافهای خاص مطالعه کرده و همچنین یک رویکرد بهینهسازی در این موضوع، به نام توابع وزن را مورد بررسی قرار خواهیم داد. | ||
کلیدواژهها | ||
سنگریزه گراف؛ عدد سنگریزه؛ پیکربندی | ||
آمار تعداد مشاهده مقاله: 6 |