موضوع مقاله: رنگ‌آمیزی کامل گراف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # رنگ‌آمیزی کامل گراف | مقدمه: عدد رنگی کامل این گراف ۶ است زیرا درجهٔ هر راس ۵ است (۵ راس مجاور + ۱خود راس=۶) در نظریه گراف، رنگ‌آمیزی کامل گراف یک نوع از رنگ‌آمیزی یالها و راسهای گراف می‌باشد. | ## بخش 1: رنگ‌آمیزی کامل گراف | اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه‌است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند. عدد رنگی کامل (χ(G یک گراف حداقل تعداد رنگهای لازم برای رنگ آمیزی کامل یک گراف G است. گراف کامل T = T(G) گراف G یک گراف است با این شرایط: اولاً اینکه مجموعهٔ رئوس T متناظر باشند با رئوس و یالهای G و دوماً اینکه دو راس در T مجاورند اگر و فقط اگر عناصر متناظر آن‌ها در G یا مجاور باشند یا متلاقی. اصطلاح «رنگ آمیزی کامل» و عبارت «حدس رنگ آمیزی کامل» در موقعیت‌های زیادی (در سال‌های ۱۹۶۴ و ۱۹۶۸) توسط بهزاد و وایزینگ به‌طور مستقل مورد استفاده قرار گرفته‌است. حدس رنگ آمیزی کامل فقط برای دستهٔ کوچک ولی مهمی از گرافها مثل تمام گرافهای دوبخشی و اکثر گرافهای مسطح به جز آنهایی که دارای حداکثر درجهٔ ۶ هستند؛ برقرار می‌باشد. اگر 'حدس گراف مسطح وایزینگ' درست باشد رنگ آمیزی کامل تمام گرافهای مسطح را دربر خواهد گرفت. این قضیه (وایزینگ) برای همه گرافهای بدون طوقه معتبر است تعداد ماکسیمم یالهایی که دو راس G را به هم متصل می‌کنند چندگانگی G می‌نامند و ان را با (G)µ نشان می‌دهند. | ## بخش 2: رنگ‌آمیزی کامل گراف | اکنون می‌توانیم قضیه وایزینگ را در حالتی کاملاً بیان کنیم : اگر G بدون طوقه باشد انگاه ∆ + µ ≤ ׳x ∆ ≤ این قضیه بدین معنا بهترین است که برای هر µ گراف G موجود است به‌طوری‌که ∆ + µ = ׳x برهان : فرض کنید G گرافی ساده‌است. تنها لازم است که نشان دهیم x′ ≤ ∆ + 1 در این صورت، فرض کنید که، .x′>∆+1 فرض کنید که ϐ = (E1,E2,..., ∆+1E) (1+∆)-رنگ امیزی یالی اپتیمالG بوده و u راسی باشد به‌طوری‌که d(u)>c(u) د این صورت رنگهای i0,i1 وجود دارند که i0 در u ارائه نشده وi1 حداقل دو بار در u ارائه شده‌است. چون∆+1>d(v1)، رنگی مانند i2 در v1 ارائه نشده‌است.اکنون i2 باید در u ارائه شود، زیرا در غیر این صورت، با رنگ امیزی دوباره uv1 با i2، اصلاحی برای ϐ به دست می‌آوریم. دوباره، چون ∆+1>d(v2)، رنگی مانند i3 در v2 ارائه نشده وi3 باید در u ارائه شود زیرا در غیر این صورت، با رنگ امیزی دوبارهuv1 با i3 وuv2 باi3، یک(∆+1)-رنگ امیزی یالی اصلاح شد را به دست می‌آوریم. چون درجه u متناهی است، کوچکترین عدد صحیح l ی وجود دارد به‌طوری‌که برای مقداری از k با شرط l>kو 1+jI= k این وضعیت در شکل الف رسم شده‌است. تعاریف و قضایا رنگ‌آمیزی یالیk: رنگ امیزی یالی ϐاز گراف بدون طوقه G تخصیص k رنگ 3,2,1,...k به یالهای G است. متقابلاً K-رنگ امیزی یالی را می‌توان به صورت یک افراز (E1,E2,...,Ek) از E تصور کرد، که در ان Ei زیرمجموعه‌ای (احتمالاً خالی) از E را نشان می‌دهد که رنگ i را اختیار کرده‌است. | ## بخش 3: رنگ‌آمیزی کامل گراف | پس k-رنگ امیزی یالی سره، k-رنگ امیزی یالی (E1, E2,...,Ek) است که در ان هر زیرمجموعهٔ Ei یک جورسازی است. اگر بدانیم از معلمXi خواسته شده‌است که در کلاس Yj برای دوره‌های Pij تدریس کند، جدول زمانی کاملی را با مینیمم تعداد دوره‌های ممکن برنامه‌ریزی کنید. این مسئله به مسئله جدول زمانی مشهور است، و می‌توان ان را کاملاً با استفاده از نظریهٔ رنگ امیزی یالی حل کرد. و تدریس در هر کلاس به وسیلهٔ حداکثر یک معلم می‌تواند انجام شود این، حداقل، پذیره ماست. لذا برنامه‌ریزی اموزشی برای یک دوره متناظر با جورسازی در گراف است و، بر عکس، هر جورسازی، متناظر با تخصیصی ممکن از معلمان به کلاسها برای یک دورا است. بنابراین، مسئلهٔ ما افرازهای یالهای G به کمترین جورسازی‌های ممکن، یا هم ارز ان، رنگ امیزی مناسب یالهای G با کمترین رنگ ممکن است. چون G دوبخشی است، می‌دانیم که x′ = ∆ لذا اگر هیچ معلمی برای بیش از p دوره درس ندهد، و اگر در هیچ کلاسی برای بیش ازp یوره تدریس نشود. | ## جمع‌بندی | این تعمیم مسئله جدول زمانی را دمپستر(1971)و دوورا(1970)مطالعه کرده‌اند.باندی، مورلی، نظریه گراف و کاربردهای ان، ترجمهٔ دارا معظمی، مرکز نشر دانشگاهی.