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

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

سایر رنگها [ ویرایش ]

نظریه رمزی [ ویرایش ]

کلاس مهمی از مشکلات نادرست در رنگ آمیزی در نظریه رمزی ، که لبه های نمودار به رنگ ها اختصاص داده شده است ، مورد مطالعه قرار می گیرد و محدودیتی در رنگ لبه های حادثه دیده نمی شود. یک مثال ساده ، قضیه دوستی است ، که بیان می کند در هر رنگ آمیزی از لبه های $K_ {6$ ، نمودار کامل شش رئوس ، یک مثلث تک رنگ وجود خواهد داشت. غالباً با گفتن اینكه هر گروه شش نفره یا سه فرد غریبه یا سه آشنای متقابل دارند ، نشان داده می شود. نظریه رمزی با کلیات این ایده در جستجوی نظم در میان اختلال و یافتن شرایط عمومی برای وجود زیرگرافهای تک رنگ با ساختار خاص است.

سایر رنگها [ ویرایش ]

رنگ مجاور- vertex- مشخص کننده کل

یک رنگ کلی با محدودیت اضافی که هر دو راس مجاور دارای مجموعه های مختلف رنگ هستند

رنگ آمیزی حلقوی

هر زیرگراف 2-کرومیک غیرقانونی است

رنگ آمیزی ب

رنگ آمیزی راسهایی که در آن هر کلاس رنگ دارای یک راس است که در همه کلاسهای رنگ دیگر همسایه دارد.

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

با انگیزه سیستم های وظیفه ای که در آن تولید به روش چرخشی انجام می شود

زیبایی

یک رنگ آمیزی صحیح راس که در آن هر کلاس رنگ باعث ایجاد یک مجموعه مستقل یا یک کلیشه می شود

رنگ آمیزی کامل

هر جفت رنگ حداقل در یک لبه ظاهر می شود

نقص نقص

رنگ آمیزی نامناسب ورته که در آن هر کلاس رنگ باعث ایجاد یک زیرگراف درجه محدود می شود.

تشخیص رنگ آمیزی

یک نقوش راس نادرست که همه تقارن های نمودار را از بین می برد

رنگ آمیزی عادلانه

اندازه کلاس رنگ حداکثر یک متفاوت است

رنگ آمیزی دقیق

هر جفت رنگ دقیقاً در یک لبه ظاهر می شود

رنگ آمیزی کسری

گرتك ها ممكن است دارای چندین رنگ باشند و در هر لبه تعداد قسمت های رنگی هر راس از یكدیگر بیشتر نیست

رنگ آمیزی همیلتون

از طول طولانی ترین مسیر بین دو راس ، که به عنوان فاصله دوری نیز شناخته می شود ، استفاده می کند

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

هر جفت رنگ حداکثر در یک لبه ظاهر می شود

رنگ آمیزی بروز

هر بروز مجاور ورت و لبه با رنگهای مشخصی رنگ آمیزی می شود

رنگ آمیزی لبه فاصله

رنگ لبه هایی که در یک راس مشترک قرار دارند ، باید متناقض باشد

لیست رنگ آمیزی

هر راس از لیست رنگ ها انتخاب می کند

لیست رنگ آمیزی را لبه کنید

هر لبه از لیست رنگ ها انتخاب می کند

L (ح ، ک) رنگ آمیزی

تفاوت رنگها در راسهای مجاور حداقل h و تفاوت رنگهای رئوس در فاصله دو حداقل k است . مورد خاص ، رنگ L (2،1) است .

رنگ آمیزی جهت دار

جهت گیری لبه های نمودار را در نظر می گیرد

رنگ آمیزی مسیر

یک مشکل مسیریابی را در نمودارها مدل می کند

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

مجموع فاصله بین رئوس ها و تفاوت رنگ آنها از k + 1 بیشتر است ، در جایی که k عدد صحیح مثبت است.

رتبه بندی رنگ آمیزی

اگر دو رأس دارای یک رنگ i مشابه باشند ، پس هر مسیری بین آنها دارای یک راس با رنگ بیشتر از من است

زیر سازی

رنگ آمیزی نامناسب ورته که در آن هر کلاس رنگ باعث ایجاد اتحادیه کلیشه ها می شود

جمع کردن رنگ

ملاک به حداقل رساندن جمع رنگها است

رنگ آمیزی ستاره

هر زیرگرافی 2-کروماتیک مجموعه ای جدا از ستاره است

رنگ آمیزی قوی

هر رنگ دقیقاً یک بار در هر پارتیشن با اندازه مساوی ظاهر می شود

رنگ آمیزی لبه قوی

لبه ها به گونه ای رنگ شده اند که هر کلاس رنگ تطبیق را ایجاد می کند (معادل رنگ آمیزی مربع نمودار خط)

رنگ آمیزی T

مقدار مطلق تفاوت بین دو رنگ راسهای مجاور نباید به مجموعه ثابت T تعلق داشته باشد

کل رنگ آمیزی

گره ها و لبه ها رنگی هستند

مرکز رنگ آمیزی

هر زیرگراف القایی متصل دارای رنگی است که دقیقا یکبار استفاده می شود

رنگ بدون لبه مثلث

لبه ها به گونه ای رنگ شده اند که هر کلاس رنگ یک زیرگراف عاری از مثلث تشکیل می دهد

رنگ آمیزی ضعیف

یک نقوش راس نادرست که در آن هر گره غیر منزوی حداقل یک همسایه با رنگ متفاوت دارد

همچنین می توان رنگ آمیزی را برای نمودارهای امضا شده در نظر گرفت و نمودارهایی را بدست آورد .

منبع

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

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

ادامه رنگ آمیزی نمودار:الگوریتم های غیر متمرکز و پیچیدگی محاسباتی

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

الگوریتم های غیر متمرکز غیرمستقیم مواردی هستند که ارسال پیام مجاز نیست (برخلاف الگوریتم های توزیع شده در جایی که پیام محلی می گذرد) و الگوریتم های غیرمتمرکز کارآمد وجود دارند که در صورت وجود یک رنگ مناسب ، یک نمودار را رنگ می کنند. اینها فرض می کنند که یک راس قادر به درک اینکه آیا هر یک از همسایگان خود از همان رنگ راس استفاده می کنند ، یعنی اینکه یک درگیری محلی وجود داشته باشد ، می تواند احساس کند. این یک فرض خفیف در بسیاری از برنامه ها است ، به عنوان مثال در تخصیص کانال بی سیم معمولاً منطقی است که فرض کنیم یک ایستگاه می تواند تشخیص دهد که آیا فرستنده های مداخله کننده دیگر از همان کانال استفاده می کنند (به عنوان مثال با اندازه گیری SINR). این اطلاعات سنجش برای اجازه دادن به الگوریتم های مبتنی بر اتومات های یادگیری کافی است تا یک رنگ مناسب نمودار را با احتمال یک پیدا کنند. [19]

پیچیدگی محاسباتی [ ویرایش ]

رنگ آمیزی نمودار از نظر محاسباتی سخت است. این تصمیم گیری NP-کامل است اگر یک نمودار معین ، k- colouring را برای یک k داده شده به جز موارد {0،1،2} قبول کند یا خیر . به طور خاص ، محاسبه شماره کروماتیک NP سخت است. [20] مشکل 3 رنگ NP- کامل حتی در نمودارهای مسطح 4 عادی است . [21] با این حال ، برای هر k > 3 ، رنگ آمیزی k از یک نمودار مسطح توسط چهار قضیه رنگ وجود دارد ، و می توان در زمان چند جمله ای چنین رنگ آمیزی را یافت.

بهترین الگوریتم تقریبی شناخته شده ، رنگ آمیزی اندازه را حداکثر در یک فاکتور O ( n (ورود به سیستم n ) 2 (ورود به سیستم) 3 ) از تعداد کروماتیک محاسبه می کند. [22] برای همه ε > 0، مقدار تقریبی عدد رنگی در N 1- ε است NP-hard است . [23]

همچنین رنگ آمیزی یک نمودار 3 رنگی با 4 رنگ [24] و یک نمودار k- colourable با k (log k ) / 25 رنگ برای K به اندازه کافی بزرگ ، همچنین NP دشوار است . [25]

محاسبه ضرایب چند جمله ای کروماتیک # P-hard است . در واقع ، حتی محاسبه مقدار $\ چی (G ، K)$ در هر نقطه عقلانی k به جز k = 1 و k = 2. [26] هیچ FPRAS برای ارزیابی چند جمله ای کروماتیک در هر نقطه منطقی k- 1.5 1.5 به جز k = 2 وجود ندارد مگر اینکه NP = RP باشد. [27]

برای رنگ آمیزی لبه ، اثبات نتیجه Vizing به یک الگوریتم می دهد که بیشتر از Δ + 1 رنگ استفاده می کند. با این حال ، تصمیم گیری بین دو مقدار نامزد برای تعداد کروماتیکی لبه NP کامل است. [28] از نظر الگوریتم های تقریبی ، الگوریتم Vizing نشان می دهد که تعداد کروماتیکی لبه می تواند در 4/3 تقریب یابد و نتیجه سختی نشان می دهد که هیچ الگوریتم (4/3 - ε ) برای هر ε> 0 وجود ندارد ، مگر اینکه P = NP . اینها از قدیمی ترین نتایج در ادبیات الگوریتم های تقریبی است ، حتی اگر هیچ یک از کاوشها از این مفهوم استفاده صریح نکنند. [29]

برنامه ها [ ویرایش ]

برنامه ریزی [ ویرایش ]

مدل های رنگ آمیزی عمودی به تعدادی از مشکلات برنامه ریزی . [30] در خالص ترین شکل ، مجموعه مشخصی از کارها باید به شکاف های زمانی اختصاص داده شوند ، هر کار به یک شکاف از این دست نیاز دارد. مشاغل به هر ترتیب می توانند برنامه ریزی شوند ، اما ممکن است جفت مشاغل در تضاد باشند به این معنا که ممکن است به یک شکاف زمانی اختصاص داده نشوند ، به عنوان مثال زیرا هر دو به یک منبع مشترک اعتماد دارند. نمودار مربوطه شامل یک محور برای هر شغل و لبه ای برای هر جفت متضاد کار است. تعداد کروماتیکی نمودار دقیقاً حداقل طول کارکرد ، زمان بهینه برای به پایان رساندن کلیه کارها بدون درگیری است.

جزئیات مشکل برنامه ریزی ساختار نمودار را مشخص می کند. به عنوان مثال ، هنگام اختصاص هواپیما به پروازها ، نمودار درگیری ناشی از آن یک نمودار فاصله ای است ، بنابراین می توان مشکل رنگ آمیزی را به صورت کارآمد حل کرد. در اختصاص پهنای باند به ایستگاه های رادیویی ، نمودار درگیری ناشی از آن یک نمودار دیسک واحد است ، بنابراین مشکل رنگ آمیزی 3-تقریبی است.

تخصیص ثبت نام [ ویرایش ]

مقاله اصلی: تخصیص ثبت نام

کامپایلر است برنامه کامپیوتری که یکی ترجمه زبان کامپیوتر را به دیگری. به منظور بهبود زمان اجرای کد در نتیجه، یکی از تکنیک های بهینه سازی کامپایلر است تخصیص ثبت نام ، که در آن ارزش ها اغلب استفاده می شود از برنامه های وارد شده در سریع نگه داشته ثبات های پردازنده . در حالت ایده آل ، مقادیر به ثبات ها اختصاص داده می شوند تا در صورت استفاده همه بتوانند در رجیسترها اقامت کنند.

رویکرد کتاب درسی برای این مشکل ، مدل کردن آن به عنوان یک مشکل رنگ آمیزی نمودار است. [31] کامپایلر یک نمودار تداخل ایجاد می کند ، که در آن رئوس ها متغیر هستند و یک لبه در صورت نیاز در همان زمان دو راس را به هم متصل می کند. اگر نمودار را می توان با رنگی K رنگ پس از آن هر مجموعه ای از متغیرهای مورد نیاز در همان زمان می توان در حداکثر ذخیره شده ک ثبات.

برنامه های دیگر [ ویرایش ]

مشکل رنگ آمیزی نمودار در بسیاری از زمینه های عملی از قبیل تطبیق الگوی ، برنامه ریزی ورزشی ، طراحی برنامه های صندلی ، جدول زمانی امتحانات ، برنامه ریزی تاکسی ها و حل معماهای سودوکو بوجود می آید . [32]

منبع

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

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

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

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

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

تصمیم گیری
نام	نمودار رنگ آمیزی، راس رنگ آمیزی، 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 توسط علی رضا نقش |

ادامه رنگ آمیزی نمودار:خواص

خواص [ ویرایش ]

مرزهای بالای شماره کروماتیک [ ویرایش ]

انتساب رنگ های مجزا به رئوس های مشخص همیشه به یک رنگ آمیزی مناسب می انجامد

$\ displaystyle 1 \ leq \ chi (G) \ leq n.$

تنها نمودارهایی که می توانند 1 رنگ باشند نمودارهای بدون لبه هستند . گراف کامل $K_ {n$ از n vertices نیاز دارد $\ chi (K_ {n}) = n$ رنگها در یک رنگ بهینه باید حداقل یکی از لبه های m نمودار بین هر جفت کلاس رنگ وجود داشته باشد

$\ displaystyle \ chi (G) (\ chi (G) -1) \ leq 2m.$

اگر G حاوی یک کلیشه به اندازه k باشد ، حداقل برای رنگ آمیزی آن کلیشه حداقل به رنگ k نیاز است. به عبارت دیگر ، شماره کروماتیک حداقل عدد کلیشه است:

\ displaystyle \ chi (G) \ geq \ omega (G). $\ displaystyle \ chi (G) \ geq \ omega (G).$

برای نمودارهای کامل ، این محدود محکم است. یافتن کلکسیون به عنوان مشکل کلیکی شناخته می شود .

نمودارهای دو رنگ دقیقاً نمودارهای دو طرفه از جمله درختان و جنگلها هستند. با قضیه چهار رنگ ، هر نمودار مسطح می تواند 4 رنگ باشد.

یک نقاشی حریص نشان می دهد که هر نمودار می تواند با یک رنگ بیشتر از حداکثر درجه راس ،

$\ displaystyle \ chi (G) \ leq \ Delta (G) +1.$

نمودارهای کامل دارند $\ chi (G) = n$ و $\ دلتا (G) = n-1$ ، و چرخه های عجیب و غریب دارند $\ chi (G) = 3$ و $\ دلتا (G) = 2$ بنابراین برای این نمودارها این حد به بهترین شکل ممکن است. در سایر موارد ، محدودیت را می توان کمی بهبود بخشید. قضیه بروکس [4] اظهار می دارد که

قضیه بروکس : $\ chi (G) \ leq \ Delta (G)$ برای یک نمودار ساده G ، متصل ، مگر اینکه G یک نمودار کامل یا یک چرخه عجیب باشد.

مرزهای پایین روی عدد کروماتیک [ ویرایش ]

چندین مرز پایین تر برای مرزهای کروماتیک طی سالها کشف شده است:

هافمن محدود: اجازه دهید{\ نمایشگر W} $W$ یک ماتریس متقارن واقعی باشد به گونه ای که $W_ {i، j} = 0$ هر زمان که {\ نمایشگر (من ، ج) $(من ، ج)$ لبه در نیست display \ نمایشگر G} $ج$ . تعريف كردن $\ displaystyle \ chi _ {W} (G) = 1 - {\ tfrac {\ lambda _ {\ max} (W) {\ lambda _ {\ min} (W)}}$ ، جایی که $\ displaystyle \ lambda _ {\ max} (W) ، \ lambda _ {\ min} (W)$ بزرگترین و کوچکترین مقادیر ویژه ای هستند {\ نمایشگر W} $W$ . تعريف كردن $\ chi _ {H} (G) = \ max _ {W} \ chi _ {W} (G)$ ، با $W$ مانند بالا. سپس:

$\ chi _ {H} (G) \ leq \ chi (G)$ .

بردار شماره کروماتیک : بگذارید $W$ یک ماتریس نیمه قطعی مثبت باشد به گونه ای که $\ displaystyle W_ {i، j} \ leq - {\ tfrac {1} {k-1}}}$ هر زمان که {\ نمایشگر (من ، ج) $(من ، ج)$ یک لبه در است display \ نمایشگر G} $ج$ . تعريف كردن $\ chi _ {V} (G)$ کمترین k برای چنین ماتریسی باشد $W$ وجود دارد سپس

$\ displaystyle \ chi _ {V} (G) \ leq \ chi (G).$

شماره Lovász : شماره Lovász از یک نمودار مکمل ، همچنین دارای علامت کمتری بر روی عدد رنگی است:

${\ displaystyle \ vartheta ({\ bar {G}}) \ leq \ chi (G).$

تعداد کروماتیکی کسری : تعداد کروماتیکی کسری از یک نمودار ، دارای علامت کروماتیک پایین تر است:

$\ displaystyle \ chi _ {f} (G) \ leq \ chi (G).$

این محدوده به شرح زیر سفارش داده می شود:

$\ displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ چی (G).$

نمودارهایی با تعداد کروماتیک بالا [ ویرایش ]

نمودارهایی با کلیشه های بزرگ دارای تعداد کروماتیکی بالایی هستند ، اما برعکس درست نیست. نمودار Grötzsch یک مثال از یک نمودار 4-رنگی بدون یک مثلث است و به عنوان مثال می توان به تعمیم Mycielskians .

قضیه مایکلسکی ( الکساندر زیکوف 1949 ، یان میسیسکی 1955 ): نمودارهای بدون مثلث با عدد کروماتیک خودسرانه زیاد وجود دارد.

از قضیه بروکس ، نمودارهایی با عدد کروماتیک بالا باید حداکثر درجه بالایی داشته باشند. یکی دیگر از دارایی های محلی که منجر به تعداد بالای کروماتیک می شود ، وجود یک کلیس بزرگ است. اما رنگ پذیری یک پدیده کاملاً محلی نیست: گرافیکی با سطح بالای درخت محلی به نظر می رسد مانند یک درخت ، زیرا همه چرخه ها طولانی هستند ، اما تعداد کروماتیکی آن لازم نیست 2:

قضیه (Erdős): نمودارهایی از محور دلخواه بالا و تعداد کروماتیک وجود دارد. [5]

محدودیت های شاخص کرومیک [ ویرایش ]

یک رنگ آمیزی لبه G رنگ آمیزی از نمودار خط آن است $L (G)$ ، و بالعکس. بدین ترتیب،

${\ displaystyle \ chi '(G) = \ chi (L (G)).$

بین رنگ پذیری لبه و حداکثر درجه نمودار رابطه قوی وجود دارد $\ دلتا (ج)$ . از آنجا که همه حواشی به یک راس مشابه نیاز به رنگ خاص خود دارند ، ما داریم

${\ displaystyle \ chi '(G) \ geq \ Delta (G).$

علاوه بر این،

قضیه Kőnig : $\ chi '(G) = \ Delta (G)$ اگر G دو طرفه است.

به طور کلی ، این رابطه حتی از آنچه قضیه بروکس برای رنگ آمیزی راس می دهد ، قوی تر است:

قضیه Vizing: نمودار حداکثر $\ دلتا$ دارای عدد کروماتیکی لبه است $\ دلتا$ یا $\ دلتا +1$ .

خواص دیگر [ ویرایش ]

نمودار دارای یک رنگ k است اگر و فقط اگر دارای جهت گیری حلقوی باشد که طولانی ترین طول آن حداکثر در طول k باشد . این قضیه Gallai-Hasse-Roy-Vitaver است ( Nešetřil & Ossona de Mendez 2012 ).

برای نمودارهای مسطح ، رنگهای ورته اساساً جریانهای صفر تا هیچ جا ندارند .

درباره نمودارهای نامتناهی ، بسیار کمتر شناخته شده است. در زیر دو از معدود نتیجه در مورد رنگ آمیزی نمودار نامحدود است:

اگر همه زیرگرافهای محدود یک نمودار بی نهایت G هستند ک -colorable، پس است G ، با این فرض از اصل موضوع انتخاب . این قضیه دو بروجن-ارده از دی بروجن و اردوس (1951) است .
اگر یک گراف اذعان کامل N -coloring برای هر نفر ≥ N 0 ، آن اذعان یک رنگ آمیزی کامل بی نهایت ( فاوست 1978 ).

مشکلات باز [ ویرایش ]

همانطور که در بالا اشاره شد، $\ displaystyle \ omega (G) \ leq \ chi (G) \ leq \ Delta (G) +1.$ حدس رید از سال 1998 این است که ارزش اساساً به مرز پایین نزدیکتر است $\ displaystyle \ chi (G) \ leq \ left \ lceil {\ frac {\ omega (G) + \ Delta (G) +1} {2}} \ Right \ rassil.$

عدد رنگی از هواپیما ، که در آن دو نقطه مجاور هستند اگر آنها واحد فاصله، ناشناخته است، هرچند آن را یکی از 5، 6، یا 7. دیگر است مشکلات باز در مورد عدد رنگی نمودار شامل حدس Hadwiger بیان کرد که هر نمودار با عدد کروماتیکی k یک نمودار کامل در رأس های k به عنوان جزئی ، حدس Erdős-Faber-Lovász را محدود می کند که تعداد کروماتیکی از اتحادیه های نمودارهای کامل را که حداکثر یک راس مشترک با هر جفت دارد ، و حدس آلبرسون را در بین k نمودارهای كروماتیك نمودارهای كامل آنهایی هستند كه دارای كوچكترین هستندعبور تعداد .

هنگامی که بیرخوف و لوئیس چند جمله ای کروماتیک را در حمله به قضیه چهار رنگ معرفی کردند ، آنها حدس زدند که برای نمودارهای مسطح G ، چند جمله ای $P (G ، t)$ هیچ صفر در منطقه ندارد $[4 ، \ infty)$ . اگرچه مشخص است که چنین چند جملهای کرومیک صفر در منطقه ندارد $[5 ، \ infty)$ و آن $P (G ، 4) \ neq 0$ ، حدس آنها هنوز حل نشده است. همچنین برای توصیف نمودارهایی که دارای چند جملهای کرومیک یکسان هستند و تعیین اینکه چند چند جمله ای دارای رنگی هستند ، یک مشکل حل نشده است.

منبع

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

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

رنگ آمیزی نمودار :تعریف و اصطلاحات

تعریف و اصطلاحات [ ویرایش ]

این نمودار به 12 روش مختلف می تواند 3 رنگ باشد.

رنگ آمیزی عمودی [ ویرایش ]

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

اصطلاحات استفاده از رنگ ها برای برچسب های vertex به رنگ آمیزی نقشه برمی گردد. از برچسب هایی مانند قرمز و آبی فقط در مواردی استفاده می شود که تعداد رنگ ها کمی باشد ، و به طور معمول درک می شود که برچسب ها از عدد صحیح 1 ، 2 ، 3 ، ... drawn کشیده می شوند.

رنگ آمیزی با استفاده از حداکثر K رنگ است (مناسب) به نام K -coloring . به کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی یک نمودار G ، تعداد کرواتیکی آن گفته می شود و اغلب به χ ( G ) اشاره می شود. گاهی اوقات γ ( G ) استفاده می شود ، زیرا χ ( G ) نیز برای مشخص کردن ویژگی اویلر یک نمودار استفاده می شود. یک نمودار است که می توان اختصاص (مناسب) K -coloring است ک -colorable ، و آن است ک -chromatic اگر عدد رنگی آن است که دقیقا ک . زیر مجموعه ای از رئوس ها که به همان رنگ اختصاص داده می شوند ، یک کلاس رنگ نامیده می شود ، هر کلاس چنین مجموعه مستقل را تشکیل می دهد . بنابراین ، k- colour همان قسمت جدائی از راس است که به مجموعه های مستقل k تبدیل شده است ، و اصطلاحات k-partite و k-colorable معنی مشابهی دارند.

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

کلیه نمودارهای غیر همسان در 3 راس و چند جملههای کروماتیک آنها. نمودار خالی E 3 (قرمز) 1 رنگ را تصدیق می کند. دیگران اعتراف نمی کنند چنین نقاشی هایی داشته باشند. نمودار سبز 12 رنگ با 3 رنگ را پذیرفته است.

مقاله اصلی: چند جمله ای Chromatic

چند جمله ای رنگی شمارش تعدادی از راه های یک گراف می توان با استفاده بیش از یک عدد داده شده از رنگ، رنگ آمیزی. به عنوان مثال ، با استفاده از سه رنگ ، نمودار موجود در تصویر مجاور می تواند به 12 روش رنگی شود. تنها با دو رنگ ، به هیچ وجه نمی توان رنگ آمیزی کرد. با چهار رنگ ، می توان آن را به صورت 24 + 4 = 12 = 72 رنگ آمیزی کرد: با استفاده از هر چهار رنگ ، 4 عدد وجود دارد! = 24 رنگ معتبر ( هر انتساب چهار رنگ به هر نمودار 4-vertex یک رنگ آمیزی مناسب است)؛ و برای هر انتخاب از سه چهار رنگ ، 12 رنگ 3 رنگ معتبر وجود دارد. بنابراین ، برای نمودار موجود در مثال ، جدول تعدادی از رنگهای معتبر مانند این شروع می شود:

رنگهای موجود	1	2	3	4	...
تعداد نقاشی ها	0	0	12	72	...

چند جمله ای کروماتیک یک تابع P ( G ، t ) است که تعداد رنگ های T رنگی G را شمارش می کند . همانطور که از نام آن مشخص است ، برای یک G خاص ، عملکرد در واقع چند جمله ای در t است . برای نمودار مثال ، P ( G ، t ) = t ( t - 1) 2 ( t - 2) و در واقع P ( G ، 4) = 72.

چند جمله ای کروماتیک حداقل به همان اندازه اطلاعات رنگی G را شامل می شود که تعداد کروماتیک آن نیز هست. در واقع ، χ کوچکترین عدد صحیح مثبت است که ریشه چند جمله ای کرومیکی ندارد

$\ chi (G) = \ min \ {k \، \ colone \، P (G، k)> 0 \.$

چند جمله ای های رنگی برای نمودارهای خاص
مثلث K 3	$t (t-1) (t-2)$
نمودار کامل K n	$t (t-1) (t-2) \ cdots (t- (n-1))$
درخت با N راس	$t (t-1) ^ {n-1$
چرخه C n	$(t-1) ^ {n} + (- 1) ^ {n} (t-1)$
نمودار پیترسن	$t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t- 352)$

رنگ آمیزی لبه [ ویرایش ]

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

لبه رنگ آمیزی از یک گراف رنگ آمیزی مناسب از است لبه ، به این معنی انتساب از رنگ به لبه به طوری که هیچ راس حادثه به دو لبه از همان رنگ است. لبه رنگ آمیزی با K رنگ است که به نام K لبه-رنگ آمیزی و معادل برای این مشکل از پارتیشن بندی مجموعه ای لبه به است ک تطابق . کمترین تعداد رنگ مورد نیاز برای رنگ آمیزی یک لبه G ، شاخص کروماتیک یا عدد کروماتیکی لبه ، χ ′ ( G ) است. رنگ آمیزی Tait یک رنگ 3 لبه از یک نمودار مکعب است . قضیه چهار رنگ معادل این ادعا که هر مکعب مسطح است bridgeless نمودار اذعان رنگ آمیزی تیت.

کل رنگ آمیزی [ ویرایش ]

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

رنگ آمیزی کامل نوعی رنگ آمیزی بر روی رئوس و لبه های یک نمودار است. در صورت استفاده از هرگونه صلاحیت ، همیشه فرض می شود که یک رنگ کامل به این معنا باشد که به هیچ یک از راسهای مجاور ، لبه های مجاور و لبه ها و سرهای انتهایی آن به همان رنگ اختصاص نمی یابد. تعداد کل کروماتیک χ ″ (G) یک نمودار G کمترین رنگ مورد نیاز در هر رنگ آمیزی کل G است.

رنگ آمیزی بدون برچسب [ ویرایش ]

رنگ آمیزی بدون برچسب یک گراف، یک است مدار از یک رنگ آمیزی تحت عمل از گروه automorphism از نمودار. اگر رنگ آمیزی از یک نمودار را تفسیر کنیم $د$ vertices به عنوان یک بردار در $\ mathbb {Z} ^ {d$ ، اقدام به یک های automorphism است جایگشت از ضرایب از رنگ آمیزی. آنالوگهای چند جمله ای کرواتیکی وجود دارد که تعداد رنگ های بدون برچسب یک نمودار را از یک مجموعه رنگ محدود مشخص می شمارد.

منبع

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

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

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

با رنگ آمیزی Edge اشتباه گرفته نشود .

یک رنگ آمیزی مناسب از ورق پیترسن با 3 رنگ ، حداقل تعداد ممکن.

در تئوری نمودار ، رنگ آمیزی نمودار یک مورد خاص از برچسب زدن نمودار است . این یک واگذاری برچسب هایی است که به طور سنتی "رنگ" به عناصر یک نمودار در معرض محدودیت های خاص گفته می شود. در ساده ترین شکل آن ، راهی برای رنگ آمیزی رئوس های یک گراف است به گونه ای که هیچ دو راس مجاور از یک رنگ برخوردار نیستند. به این رنگ آمیزی vertex گفته می شود . به طور مشابه ، یک لبه رنگ آمیزی به هر لبه یک رنگ اختصاص می دهد به طوری که هیچ دو لبه مجاور از یک رنگ برخوردار نیستند ، و رنگ آمیزی صورت از یک نمودار مسطح یک رنگ را به هر صورت یا منطقه اختصاص می دهد به طوری که هیچ دو صورت که دارای یک مرز مشترک هستند. همان رنگ

رنگ آمیزی عمودی معمولاً برای معرفی مشکلات مربوط به رنگ آمیزی نمودار استفاده می شود زیرا سایر مشکلات رنگ آمیزی را می توان به عنوان نمونه رنگ آمیزی راس تبدیل کرد. به عنوان مثال ، رنگ آمیزی یک لبه یک نمودار فقط یک نقوش محور از نمودار خط آن است ، و رنگ آمیزی صورت یک نمودار هواپیما فقط یک نقوش محوری از دوتایی آن است . با این حال ، مشکلات رنگ آمیزی غیر vertex اغلب گفته می شود و مورد مطالعه قرار می گیرد . این تا حدی آموزشی است و بخشی نیز به دلیل اینکه بعضی از مشکلات به بهترین شکل در شکل غیر vertex آنها ، مانند مورد رنگ آمیزی لبه ها مورد بررسی قرار می گیرد.

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

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

توجه: بسیاری از اصطلاحات به کار رفته در این مقاله در واژه نامه تئوری نمودار تعریف شده است .

فهرست

تاریخچه [ ویرایش ]

همچنین ببینید: تاریخچه قضیه چهار رنگ و تاریخ نظریه نمودار

اولین نتایج در مورد رنگ آمیزی نمودار تقریباً منحصراً با نمودارهای مسطح به شکل رنگ آمیزی نقشه ها سروکار دارد . در حالی که تلاش به رنگ یک نقشه از شهرستان از انگلستان، فرانسیس Guthrie بدیهی شمرده حدس چهار رنگ و اشاره کرد که چهار رنگ به رنگ در نقشه به طوری که هیچ مناطق به اشتراک گذاری مرز مشترک همان رنگ دریافت کافی بود. برادر گاتری این سؤال را به معلم ریاضیات خود آگوستوس د مورگان در کالج دانشگاه منتقل کرد ، که در نامه ای به ویلیام همیلتون در سال 1852 اشاره کرد. آرتور کیلی در جلسه انجمن ریاضی لندن این مشکل را مطرح کرد.در سال 1879. در همان سال ، آلفرد کمپ مقاله ای را منتشر کرد که ادعا می کند نتیجه را می گیرد و برای یک دهه مشکل چهار رنگ حل کرد. برای موفقیت خود کمپه عضو انجمن سلطنتی و بعداً رئیس انجمن ریاضی لندن انتخاب شد. [1]

در سال 1890 ، هووود اظهار داشت كه استدلال كمپ اشتباه بوده است. با این حال ، او در این مقاله ، قضیه پنج رنگ را اثبات کرد و گفت که هر نقشه مسطح با استفاده از ایده های کمپ می تواند بیش از پنج رنگ باشد. در قرن بعد ، تعداد زیادی کار و تئوری برای کاهش تعداد رنگها به چهار نفر تدوین شد ، تا اینکه قضیه چهار رنگ بالاخره در سال 1976 توسط کنت اپل و ولفگانگ هاکن ثابت شد . اثبات به عقاید هووود و کمپ برمی گردد و تا حدود زیادی از تحولات مداخله گرانه صرف نظر می کرد. [2] اثبات قضیه چهار رنگ نیز به دلیل اولین اثبات مهم رایانه ای قابل توجه است.

در سال 1912، جورج دیوید Birkhoff معرفی چند جمله ای رنگی به مطالعه مشکلات رنگ آمیزی، که به تعمیم داده شد چند جمله ای Tutte توسط Tutte ، سازه مهم در نظریه گراف جبری . کمپ قبلاً توجه خود را به مورد کلی و غیر مسطح در سال 1879 جلب کرده بود ، [3] و نتایج بسیاری راجع به کلیات رنگ آمیزی نمودارهای مسطح به سطحی با مرتبه بالاتر که در اوایل قرن بیستم دنبال شد.

در سال 1960 ، Claude Berge حدس دیگری را در مورد رنگ آمیزی نمودار ، حدس گرافیکی عالی و کامل ، که در اصل با یک مفهوم اطلاعات نظری به نام ظرفیت خطای صفر گراف ارائه شده توسط شانون ایجاد می شد ، فرموله کرد . این حدس به مدت 40 سال حل نشده باقی ماند ، تا اینکه در سال 2002 به عنوان قضیه نمودار قدرتمند برجسته مشهور توسط چودنوفسکی ، رابرتسون ، سیمور و توماس تاسیس شد.

رنگ آمیزی نمودار از اوایل دهه 1970 به عنوان یک مسئله الگوریتمی مورد مطالعه قرار گرفته است: مشکل شماره کروماتیک یکی از مشکلات 21 NP-کامل کارپ از سال 1972 است ، و تقریباً در همان زمان ، الگوریتم های مختلف نمایی مختلفی مبتنی بر بازگشت به عقب و حذف حذف شد. عود كنترل انقباض زيكوف (1949) . یکی از کاربردهای مهم رنگ آمیزی نمودار ، تخصیص ثبت در کامپایلرها ، در سال 1981 معرفی شد.

منبع

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

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

راس یا Vertex (تئوری نمودار)

نمودار با 6 راس و 7 لبه که در راس شماره 6 در سمت چپ سمت راست یک برگه برگ یا یک راس آویز قرار دارد.

در ریاضیات ، و به طور خاص در نظریه گراف ، یک راس (الجمع راس ) و یا گره واحد بنیادی که نمودار شکل می گیرند: یک گراف بدون جهت متشکل از مجموعه ای از رئوس و مجموعه ای از لبه (جفت نامرتب رأس)، در حالی که گراف جهت متشکل از مجموعه ای از رئوس و مجموعه ای از کمان (زوج مرتب از رئوس). در نمودار نمودار ، یک راس معمولاً توسط یک دایره با یک برچسب نمایش داده می شود و یک لبه توسط یک خط یا فلش نمایش داده می شود که از یک راس به دیگری امتداد دارد.

از نظر تئوری نمودار ، رئوسها به عنوان اشیاء بدون ویژگی و غیرقابل تفکیک رفتار می شوند ، اگرچه بسته به کاربردی که از آن نمودار بوجود می آیند ، ممکن است دارای ساختار اضافی باشند. به عنوان مثال ، یک شبکه معنایی گرافی است که در آن رئوسها مفاهیم یا کلاس اشیاء را نشان می دهند.

گفته می شود که دو راس تشکیل دهنده ی لبه ، نقاط انتهایی این لبه است و گفته می شود که این لبه حادثه ای به سمت راسها است. گفته می شود که یک راس w در حالی که یک نمودار حاوی یک لبه ( v ، w ) باشد ، مجاور یک راس دیگر v است . محله از یک راس V یک IS زیرگراف القایی از نمودار، تشکیل شده توسط تمام رئوس مجاور به V .

فهرست

انواع رئوس [ ویرایش ]

شبکه نمونه با 8 راس (که یکی از آنها جدا شده) و 10 لبه است.

درجه یک راس، δ (V) در یک گراف نشان داده می شود تعداد یال به آن است. راس جدا شده یک راس با درجه صفر است. یعنی یک راس که نقطه پایانی از هر لبه نیست (تصویر مثال یک راس جدا شده را نشان می دهد). [1] راس برگ (همچنین راس آویز ) یک راس با یک درجه است. در یک نمودار کارگردانی ، می توانید outdegree (تعداد لبه های خروجی) ، با علامت 𝛿 + (v) ، از indegree (تعداد لبه های ورودی) ، مشخص شده distingu - (v) را تشخیص دهید. یک راس منبع یک راس با صفر نامشخص است ، در حالی که یک راس سینک یک راس با صفر outdegree است. های simplicial راس همسایه ای است که همسایگانش کلیپی تشکیل می دهند : هر دو همسایه در مجاورت هستند. راس جهانی یک راس است که در مجاورت هر راس دیگر در گراف است.

راس برش یک راس است که با حذف آن می توانید نمودار باقیمانده را جدا کنید. جدا راس مجموعه ای از رئوس حذف که نمودار باقی مانده را به قطعات کوچک جدا است. گراف k- راس متصل یک گراف که از بین بردن کمتر از است ک راس همیشه برگ گراف باقی مانده متصل می شود. یک مجموعه مستقل مجموعه ای از رئوس است که هیچ دو از آنها در مجاورت قرار ندارند و یک پوشش راس مجموعه ای از رئوس است که حداقل یک نقطه انتهایی از هر لبه در نمودار را شامل می شود. فضای راس های یک گراف یک فضای برداری داشتن مجموعه ای از بردارهای پایه متناظر با رئوس گراف است.

نمودار دارای vertex-transitive است اگر دارای تقارنهایی باشد که هر راس را به هر راس دیگر نشان می دهد. در زمینه شمارش نمودار و ایزومورفیسم گراف ، تمایز بین راسهای دارای برچسب و راسهای بدون برچسب مهم است . یک راس برچسب راس است که با اطلاعات اضافی در ارتباط است و باعث می شود تا از دیگر راس های دارای برچسب متمایز شوند. دو نمودار را می توان ایزومورفیک در نظر گرفت که مکاتبات بین رئوس آنها با برچسب های مساوی راسها بالا می رود. یک راس بدون برچسب است که می تواند جایگزین هر راس دیگر شود فقط بر اساس مجاورت آن در نمودار و بر اساس هیچ اطلاعات اضافی نیست.

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

منبع

https://en.wikipedia.org/wiki/Vertex_(graph_theory)

+ نوشته شده در سه شنبه بیست و ششم فروردین ۱۳۹۹ ساعت 7:26 توسط علی رضا نقش |