موجود
|
در این پایان نامه با توجه به اینکه برای هر لاتیس گراف متناظر با آن معرف میشود،مسئله رنگ آمیزی در نظریه گراف ها به طور خاص در اینجا مطرح میشود که آن را رنگ آمیزی لاتیس ها مینامیم.
در این پایان نامه رنگ آمیزی برای گراف هایی مطالعه میشود که از لاتیس های صفرداربدست می آیند ثابت میشود که گراف بدست آمده از لاتیس های توزیع پذیر دارای عدد رنگ و عدد خوشه ای برابر است.
ثابت میکنیم که تعداد اتمهای لاتیس اتم L برابر nاست اگر و تنها اگر عدد رنگ وعدد خوشه ای آن n + ۱باشد.
کلمات کلیدی: لاتیس صفردار، گراف مقسوم علیه صفر، عددرنگ، عدد خوشه ای
مقالات زیادی هستند که به رابطه بین نظریه گراف و نظریه لاتیس پرداخته اند. مقالات فیلیپوو ، گدونوا ، دافوس و ریوال ، بولوباس و ریوال ، ویژگیهای گراف که از مجموعه مرتب جزیی ناشی می شود را مطالعه کرده اند.
یکی از کارهای فیلیپوو مجاورت بین دو عضو می باشد که در رابطه ای مقایسه پذیری بین دو عضو از مجموعه مرتب جزیی تعریف شده است. یعنی a و b مجاور هستند اگر a ≤ bیا b ≤ aباشد. این گراف ها، گراف های مقایسه پذیری نامیده می شود. از طرف دیگر،گدنوا ،دافوس و ریوال از رابطه پوشش بین دو عضو برای تعریف مجاورت بین دو عضو استفاده کرده اند. این گراف ها، گراف پوششی نامیده میشود. بولوباس از گراف پوشش لاتیس برای مطالعه رنگ آمیزی در لاتیس استفاده کرده است.