عنوان پایان‌نامه
پیمان در گراف
- رشته تحصیلی
- ریاضی کاربردی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 5051;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 58099
- تاریخ دفاع
- ۲۳ بهمن ۱۳۹۱
- دانشجو
- هاله مریوانی
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- در این پایان نامه G یک گراف ساده ی با مجموعه رأس های V(G) و مجموعه یال های E(G) است. به ازای هر رأس v?Vمجموعه تمام رئوس مجاور با v را با N(V) نشان داده و آن را مجموعه همسایه های v می گوییم و N[v] را به صورت N[v]=N(v)?{v} تعریف می کنیم. در گراف G زیرمجموعه ناتهی S از رئوس را پیمان دفاعی ( به اختصارپیمان) می نامیم اگر به ازای هر راس v?S رابطه زیر برقرار باشد: |N[v] S|?| N(v) (V S)| مفهوم پیمان در گراف اولین بار توس P. Kristiansen، S.M. Hedetniemi ، S.T. Hedetniemi معرفی شد معرفی شد و به تدریج با بررسی کاربردهای متنوع این مفهوم، گونه های مختلفی از آن، مانند پیمان عمومی، پیمان مهاجم ... و همچنین پیمان در گراف های وزن دار معرفی شدند. عدد پیمان یک گراف عبارتست از کوچکترین اندازه یک پیمان در آن گراف . عدد پیمان توسط هدتنیمی در انواع خاصی از گراف ها یافته شده و کران های بالا و پایین برای آن ارائه شده. از دیگر مسائلی که در پیمان مورد بررسی قرار می گیرد، افراز گراف به پیمان هاست. عدد افراز یک پیمان عبارتست از بیشترین تعداد مجموعه در مجموعه افرازهای رئوس به طوری که هر مجموعه خود یک پیمان باشدعدد افراز پیمان عمومی و می نیمم درجه یک گراف مورد مطالعه قرارگرفته و عدد افراز پیمان عمومی در درخت بررسی شده و اثبات شده که عدد افراز پیمان عمومی در درخت تنها دو مقدار اختیار می کند و هم چنین کران های بالا و پایین برای عدد افراز پیمان دفاعی در گراف های همبند، ناهمبند، منتظم و درخت ها یافته شده و مقدار دقیق عدد افراز پیمان دفاعی در رده ای از گراف ها بدست آمده است. ما مسائل مشابه یعنی یافتن کران های بالا و پایین در گراف های ناهمبند، همبند، منتظم و درخت را در مورد عدد افراز پیمان دفاعی قوی را مورد بررسی قرار می دهیم . همچنین راجع به عدد افراز پیمان دفاعی و عدد افراز پیمان عمومی و پیمان مهاجم نتایج جدیدی را بیان می نماییم . واژه‌های کلیدی : پیمان دفاعی , پیمان عمومی , مجموعه غالب , عدد پیمان , عدد افراز
- Abstract
- sets V(G) and E(G) respectively.All of adjacend vertex of v is shown with N(v) and called neighberhood of v and N[v] is defined as N[v]=N(v)?{v} (defensive) alliance in G is a subset S of V (G)such that for every vertex , v?S |N[v] S|?| N(v) (V S)| The alliance partition number of a graph G is defined to be the maximum number of sets in a partition of V (G) such that each set is a (defensive)alliance. The concept of Alliances in graphs was first defined and studied by Hedetniemi, and Kristiansen .Little by little , with studing of diffrent uses of alliance , various kinds of it was introduced such as global alliance , defensive alliance ,ect. Also it was used in weighted graphs.The cardinality of minimum alliance of a graph G is called the alliance number of G. Hedeteniemi used the alliance number in a special kind of graphs and obtained upper and lower bound for it.Alliance is used in other issues such as graphs partition. global partition number and minimum degree in graphs are studied and finally global partition number is used in trees. It is shown that global partition number in tree has just 2 amount. Also global partition number is found in connected , regular graphs and trees. The exact amount of alliance partition number is seen in some groups of graphs.It means that we study similar issues like finding upper bound and lower bound in regular, connected , tree... in strong defensive alliance.Also, we proved new result about defensive partition number ,global partition number and offensive alliance. Keywords :alliance, domination, partition, alliance partition,alliance number.
