تعداد نشریات | 43 |
تعداد شمارهها | 1,652 |
تعداد مقالات | 13,419 |
تعداد مشاهده مقاله | 30,841,249 |
تعداد دریافت فایل اصل مقاله | 12,140,756 |
مدل و عدد سنگریزه گراف | ||
نشریه ریاضی و جامعه | ||
دوره 7، شماره 4، اسفند 1401، صفحه 11-32 اصل مقاله (1.72 M) | ||
نوع مقاله: مقاله پژوهشی | ||
شناسه دیجیتال (DOI): 10.22108/msci.2023.133617.1509 | ||
نویسندگان | ||
فاطمه آقایی؛ سعید علیخانی* | ||
دانشکده علوم ریاضی، دانشگاه یزد، یزد | ||
چکیده | ||
موضوعات بسیاری در نظریه گراف وجود دارند که میتوانند تحت عنوان «حرکت اشیاء حول یک گراف» قرار گیرند. برای مثال، در بهینهسازی شبکه، محمولهها با توجه به هزینههای تعلق گرفته به یالها، از برخی رئوس (منابع) به برخی دیگر از رئوس (تقاضا) به نحوی منتقل میشوند که این کار به ارزانترین حالت انجام شود. یک حرکت سنگریزه در گراف، شامل برداشتن دو سنگریزه از یک رأس گراف و سپس قرار دادن یک سنگریزه در رأس مجاور آن است. اگر یک توزیع (یا پیکربندی) از سنگریزهها به ما اجازه دهد که با اعمال مکررِ حرکات سنگریزه، حداقل یک سنگریزه را به هر رأس حرکت دهیم، آنگاه آن توزیع، یک سنگریزه از گراف نامیده میشود. از اساسیترین سوالات این است که چه تعداد سنگریزه مورد نیاز است تا ضمانت کند که هر پیکربندی با این تعداد، میتواند یک سنگریزه را روی هر رأس هدف مشخص قرار دهد. به کمترین تعداد سنگ که این شرط را برآورده کند، عدد سنگریزه گراف میگویند. در این مقاله، پس از بررسی ریشههای نظریه اعدادِ مدل گراف سنگریزه که به نوبه خود موضوع پرباری است، عدد سنگریزه را برای گرافهای خاص مطالعه کرده و همچنین یک رویکرد بهینهسازی در این موضوع، به نام توابع وزن را مورد بررسی قرار خواهیم داد. | ||
کلیدواژهها | ||
سنگریزه گراف؛ عدد سنگریزه؛ پیکربندی | ||
مراجع | ||
[1] J. Asplund, G. Hurlbert and F. Kenter, Pebbling on graph products and other binary graph construc-tions, Australas. J. Combin., 71 (2018) 246–260. | ||
آمار تعداد مشاهده مقاله: 179 تعداد دریافت فایل اصل مقاله: 301 |