آشنایی با فهرست رنگ های گراف An Introduction to List Colorings of Graphs
- نوع فایل : کتاب
- زبان : فارسی
توضیحات
رشته های مرتبط: مهندسی کامپیوتر، سخت افزار، معماری سیستم های کامپیوتری . مهندسی نرم افزار
خلاصه یکی از زمینه های متداول و مفید نظریه ی گراف ، گراف رنگ ها است. گرافی را گراف رنگی گویند که به رئوس آن اعداد صحیح نسبت داده می شود به طوری که هیچ دو رأس مجاوری عدد صحیح یکسان ندارند. این مسئله اغلب در زمانبندی و مجراهای کابردی رخ می دهد. یک فهرست رنگی ، اعداد صحیح را به رئوس یک گراف نسبت می دهد با این شرط که قبلا اعداد صحیح از لیست های ویژه ی رنگ های در دسترس در هر رأس آمده باشند. برای یک کاربرد فیزیکی این مسئله ، یک شبکه ی بیسیم را در نظر بگیرید. با توجه به محدودیت های سخت افزاری ، هر رادیو مجموعه فرکانس های محدودی دارد، از آنجاییکه هر کدام از آنها می توانند ارتباط برقرار کنند و رادیو ها در بین یک فاصله ی معین از یکدیگر نمی توانند بدون تداخل در فرکانس های مشابه عمل کنند. ما این مسئله را به کمک یک گراف با نشان دادن رادیو های بیسیم به وسیله ی رئوس گراف و نسبت دادن یک فهرست به هر رأس مطابق ، فرکانس های در دسترس آنها مدلسازی کردیم. سپس رنگ های گراف را از میان این لیست ها جستجو کردیم. کلمات کلیدی: لیست رنگ ها،قابلیت انتخاب، الگوریتم حریص کاربرد فهرست های رنگ آمیزی رنگ های گراف برای حل مسائل مختلف در حوزه ی زمان بندی کانال مسئله ی واگذار شده مفید هستند. طبیعتا آنچه به طور ویژه از کاربرد های فهرست رنگ ها که با مقادیر محدودی هستند بر می آید، می تواند به چیز های معینی نسبت داده شود. در این قسمت ما تعداد اندکی مثال از این مسائل و اینکه چطور فهرست های رنگ آمیزی برای حل آن ها مفید هستند عرضه می کنیم. زیت هوفر و ویس کاربرد فهرست های رنگی را با ثبت برای پردازش محاسبات توضیح دادند. آن ها یک وضعیت شرح دادند با واحد های تابعب چندگانه ، برخی قادر به جمع و ضرب و بعضی جمع به تنهایی. سپس فهرست رنگ ها برای راهنمایی برنامه ریزی استفاده شد، به عنوان مثال اگر یک عملیات نیازمند تکثیر باشد، نمی تواند به یک واحد جمع به تنها مختص شود. به همین منظور هر عملیات به یک لیست از واحد هایی که می توانند آن را پردازش کنند و یک لیست از مسئله ی آشکار فهرست رنگ آمیزی اختصاص داده شده است. فهرست دوم مسئله ی رنگ آمیزی ، زمانی رخ می دهد که ثبت شده ها را به ذخیره سازی مقادیر متوسط اختصاص می دهند. عملیات ها فهرست های معین از مقادیر ثبت شده ی مربوط به هر مقدار ثبت شده ی واحد های محاسبات ضروری هستند. اگر یک عملیات نیازمند افزایشی پیرو یک ضریب باشد، مقدار متوسط افزایش نباید در یک فهرست ذخیره شود، که به وسیله ی یک ضریب اشتراک در دسترس قرار گرفته است. این مسائل پس از مشخص کردن مقدار ثبت شده ی تخصیص داده شده مناسب و دستورالعمل برنامه ریزی برای محاسبه ی مطلوب حل می شود. زیرا مسئله ی فهرست رنگ آمیزی ان پی هارد ، زیتآفرو و ویس از ویژگی های معین از پدیدار شدن گراف ها و از واگذاری مسئله در دستور کار برای پیدا کردن یک رنگ فایده می دهد. کاربرد دیگر فهرست رنگ آمیزی ها مجرای واگذاری مسئله است. راما چاندرا ، بلدینگ و بادجیکوت در شبکه ی بیسیم نزدیک هم تداخل غالبی در یکدیگر را مطرح کردند. [۹] بدینسان ، برای محدود کردن تداخل امواج و جبران نیاز سخت افزاری، یک مسئله ی ضروری دسترسی به یک نویزگیر است. این کار به وسیله ی یک فهرست رنگ آمیزی مدل سازی شده.راماچاندرا و همکارانش ، اختصاص دادن فرکانس ها به یک شبکه ی غربالگری بیسیم که از ترکیبی از امواج رادیویی چندگانه و امواج رادیویی انفرادی نویزگیرها ساخته شده بود را توضیح دادند. امواج رادیویی چندگانه ی نویزگیر، دارای امواج رادیویی بی سیم متعددی هستند که می توانند روی کانال های روی هم ریخته نشده تنظیم شوند و با سایر امواج رادیویی ارتباط برقرار کنند. از طرف دیگر ، امواج رادیویی انفرادی نویزگیرها ، تنها می توانند بر روی یک کانال تنظیم شوند. در به تصویر کشیدن این مسئله به وسیله ی یک مسئله ی نظریه ی گراف ، فرض شده که سخت افزار شبکه از قبل کار گذاشته شده است، به طوری که ، جانمایی شبکه مفروض است. سپس هر رادیو با یک رأس مطابقت می کند. بدین معنی که اگر یک نویزگیر ، سه رادیو دارد آن نویزگیر با سه رأس مطابقت می کند. هر یال نمایانگر یک ارتباط بیسیم بین رادیو ها در جانمایی شبکه ی معینی می باشد. این گراف ، G نامیده می شود. مبتکرین سپس در جایی که هر یال در G متناسب با یک رأس بود، گراف ناسازگار امواج رادیویی چندگانه (MCG) را ایجاد کردند. سپس اگر دو ارتباط بیسیم در G با هم تداخل کردند یک یال ما بین رئوس MCG که ارتباط آن با هم داخل کرده اند کشیده می شود. فهرست های فرکانس های در دسترس به هر رأس در MCG تخصیص داده شده اند و یک رنگ آمیزی صحیح پیگیری شده است. راما چاندرا و همکارانش به وسیله ی استفاده از الگوریتم جستجوی پهنای اول و اختصاص کانال ها به رئوس MCG بر اشکال مسئله ی فهرست رنگ آمیزی فائق آمدند. هر شبکه در جایی که آن شبکه به یک شبکه ی خارجی متصل شده است ، یک گذرگاه نویزگیر دارد. این نویزگیر به عنوان نقطه ی شروع جستجو ی پهنای اول انتخاب شده استاز اینرو اتصالات ، میزبان بیشترین ترافیک فرض شده اند. یکی از رئوس MCG مطابق با یک ارتباط بیسیم با گذرگاه نویزگیر رنگ شده ی اول خواهد بود و رنگ آمیزی برای بقیه ی MCG در راه کم کردن تداخلات ، ادامه خواهد داشت. ۴ به خاطر داشته باشید که مسئله ی فهرست رنگ آمیزی حقیقتا در اینجا یک فهرست رنگ آمیزی از یال های G می باشد. رنگ آمیزی یال در فصل ۴ بیشتر توضیح داده خواهد شد.
خلاصه یکی از زمینه های متداول و مفید نظریه ی گراف ، گراف رنگ ها است. گرافی را گراف رنگی گویند که به رئوس آن اعداد صحیح نسبت داده می شود به طوری که هیچ دو رأس مجاوری عدد صحیح یکسان ندارند. این مسئله اغلب در زمانبندی و مجراهای کابردی رخ می دهد. یک فهرست رنگی ، اعداد صحیح را به رئوس یک گراف نسبت می دهد با این شرط که قبلا اعداد صحیح از لیست های ویژه ی رنگ های در دسترس در هر رأس آمده باشند. برای یک کاربرد فیزیکی این مسئله ، یک شبکه ی بیسیم را در نظر بگیرید. با توجه به محدودیت های سخت افزاری ، هر رادیو مجموعه فرکانس های محدودی دارد، از آنجاییکه هر کدام از آنها می توانند ارتباط برقرار کنند و رادیو ها در بین یک فاصله ی معین از یکدیگر نمی توانند بدون تداخل در فرکانس های مشابه عمل کنند. ما این مسئله را به کمک یک گراف با نشان دادن رادیو های بیسیم به وسیله ی رئوس گراف و نسبت دادن یک فهرست به هر رأس مطابق ، فرکانس های در دسترس آنها مدلسازی کردیم. سپس رنگ های گراف را از میان این لیست ها جستجو کردیم. کلمات کلیدی: لیست رنگ ها،قابلیت انتخاب، الگوریتم حریص کاربرد فهرست های رنگ آمیزی رنگ های گراف برای حل مسائل مختلف در حوزه ی زمان بندی کانال مسئله ی واگذار شده مفید هستند. طبیعتا آنچه به طور ویژه از کاربرد های فهرست رنگ ها که با مقادیر محدودی هستند بر می آید، می تواند به چیز های معینی نسبت داده شود. در این قسمت ما تعداد اندکی مثال از این مسائل و اینکه چطور فهرست های رنگ آمیزی برای حل آن ها مفید هستند عرضه می کنیم. زیت هوفر و ویس کاربرد فهرست های رنگی را با ثبت برای پردازش محاسبات توضیح دادند. آن ها یک وضعیت شرح دادند با واحد های تابعب چندگانه ، برخی قادر به جمع و ضرب و بعضی جمع به تنهایی. سپس فهرست رنگ ها برای راهنمایی برنامه ریزی استفاده شد، به عنوان مثال اگر یک عملیات نیازمند تکثیر باشد، نمی تواند به یک واحد جمع به تنها مختص شود. به همین منظور هر عملیات به یک لیست از واحد هایی که می توانند آن را پردازش کنند و یک لیست از مسئله ی آشکار فهرست رنگ آمیزی اختصاص داده شده است. فهرست دوم مسئله ی رنگ آمیزی ، زمانی رخ می دهد که ثبت شده ها را به ذخیره سازی مقادیر متوسط اختصاص می دهند. عملیات ها فهرست های معین از مقادیر ثبت شده ی مربوط به هر مقدار ثبت شده ی واحد های محاسبات ضروری هستند. اگر یک عملیات نیازمند افزایشی پیرو یک ضریب باشد، مقدار متوسط افزایش نباید در یک فهرست ذخیره شود، که به وسیله ی یک ضریب اشتراک در دسترس قرار گرفته است. این مسائل پس از مشخص کردن مقدار ثبت شده ی تخصیص داده شده مناسب و دستورالعمل برنامه ریزی برای محاسبه ی مطلوب حل می شود. زیرا مسئله ی فهرست رنگ آمیزی ان پی هارد ، زیتآفرو و ویس از ویژگی های معین از پدیدار شدن گراف ها و از واگذاری مسئله در دستور کار برای پیدا کردن یک رنگ فایده می دهد. کاربرد دیگر فهرست رنگ آمیزی ها مجرای واگذاری مسئله است. راما چاندرا ، بلدینگ و بادجیکوت در شبکه ی بیسیم نزدیک هم تداخل غالبی در یکدیگر را مطرح کردند. [۹] بدینسان ، برای محدود کردن تداخل امواج و جبران نیاز سخت افزاری، یک مسئله ی ضروری دسترسی به یک نویزگیر است. این کار به وسیله ی یک فهرست رنگ آمیزی مدل سازی شده.راماچاندرا و همکارانش ، اختصاص دادن فرکانس ها به یک شبکه ی غربالگری بیسیم که از ترکیبی از امواج رادیویی چندگانه و امواج رادیویی انفرادی نویزگیرها ساخته شده بود را توضیح دادند. امواج رادیویی چندگانه ی نویزگیر، دارای امواج رادیویی بی سیم متعددی هستند که می توانند روی کانال های روی هم ریخته نشده تنظیم شوند و با سایر امواج رادیویی ارتباط برقرار کنند. از طرف دیگر ، امواج رادیویی انفرادی نویزگیرها ، تنها می توانند بر روی یک کانال تنظیم شوند. در به تصویر کشیدن این مسئله به وسیله ی یک مسئله ی نظریه ی گراف ، فرض شده که سخت افزار شبکه از قبل کار گذاشته شده است، به طوری که ، جانمایی شبکه مفروض است. سپس هر رادیو با یک رأس مطابقت می کند. بدین معنی که اگر یک نویزگیر ، سه رادیو دارد آن نویزگیر با سه رأس مطابقت می کند. هر یال نمایانگر یک ارتباط بیسیم بین رادیو ها در جانمایی شبکه ی معینی می باشد. این گراف ، G نامیده می شود. مبتکرین سپس در جایی که هر یال در G متناسب با یک رأس بود، گراف ناسازگار امواج رادیویی چندگانه (MCG) را ایجاد کردند. سپس اگر دو ارتباط بیسیم در G با هم تداخل کردند یک یال ما بین رئوس MCG که ارتباط آن با هم داخل کرده اند کشیده می شود. فهرست های فرکانس های در دسترس به هر رأس در MCG تخصیص داده شده اند و یک رنگ آمیزی صحیح پیگیری شده است. راما چاندرا و همکارانش به وسیله ی استفاده از الگوریتم جستجوی پهنای اول و اختصاص کانال ها به رئوس MCG بر اشکال مسئله ی فهرست رنگ آمیزی فائق آمدند. هر شبکه در جایی که آن شبکه به یک شبکه ی خارجی متصل شده است ، یک گذرگاه نویزگیر دارد. این نویزگیر به عنوان نقطه ی شروع جستجو ی پهنای اول انتخاب شده استاز اینرو اتصالات ، میزبان بیشترین ترافیک فرض شده اند. یکی از رئوس MCG مطابق با یک ارتباط بیسیم با گذرگاه نویزگیر رنگ شده ی اول خواهد بود و رنگ آمیزی برای بقیه ی MCG در راه کم کردن تداخلات ، ادامه خواهد داشت. ۴ به خاطر داشته باشید که مسئله ی فهرست رنگ آمیزی حقیقتا در اینجا یک فهرست رنگ آمیزی از یال های G می باشد. رنگ آمیزی یال در فصل ۴ بیشتر توضیح داده خواهد شد.
Description
One of the most popular and useful areas of graph theory is graph colorings. A graph coloring is an assignment of integers to the vertices of a graph so that no two adjacent vertices are assigned the same integer. This problem frequently arises in scheduling and channel assignment applications. A list coloring of a graph is an assignment of integers to the vertices of a graph as before with the restriction that the integers must come from specific lists of available colors at each vertex. For a physical application of this problem, consider a wireless network. Due to hardware restrictions, each radio has a limited set of frequencies through which it can communicate, and radios within a certain distance of each other cannot operate on the same frequency without interfering. We model this problem as a graph by representing the wireless radios by vertices and assigning a list to each vertex according to its available frequencies. We then seek a coloring of the graph from these lists.
