چگونه شماره رنگی را پیدا کنیم | الگوریتم رنگ آمیزی نمودار

نظریه نمودار

شماره رنگی-

قبل از اینکه این مقاله را مرور کنید ، مطمئن شوید که مقاله قبلی مربوط به شماره Chromatic را مرور کرده اید .

ما بحث کردیم

• Graph Coloring فرایندی است که رنگها را به رئوس یک نمودار اختصاص می دهد.
• این اطمینان حاصل می کند که هیچ دو راس مجاور نمودار با یک رنگ رنگی نیستند.
• Chromatic Number حداقل رنگ مورد نیاز برای رنگ آمیزی صحیح هر نمودار است.

در این مقاله ، ما در مورد چگونگی پیدا کردن شماره Chromatic هر نمودار بحث خواهیم کرد.

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

• هیچ الگوریتمی کارآمد برای رنگ آمیزی نمودار با حداقل تعداد رنگ وجود ندارد.
• نمودار رنگ آمیزی یک مشکل کامل NP است.

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

الگوریتم حریص-

مرحله 01:

اولین راس را با اولین رنگ رنگ کنید.

مرحله 02:

اکنون ، رئوس باقی مانده (V-1) را یکی یکی در نظر بگیرید و موارد زیر را انجام دهید-

• در صورتی که از راس فعلی انتخاب شده برای رنگ آمیزی راسهای مجاور آن استفاده نشده باشد ، با کمترین شماره شماره گذاری شده رنگ آمیزی کنید.
• اگر از آن استفاده شده است ، رنگ بعدی کم شماره را انتخاب کنید.
• اگر از همه رنگهای قبلی استفاده شده است ، یک رنگ جدید به راس فعلی انتخاب شده اختصاص دهید.

اشکال الگوریتم حریص-

اشکال زیر الگوریتم حریصانه فوق وجود دارد -

• الگوریتم فوق همیشه از حداقل تعداد رنگ استفاده نمی کند.
• تعداد رنگهای استفاده شده گاهی به ترتیب پردازش رأس بستگی دارد.

همچنین انواع نمودارها را در تئوری نمودار بخوانید

مشكلات عملي بر اساس يافتن تعداد كروماتيك يك نمودار-

مسئله -01:

شماره رنگی نمودار زیر را پیدا کنید-

راه حل-

با استفاده از الگوریتم حریص ، ما باید-

از اینجا،

• حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 2 رنگ است.
• بنابراین ، Chromatic Number نمودار داده شده = 2.

نمودار داده شده ممکن است به درستی با استفاده از 2 رنگ مطابق شکل زیر رنگ آمیزی شود -

مسئله 02:

شماره رنگی نمودار زیر را پیدا کنید-

راه حل-

با استفاده از الگوریتم حریص ، ما باید-

از اینجا،

• حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 3 است.
• بنابراین ، Chromatic Number نمودار داده شده = 3.

نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

مسئله -03:

شماره رنگی نمودار زیر را پیدا کنید-

راه حل-

با استفاده از الگوریتم حریص ، ما باید-

از اینجا،

• حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 4 است.
• بنابراین ، Chromatic Number نمودار داده شده = 4.

نمودار داده شده ممکن است به درستی با استفاده از 4 رنگ مطابق شکل زیر رنگ آمیزی شود -

مشکل -04:

شماره رنگی نمودار زیر را پیدا کنید-

راه حل-

با استفاده از الگوریتم حریص ، ما باید-

از اینجا،

• حداقل تعداد رنگهایی که برای رنگ آمیزی نمودار داده شده استفاده می شود 3 است.
• بنابراین ، Chromatic Number نمودار داده شده = 3.

نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

مسئله -05:

شماره رنگی نمودار زیر را پیدا کنید-

راه حل-

با استفاده از الگوریتم حریص ،

• حداقل تعداد رنگ های مورد نیاز برای رنگ آمیزی نمودار داده شده 3 است.
• بنابراین ، Chromatic Number نمودار داده شده = 3.

نمودار داده شده ممکن است به درستی با استفاده از 3 رنگ مطابق شکل زیر رنگ آمیزی شود -

برای درک بهتر درباره نحوه یافتن شماره رنگی ،

این سخنرانی ویدئویی را مشاهده کنید

یادداشت های بیشتر و سایر مطالب مطالعه تئوری نمودار را دریافت کنید .

با مراجعه به کانال YouTube ما LearnVidFun ، سخنرانی های ویدیویی را تماشا کنید .

خلاصه

نام مقاله

چگونه شماره رنگی را پیدا کنیم | الگوریتم رنگ آمیزی نمودار

شرح

الگوریتم رنگ آمیزی نمودار - الگوریتمی حریصانه برای رنگ آمیزی نمودار وجود دارد. چگونه می توان تعداد رنگی نمودار را پیدا کرد - ما برای یافتن شماره رنگی نمودار ، الگوریتم حریص را دنبال می کنیم. مشکلاتی در یافتن شماره Chromatic یک نمودار داده شده است.

نویسنده

آکشی سینگال

نام ناشر

دروازه ویدیالی

آرم ناشر