دانلود رایگان ترجمه مقاله مقدمه ای بر فهرست رنگ های نمودارها

مقاله انگلیسی رایگان

ترجمه فارسی رایگان 

بخشی از ترجمه فارسی مقاله:

خلاصه
یکی از زمینه های متداول و مفید نظریه ی گراف ، گراف رنگ ها است. گرافی را گراف رنگی گویند که به رئوس آن اعداد صحیح نسبت داده می شود به طوری که هیچ دو رأس مجاوری عدد صحیح یکسان ندارند.
این مسئله اغلب در زمانبندی و مجراهای کابردی رخ می دهد. یک فهرست رنگی ، اعداد صحیح را به رئوس یک گراف نسبت می دهد با این شرط که قبلا اعداد صحیح از لیست های ویژه ی رنگ های در دسترس در هر رأس آمده باشند.
برای یک کاربرد فیزیکی این مسئله ، یک شبکه ی بیسیم را در نظر بگیرید. با توجه به محدودیت های سخت افزاری ، هر رادیو مجموعه فرکانس های محدودی دارد، از آنجاییکه هر کدام از آنها می توانند ارتباط برقرار کنند و رادیو ها در بین یک فاصله ی معین از یکدیگر نمی توانند بدون تداخل در فرکانس های مشابه عمل کنند. ما این مسئله را به کمک یک گراف با نشان دادن رادیو های بیسیم به وسیله ی رئوس گراف و نسبت دادن یک فهرست به هر رأس مطابق ، فرکانس های در دسترس آنها مدلسازی کردیم. سپس رنگ های گراف را از میان این لیست ها جستجو کردیم.
کلمات کلیدی: لیست رنگ ها،قابلیت انتخاب، الگوریتم حریص
کاربرد فهرست های رنگ آمیزی
رنگ های گراف برای حل مسائل مختلف در حوزه ی زمان بندی کانال مسئله ی واگذار شده مفید هستند. طبیعتا آنچه به طور ویژه از کاربرد های فهرست رنگ ها که با مقادیر محدودی هستند بر می آید، می تواند به چیز های معینی نسبت داده شود. در این قسمت ما تعداد اندکی مثال از این مسائل و اینکه چطور فهرست های رنگ آمیزی برای حل آن ها مفید هستند عرضه می کنیم.
زیت هوفر و ویس کاربرد فهرست های رنگی را با ثبت برای پردازش محاسبات توضیح دادند. آن ها یک وضعیت شرح دادند با واحد های تابعب چندگانه ، برخی قادر به جمع و ضرب و بعضی جمع به تنهایی.
سپس فهرست رنگ ها برای راهنمایی برنامه ریزی استفاده شد، به عنوان مثال اگر یک عملیات نیازمند تکثیر باشد، نمی تواند به یک واحد جمع به تنها مختص شود. به همین منظور هر عملیات به یک لیست از واحد هایی که می توانند آن را پردازش کنند و یک لیست از مسئله ی آشکار فهرست رنگ آمیزی اختصاص داده شده است.
فهرست دوم مسئله ی رنگ آمیزی ، زمانی رخ می دهد که ثبت شده ها را به ذخیره سازی مقادیر متوسط اختصاص می دهند.
عملیات ها فهرست های معین از مقادیر ثبت شده ی مربوط به هر مقدار ثبت شده ی واحد های محاسبات ضروری هستند. اگر یک عملیات نیازمند افزایشی پیرو یک ضریب باشد، مقدار متوسط افزایش نباید در یک فهرست ذخیره شود، که به وسیله ی یک ضریب اشتراک در دسترس قرار گرفته است.
این مسائل پس از مشخص کردن مقدار ثبت شده ی تخصیص داده شده مناسب و دستورالعمل برنامه ریزی برای محاسبه ی مطلوب حل می شود. زیرا مسئله ی فهرست رنگ آمیزی ان پی هارد ، زیتآفرو و ویس از ویژگی های معین از پدیدار شدن گراف ها و از واگذاری مسئله در دستور کار برای پیدا کردن یک رنگ فایده می دهد.
کاربرد دیگر فهرست رنگ آمیزی ها مجرای واگذاری مسئله است. راما چاندرا ، بلدینگ و بادجیکوت در شبکه ی بیسیم نزدیک هم تداخل غالبی در یکدیگر را مطرح کردند. [9]
بدینسان ، برای محدود کردن تداخل امواج و جبران نیاز سخت افزاری، یک مسئله ی ضروری دسترسی به یک نویزگیر است. این کار به وسیله ی یک فهرست رنگ آمیزی مدل سازی شده.راماچاندرا و همکارانش ، اختصاص دادن فرکانس ها به یک شبکه ی غربالگری بیسیم که از ترکیبی از امواج رادیویی چندگانه و امواج رادیویی انفرادی نویزگیرها ساخته شده بود را توضیح دادند.
امواج رادیویی چندگانه ی نویزگیر، دارای امواج رادیویی بی سیم متعددی هستند که می توانند روی کانال های روی هم ریخته نشده تنظیم شوند و با سایر امواج رادیویی ارتباط برقرار کنند.
از طرف دیگر ، امواج رادیویی انفرادی نویزگیرها ، تنها می توانند بر روی یک کانال تنظیم شوند.
در به تصویر کشیدن این مسئله به وسیله ی یک مسئله ی نظریه ی گراف ، فرض شده که سخت افزار شبکه از قبل کار گذاشته شده است، به طوری که ، جانمایی شبکه مفروض است. سپس هر رادیو با یک رأس مطابقت می کند. بدین معنی که اگر یک نویزگیر ، سه رادیو دارد آن نویزگیر با سه رأس مطابقت می کند. هر یال نمایانگر یک ارتباط بیسیم بین رادیو ها در جانمایی شبکه ی معینی می باشد. این گراف ، G نامیده می شود. مبتکرین سپس در جایی که هر یال در G متناسب با یک رأس بود، گراف ناسازگار امواج رادیویی چندگانه (MCG) را ایجاد کردند. سپس اگر دو ارتباط بیسیم در G با هم تداخل کردند یک یال ما بین رئوس MCG که ارتباط آن با هم داخل کرده اند کشیده می شود. فهرست های فرکانس های در دسترس به هر رأس در MCG تخصیص داده شده اند و یک رنگ آمیزی صحیح پیگیری شده است. راما چاندرا و همکارانش به وسیله ی استفاده از الگوریتم جستجوی پهنای اول و اختصاص کانال ها به رئوس MCG بر اشکال مسئله ی فهرست رنگ آمیزی فائق آمدند. هر شبکه در جایی که آن شبکه به یک شبکه ی خارجی متصل شده است ، یک گذرگاه نویزگیر دارد. این نویزگیر به عنوان نقطه ی شروع جستجو ی پهنای اول انتخاب شده استاز اینرو اتصالات ، میزبان بیشترین ترافیک فرض شده اند.
یکی از رئوس MCG مطابق با یک ارتباط بیسیم با گذرگاه نویزگیر رنگ شده ی اول خواهد بود و رنگ آمیزی برای بقیه ی MCG در راه کم کردن تداخلات ، ادامه خواهد داشت. 4
به خاطر داشته باشید که مسئله ی فهرست رنگ آمیزی حقیقتا در اینجا یک فهرست رنگ آمیزی از یال های G می باشد. رنگ آمیزی یال در فصل 4 بیشتر توضیح داده خواهد شد.

بخشی از مقاله انگلیسی:

ABSTRACT

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.

key words:list coloring- k-Choosability- Planar – Greedy Algorithm

Applications of List Colorings Graph colorings are useful to solve various problems ranging from scheduling [2] to the channel assignment problem. List colorings in particular arise naturally from applications with restrictions on which values can be assigned to certain objects. In this section, we offer a few examples of these problems and how list colorings are used to solve them. In 3 , Zeitlhofer and Wess describe using list colorings to determine register assignments for computing processes. They discuss a situation with multiple functional units–some capable of addition and multiplication, and some capable of only addition. List coloring is then used for instruction scheduling. For example, if an operation requires a multiplication, it cannot be assigned to an addition-only unit. Thus, each operation is assigned a list of units that can process it, and a list coloring problem emerges. A second list coloring problem arises when assigning registers to store intermediate values. The operations are assigned lists of registers depending on which registers the necessary computation units access, i.e. if an operation requires an addition followed by a multiplication, the intermediate value of the addition should not be stored in a register that is not accessed by a multiplicationcapable unit. Solving these problems then determines an appropriate register assignment and instruction schedule for the desired computation. Because the list coloring problem is NP-hard, Zeitlhofer and Wess take advantage of certain properties of the graphs emerging from their registry assignment problem in order to find a coloring. Another application of list colorings is the channel assignment problem. As Ramachandran, Belding, Almeroth, and Buddhikot discuss in [9], wireless networks near each other often interfere. Thus, to limit the interference and to satisfy hardware requirements, one must limit the frequencies available to a router. This situation is modeled as a list coloring problem. Ramachandran et al. describe assigning frequencies to a wireless mesh network built on a mixture of multi-radio and single-radio routers. Multi-radio routers have multiple wireless radios which can be tuned to nonoverlapping channels and communicate with severalCourtney L. Baber Chapter 1. Introduction 6 other radios. Single-radio routers, on the other hand, can only be tuned to one channel. In representing this problem as a graph theory problem, it is assumed that the hardware for the network is already in place, so that a network topology is given. Each radio then corresponds to a vertex. Thus, if a router has three radios, that router corresponds to three vertices. Each edge represents a wireless link between radios in the given network topology. Call this graph G. The authors then construct the Multi-radio Conflict Graph (MCG) where each edge in G becomes a vertex. Then if two wireless links in G interfere with each other, an edge is drawn between the vertices in MCG that represent those links. Lists of available frequencies are assigned to each vertex of MCG, and a proper coloring is sought. Ramachandran et al. cope with the difficulty of the list coloring problem by using a breadth-first search algorithm to assign channels to the vertices of MCG. Each network has a gateway router where the network connects to an external network. This router is chosen as the starting point of the breadth-first search since its connections are assumed to host the most traffic. One of the vertices of MCG corresponding to a wireless link with the gateway router will be the first colored, and the coloring will be extended to the rest of MCG in a way that minimizes interference4 . Note that the list coloring problem presented here is actually a list coloring of the edges of G. Edge colorings will be discussed in more detail in Chapter 4.