عنوان پایان‌نامه
دوره های کوچک در گراف پنکیک
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 6350;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77045;کتابخانه پردیس علوم شماره ثبت: 6350;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77045
- تاریخ دفاع
- ۱۷ بهمن ۱۳۹۴
- دانشجو
- حدیثه صیدی
- استاد راهنما
- محمدرضا درفشه
- چکیده
- است. این مسئله درمورد محاسبه قطر گراف پنکیک می‌باشد. در این پایان‌نامه ثابت خواهیم کرد که گراف پنکیک دارای ساختار سلسله مراتبی است و همچنین گرافی فوق‌همبند و ابرهمبند است. به علاوه نشان خواهیم داد که مطالعه دورهای کوچک گراف پنکیک در مسیر حل مسئله پنکیک بسیار سودمند است. ما ساختار و تعداد دورهای کوچک گراف پنکیک را بدست خواهیم آورد. در نهایت با استفاده از گروه خودریختی‌های گراف پنکیک نشان خواهیم داد که یک گراف پنکیک یک نمایش منظّم گرافی از یک گروه متقارن می‌باشد.
- Abstract
- The Pancake graph is a Cayley graph of the symmetric group Sn defined on a certain set of generators of Sn called prefix-reversal. The well-known Pancake problem requires finding the diameter of the Pancake graph. In this thesis we prove that the Pancake graph has a hierarchical structure and it is super-connected and hyper-connected. In addition, we show that studying small cycles in the Pancake graph is an effective way to solve the Pancake problem. We obtain structure and number of small cycles in the Pancake graph. Finally, by automorphism groups of the Pancake graphs we show that a Pancake graph is a graphical regular representation of a symmetric group.
