رنگ آمیزی¶
رنگ آمیزی راسی¶
در رنگ آمیزی راسی، به هر راس یک رنگ تعلق می گیرد به طوری که دو راس مجاور دو رنگ مختلف داشته باشند.
K رنگ پذیر¶
اگر بتوانیم با حداکثر k رنگ راس های گرافی را رنگ کنیم به آن گراف k رنگ پذیر می گوییم.
K رنگ آمیزی مناسب¶
اگر در رنگ آمیزی راس ها از k رنگ استفاده کنیم (به ازای هر رنگ z، راسی وجود داشته باشد که در رنگ آمیزی به رنگ z باشد)، به رنگ آمیزی انجام شده، k رنگ آمیزی مناسب می گوییم.
عدد رنگی¶
به گرافی k رنگ پذیر باشد ولی k - 1 رنگ پذیر نباشد، k رنگی گفته می شود. به k، عدد رنگی گراف گفته می شود که آن را به صورت χ(G) = k نشان می دهند. در واقع عدد رنگی یک گراف کمترین تعداد رنگ مورد نیاز برای رنگ کردن راس های گراف را نشان می دهد.
رنگ آمیزی یالی¶
اگر بتوان یال های یک گراف را با k رنگ رنگ آمیزی کرد گوییم آن گراف k رنگ پذیر یالی است.
عدد رنگی یالی¶
اگر گرافی k رنگ پذیر یالی باشد ولی k - 1 رنگ پذیر یالی نباشد گوییم این گراف k رنگی یالی است. در اینجا k عدد رنگی یالی گراف محسوب می شود و آن را به صورت χ′(G) = k نشان می دهیم.
اطلاعاتی درباره رنگ آمیزی¶
نقشه ها را جوری رنگ آمیزی می کنند تا دو کشور همسایه رنگ یکسان نداشته باشند. اما سوال اینجا بود که کمترین تعداد رنگ مورد نیاز برای رنگ کردن چقدر است و فرانسیس گاثری اولین کسی بود که احتمال داد هر نقشه با ۴ رنگ قابل رنگ آمیزی است و در سال ۱۹۷۶ احتمال گاثری به کمک کامپیوتر اثبات شد و به قضیه تبدیل شد.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
