ادامه رنگ آمیزی نمودار:الگوریتم ها

الگوریتم ها [ ویرایش ]

رنگ آمیزی نمودار

تصمیم گیری
نام	نمودار رنگ آمیزی، راس رنگ آمیزی، K -coloring
ورودی	نمودار G با vertices n . علاقه k
خروجی	آیا G یک رنگ آمیزی مناسب با رنگ K را پذیرفته است؟
زمان اجرا	O (2 n n ) [6]
پیچیدگی	NP کامل است
کاهش از	3-رضایت بخش
گری - جانسون	GT4
بهینه سازی
نام	شماره کروماتیک
ورودی	نمودار G با vertices n .
خروجی	χ ( G )
پیچیدگی	NP-سخت
تقریب	O ( n (ورود n ) −3 (ورود به سیستم n ) 2 )
غیر قابل تقریب بودن	O ( n 1 − ε ) مگر اینکه P = NP باشد
مشکل شمارش
نام	چند جمله ای کرواتیک
ورودی	نمودار G با vertices n . علاقه k
خروجی	تعداد P ( G ، k ) رنگهای مناسب K از G
زمان اجرا	O (2 n n )
پیچیدگی	# P-کامل
تقریب	FPRAS برای موارد محدود
غیر قابل تقریب بودن	بدون PTAS مگر اینکه P = NP باشد

زمان چند جمله ای [ ویرایش ]

تعیین اینکه آیا یک گراف با 2 رنگ می تواند معادل تعیین اینکه آیا نمودار دو طرفه است یا خیر ، می باشد و بنابراین در زمان خطی با استفاده از جستجوی وسعت اول یا جستجوی عمق اول محاسبه می شود . به طور کلی ، تعداد کرومیک و رنگ آمیزی مربوط به نمودارهای کامل را می توان در زمان چند جمله ای با استفاده از برنامه نویسی semidefinite محاسبه کرد . فرمولهای بسته چند جمله ای کرومیک برای بسیاری از کلاس های نمودار ، مانند جنگل ها ، نمودارهای وتر ، چرخه ها ، چرخ ها و نردبان ها شناخته شده است ، بنابراین می توان این موارد را در زمان چند جمله ای ارزیابی کرد.

اگر نمودار مسطح باشد و از عرض شاخه کمی برخوردار باشد (یا غیر قطبی است اما با تجزیه شاخه شناخته شده است) ، می توان آن را در زمان چند جمله ای با استفاده از برنامه نویسی پویا حل کرد. به طور کلی ، زمان مورد نیاز در اندازه نمودار چند جمله ای است ، اما در عرض شاخه نمایی است.

الگوریتم های دقیق [ ویرایش ]

جستجوی بی رحمانه برای k- colouring ، هر یک را در نظر می گیرد $k ^ {n$ تکالیف از رنگ k به n راس و چک برای هر یک اگر قانونی باشد. برای محاسبه تعداد کروماتیک و چند جمله ای کرومی ، این روش برای همه استفاده می شود $k = 1 ، \ ldots ، n-1$ غیر عملی برای همه به جز کوچکترین نمودارهای ورودی.

با استفاده از برنامه نویسی پویا و محدود کردن تعداد مجموعه های مستقل حداکثر ، قابلیت k- colouris در زمان و مکان قابل تصمیم گیری است $\ displaystyle O (2.4423 ^ {n})$ . [7] با استفاده از اصل شمول و خروج و الگوریتم Yates برای تبدیل سریع زتا ، میزان رنگپذیری k می تواند در زمان تصمیم گیری شود $O (2 ^ {n} n)$ [6] برای هر k . الگوریتم های سریعتر به دلیل رنگ آمیزی 3- و 4 شناخته شده اند که می توان در زمان تصمیم گیری کرد $O (1.7272 ^ {n})$ ، به ترتیب [9]

انقباض [ ویرایش ]

انقباض $G / UV$ از نمودار G ، گرافی است که با شناسایی راس های u و v ، و از بین بردن لبه های بین آنها به دست می آید. لبه های باقیمانده در ابتدا به u یا v اتفاق می افتد ، در حال حاضر حادثه شناسایی آنها است. این عمل در تحلیل رنگ آمیزی نمودار نقش عمده ای دارد.

عدد کروماتیک رابطه عود را برآورده می کند :

$\ chi (G) = {\ text {min}} \ {\ chi (G + uv) ، \ chi (G / uv) \$

با توجه به Zykov (1949) ، که در آن شما و v راس غیر مجاور ، و $G + uv$ نمودار با لبه uv اضافه شده است. چندین الگوریتم بر اساس ارزیابی این عود بنا شده اند و درخت محاسبه حاصل بعضاً درخت زایکوف نامیده می شود. زمان اجرا برای انتخاب راس های u و v مبتنی بر اکتشافی است .

چند جمله ای کرومی رابطه عود کننده زیر را برآورده می کند

$P (G-uv، k) = P (G / uv، k) + P (G، k)$

که در آن u و v راسهای مجاور هستند ، و $G-UV$ نمودار با لبه uv برداشته شده است. $P (G-UV ، k)$ تعداد رنگهای مناسب و مناسب گراف را نشان می دهد ، جایی که رنگها ممکن است یکسان یا متفاوت باشند. سپس رنگهای مناسب از دو نمودار مختلف بوجود می آید. برای توضیح ، اگر رئوس های u و v دارای رنگ های مختلف باشند ، ممکن است گرافیکی را در نظر بگیریم که u و v در مجاورت قرار دارند. اگر u و v یکسان با هم باشند ، ممکن است گرافیکی را نیز در نظر بگیریم که u و v در آن منعقد می شوند. کنجکاوی توته در مورد اینکه دیگر خصوصیات گراف این عود را راضی می کند ، باعث شد که وی یک تعمیم دو متغیره از چند جملهای کرومی ، چند جمله ای Tutte را کشف کند .

این عبارات منجر به یک روش بازگشتی به نام الگوریتم حذف-انقباض می شود ، که اساس بسیاری از الگوریتم ها برای رنگ آمیزی نمودار را تشکیل می دهد. زمان اجرا همان عود عدد را با ارقام فیبوناچی برآورده می کند ، بنابراین در بدترین حالت الگوریتم به موقع در یک فاکتور چند جملهای اجرا می شود ${\ displaystyle \ left ({\ tfrac {1 + {\ sqrt {5}}} {2}} \ Right) ^ {n + m} = O (1.6180 ^ {n + m})}$ برای n vertices و m edge. [10] تجزیه و تحلیل می تواند در یک فاکتور چند جمله ای از تعداد بهبود یابد $t (G)$ از درختهای پوشا از گراف ورودی. [11] در عمل ، استراتژی های شاخه و محدود و رد ایزومورفیسم نمودار برای جلوگیری از برخی تماس های بازگشتی استفاده می شود. زمان اجرا بستگی به اکتشافی دارد که برای انتخاب جفت ورتکس استفاده می شود.

رنگ آمیزی حریص [ ویرایش ]

مقاله اصلی: رنگ آمیزی حریص

دو رنگ حریص از همان نمودار با استفاده از سفارشات مختلف vertex. مثال مناسب نمودارهای 2 رنگی با n رئوس را تعمیم می دهد ، جایی که الگوریتم حریص صرف می شود $n / 2$ رنگها

الگوریتم حریصانه رئوس در یک نظم خاص در نظر می گیرد $v_ {1$ ، ... ، $v_ {n$ و اختصاص به $v_ {من$ کمترین رنگ موجود توسط آن استفاده نشده است $v_ {من$ در میان همسایگان $v_ {1$ ، ... ، $v_ {i-1$ در صورت لزوم ، یک رنگ تازه اضافه کنید. کیفیت رنگ آمیزی حاصل به ترتیب انتخابی بستگی دارد. یک سفارش وجود دارد که منجر به رنگ آمیزی حریص با تعداد بهینه آن می شود $\ چی (G)$ رنگها از طرف دیگر ، رنگ های حریص می توانند خودسرانه بد باشند. به عنوان مثال ، نمودار تاج در n vertices می تواند 2 رنگ باشد ، اما دارای نظمی است که منجر به رنگ آمیزی حریص با $n / 2$ رنگها

برای نمودارهای وتر و مخصوصاً در موارد خاص نمودارهای وتر مانند نمودارهای فاصله و نمودارهای بی تفاوت ، از الگوریتم رنگ آمیزی حریص می توان برای یافتن رنگهای بهینه در زمان چند جمله ای استفاده کرد ، با انتخاب دستور vertex به عنوان معکوس سفارش کامل حذف . نمودار نمودار کاملا orderable تعمیم این اموال، بلکه آن است که NP-hard است برای پیدا کردن یک سفارش کامل از این نمودار.

اگر رئوس ها مطابق درجه آنها سفارش داده شوند ، در نتیجه رنگ آمیزی حریص حداکثر استفاده می شود ${\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i}) + 1، i \$ رنگ ها ، حداکثر یک بیشتر از حداکثر درجه نمودار. این اکتشافی گاهی اوقات الگوریتم ولز-پاول نامیده می شود. [12] اکتشافی دیگر به دلیل Brllaz ترتیب را بصورت پویا و در حالی که الگوریتم پیش می رود ، تنظیم می کند ، و گزینه بعدی راس مجاور بیشترین تعداد رنگ های مختلف را انتخاب می کند. [13] بسیاری دیگر از اکتشافات رنگ آمیزی نمودار نیز به همین ترتیب مبتنی بر رنگ آمیزی حریص برای یک استراتژی خاص استاتیک یا پویا برای سفارش رأسها هستند ، این الگوریتم ها گاهی اوقات الگوریتم های رنگ آمیزی متوالی نامیده می شوند .

حداکثر (بدترین) تعداد رنگ هایی که می توان با الگوریتم حریص بدست آورد ، با استفاده از یک دستور vertex که برای به حداکثر رساندن این عدد انتخاب شده است ، به عنوان Grundy یک نمودار گفته می شود.

الگوریتم های موازی و توزیع شده [ ویرایش ]

در زمینه الگوریتم های توزیع شده ، رنگ آمیزی نمودار با مشکل شکست تقارن ارتباط نزدیکی دارد . الگوریتم های تصادفی پیشرفته ترین حالت فعلی برای حداکثر درجه Δ به اندازه کافی بزرگتر از الگوریتم های قطعی سریعتر هستند. سریعترین الگوریتم های تصادفی از تکنیک چند کارآزمایی توسط Schneider و همکاران استفاده می کنند. [14]

در یک نمودار متقارن ، یک الگوریتم توزیع شده قطعی نمی تواند رنگ آمیزی مناسبی را پیدا کند. برخی از اطلاعات کمکی برای شکستن تقارن مورد نیاز است. یک فرض استاندارد این است که در ابتدا هر گره یک شناسه منحصر به فرد دارد ، به عنوان مثال از مجموعه 1 ، 2 ، ... ، n . قرار دادن در غیر این صورت، فرض کنیم که ما یک داده می شود N -coloring. چالش این است که کاهش تعداد رنگ از N به عنوان مثال، Δ + 1. بیشتر رنگ به کار می شوند، به عنوان مثال O (Δ) به جای Δ + 1، دور ارتباطات کمتری مورد نیاز است. [14]

یک نسخه مستقیم توزیع شده از الگوریتم حریص برای نقاشی (Δ + 1) برای بدست آوردن دورهای ارتباطی( Θ ( n به بدترین حالت نیاز دارد - ممکن است اطلاعات از یک طرف شبکه به طرف دیگر منتقل شود.

ساده ترین حالت جالب یک IS N - چرخه . ریچارد کول و اوزی ویشکین [15] نشان می دهند که یک الگوریتم توزیع شده وجود دارد که تعداد رنگ ها را از n به O (log n ) در یک مرحله ارتباطی همزمان کاهش می دهد. با تکرار همین روال ، می توان 3 رنگ یک چرخه n را در مراحل ارتباطی O ( log * n ) بدست آورد (با فرض اینکه ما یک شناسه گره منحصر به فرد داریم).

ورود به سیستم تابع * ، لگاریتم تکرار شده ، یک تابع به آرامی در حال رشد است ، "تقریباً ثابت". از این رو نتیجه توسط کول و ویشکین این سؤال را ایجاد می کند که آیا یک الگوریتم توزیع زمان ثابت برای 3 رنگ آمیزی چرخه n وجود دارد یا خیر . Linial (1992) نشان داد كه این امر امكان پذیر نیست: هر الگوریتم توزیع كننده قطعی نیاز به مراحل ارتباطی Ω ( log * n ) برای كاهش n- colouring به 3 رنگ در چرخه n دارد .

این تکنیک توسط کول و ویشکین می تواند در نمودارهای سطح محدود دلخواه نیز اعمال شود. زمان اجرا پلی (Δ) + O است ( log * n ). [16] این تکنیک توسط اشنایدر و همکاران به نمودارهای دیسک واحد گسترش یافت . [17] سریعترین الگوریتم های تعیین کننده برای نقاشی (Δ + 1) برای Δهای کوچک به دلیل لئونید بارنبیم ، مایکل الکین و فابیان کوهن است. [18] الگوریتم Barenboim و همکاران. در زمان O (Δ) + log * ( n ) / 2 اجرا می شود که از نظر n بهینه است زیرا فاکتور ثابت 1/2 به دلیل محدودیت پایین Linial نمی تواند بهبود یابد.Panconesi و Srinivasan (1996) از تجزیه شبکه برای محاسبه یک رنگ آمیزی Δ + 1 به موقع استفاده می کنند $2 ^ {O \ چپ ({\ sqrt {\ log n}} \ سمت راست)$ .

مشکل رنگ آمیزی لبه نیز در مدل توزیع شده مورد بررسی قرار گرفته است. Panconesi و Rizzi (2001) در این مدل به O ( ΔΔ + log * n ) با رنگ آمیزی (2Δ - 1) رسیدند . حد پایین برای رنگ آمیزی vertex توزیع شده به دلیل Linial (1992) نیز برای مسئله رنگ آمیزی لبه توزیع شده اعمال می شود.

منبع

https://en.wikipedia.org/wiki/Graph_coloring

+ نوشته شده در یکشنبه هجدهم خرداد ۱۳۹۹ ساعت 6:56 توسط علی رضا نقش |

کامپیوتر و ریاضی با علی رضا نقش

آموزش