نام دانشجو: فاطمه سیفی

   استاد راهنما: دکتر ابراهیم قربانی

   استاد ارزیاب داخلی: دکتر محمدجواد نیک¬مهر

   استاد ارزیاب خارجی: دکتر حمیدرضا میمنی

 

 

رتبه یک گراف برابر با رتبه ماتریس مجاورت آن است. گرافکاهش یافته نامیده می­شود هرگاه رأس تنها نداشته باشد و هیچ دو رأس آن مجموعه همسایه­های یکسان نداشته باشند. گراف کاهش­یافته را ماکسیمال گویند هرگاه یک زیرگراف القایی و سره از یک گراف کاهش­یافته با رتبه یکسان بانباشد. -رتبه ماتریسبرابر با رتبهاست. نشان می­دهیم هرگاه آنگاه مجموعه گراف­ها با - رتبه مشخص، متناهی است و با استفاده از رأس­های دوقلو و هم­دوقلو این موضوع را به و گسترش می­دهیم و یک الگوریتم برای ساختن گراف­هایی با -رتبه مشخص ارائه می­دهیم. رتبه تمام گراف­هایی که با اضافه کردن دو رأس به گراف کامل به دست می­آیند را محاسبه می­کنیم و سه خانواده نامتناهی از گراف­های ماکسیمال را معرفی می­کنیم. هم­چنین، گراف­های دوستی تعمیم­یافته را معرفی می­کنیم و یک رده­بندی تقریباً کامل از این گراف­ها ارائه می­دهیم. به علاوه، یک رده­بندی کامل از درخت­های ماکسیمال را معین می­کنیم. سرانجام، با استفاده از مفهوم2-رتبه یکگراف، عدد رنگی برخی از گراف­های کاهش­یافته را مشخص می­کنیم.