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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک مثال مناسب از رنگ آمیزی کامل با ۶ رنگ. عدد رنگی کامل این گراف ۶ است زیرا درجهٔ هر راس ۵ است (۵ راس مجاور + ۱خود راس=۶)

در نظریه گراف، رنگ‌آمیزی کامل گراف یک نوع از رنگ‌آمیزی یالها و راسهای گراف می‌باشد. اگر این نوع از رنگ آمیزی بدون هیچ شرط و قیدی بیان شود معمولاً اینگونه‌است که هیچ راسی، هیچ یال متلاقی و همچنین هیچ یال و رئوس دو سر آن یک رنگ نباشند.

عدد رنگی کامل (χ(G یک گراف حداقل تعداد رنگهای لازم برای رنگ آمیزی کامل یک گراف G است. گراف کامل T = T(G) گراف G یک گراف است با این شرایط: اولاً اینکه مجموعهٔ رئوس T متناظر باشند با رئوس و یالهای G و دوماً اینکه دو راس در T مجاورند اگر و فقط اگر عناصر متناظر آنها در G یا مجاور باشند و یا متلاقی.

برخی از خصوصیات عدد رنگی کامل :

  1. χ″(G) ≥ Δ(G) + ۱.
  2. χ″(G) ≤ Δ(G) + ۱۰۲۶.
  3. χ″(G) ≤ Δ(G) + ۸ ln۸(Δ(G)).
  4. χ″(G) ≤ ch′(G) + ۲.

در اینجا Δ(G) حداکثر درجهٔ گراف و ch′(G) توانایی انتخاب یالها هستند.

حدس رنگ‌آمیزی کامل (بهزاد و وایزینگ)[ویرایش]

χ″(G) ≤ Δ(G) + ۲.

اصطلاح «رنگ آمیزی کامل» و عبارت «حدس رنگ آمیزی کامل» در موقعیت‌های زیادی (در سالهای ۱۹۶۴ و ۱۹۶۸) توسط بهزاد و وایزینگ به طور مستقل مورد استفاده قرار گرفته‌است. حدس رنگ آمیزی کامل فقط برای دستهٔ کوچک ولی مهمی از گرافها مثل تمام گرافهای دوبخشی و اکثر گرافهای مسطح به جز آنهایی که دارای حداکر درجهٔ ۶ هستند؛ برقرار می‌باشد. اگر 'حدس گراف مسطح وایزینگ' درست باشد رنگ آمیزی کامل تمام گرافهای مسطح را دربر خواهد گرفت.

این قضیه (وایزینگ) برای همه گرافهای بدون طوقه معتبر است تعداد ماکسیمم یالهایی که دو راس G را به هم متصل می‌کنند چندگانگی G می‌نامند و ان را با (G)µ نشان می‌دهند. اکنون می‌توانیم قضیه وایزینگ را در حالتی کاملاً بیان کنیم : اگر 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 ارایه شده‌است. فرض کنید uv1، دارای رنگ i1 باشد. چون∆+1>d(v1)، رنگی مانند i2 در v1 ارایه نشده‌است.اکنون i2 باید در u ارایه شود، زیرا در غیر این صورت، با رنگ امیزی دوباره uv1 با i2، اصلاحی برای ϐ به دست می‌اوریم. لذا یالی مانندuv1 دارای رنگi2 است. دوباره، چون ∆+1>d(v2)، رنگی مانند i3 در v2 ارایه نشده وi3 باید در u ارایه شود زیرا در غیر این صورت، با رنگ امیزی دوبارهuv1 با i3 وuv2 باi3، یک(∆+1)-رنگ امیزی یالی اصلاح شد را به دست می‌اوریم. لذا یالی مانند uv3 دارای رنگ i3 است. با ادامه این شیوه، دنبالهٔ v1,v2,... از راسها و دنباله i1,i2,... از رنگها را می‌سازیم، به طوری که UVi دارای رنگ Ij و +1Ij درVi ارایه نشده‌است. چون درجه u متناهی است، کوچکترین عدد صحیح l ی وجود دارد به طوری که برای مقداری از k با شرط l>kو 1+jI= k این وضعیت در شکل الف رسم شده‌است. اکنون G را به ترتیب زیر دوبار رنگ می کنیم. برای(j≤1,j≥ k−1)، UVj را با رنگ1 +jI دوباره رنگ می‌کنیم، (∆+1)رنگ امیزی یالی جدید(e1,e2,...,∆ +1e) = ׳ϐ به دست می‌اید. به وضوح c′(v) ≥ c(v) و بنابراین ׳ϐ هم یک(∆+1)رنگ امیزی یالی اپتیمال از G است. مولفه ׳H از (ei U eik)G که شامل u است یک دور فرد است. حال علاوه براین UVj را با رنگL−1 ≤J K≤را با رنگ Ik دوباره رنگ می‌کنیم، تا (∆+1)رنگ امیزی یالی (׳e1,..., ∆+1׳e) =׳׳ϐ به دست می‌اید (v)c ≥ (v)׳׳c و مولفه׳׳H از(׳ei U ׳eik)G که شامل u است یک دور فرد است. اما چونVk دارای درجهٔ دو در ׳H است، به وضوح Vk دارای درجهٔ یک در ׳׳H است.[۱]

تعاریف و قضایا[ویرایش]

رنگ‌آمیزی یالیk: رنگ امیزی یالی ϐاز گراف بدون طوقه G تخصیص k رنگ 3,2,1,...k به یالهای G است.

رنگ امیزی سره: رنگ امیزی ϐ سره‌است اگر هیچ دو یال مجاور همرنگ نباشند.

متقابلاً K-رنگ امیزی یالی را می‌توان به صورت یک افراز (E1,E2,...,Ek) از E تصور کرد، که در ان Ei زیرمجموعه‌ای (احتمالاً خالی) از E را نشان می‌دهد که رنگ i را اختیار کرده‌است. پس k-رنگ امیزی یالی سره، k-رنگ امیزی یالی (E1, E2,...,Ek) است که در ان هر زیرمجموعهٔ Ei یک جورسازی است.

قضیه: اگرG دوبخشی باشد آنگاه x′ = ∆.

برهان : فرض کنید G گرافی با x′> ∆ باشد، گیریم(∆E1, E2,..., E)= ϐ یک ∆-رنگ امیزی یالی اپتیمال از G است، و u راسی است که برای ان d(u)>c(u). بنابراین G شامل یک دور فرد بوده و لذا دو بخشی نیست. نتیجه می شود که اگر G دوبخشی باشد انگاهx′ = ∆.‏[۱]

کاربردها[ویرایش]

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

در یک مدرسه، m معلم X1,X2,...,Xm و n کلاس Y1,Y2,...,Yn وجود دارند. اگر بدانیم از معلمXi خواسته شده‌است که در کلاس Yj برای دوره‌های Pij تدریس کند، جدول زمانی کاملی را با مینیمم تعداد دوره‌های ممکن برنامه ریزی کنید. این مساله به مساله جدول زمانی مشهور است، و می‌توان ان را کاملاً با استفاده از نظریهٔ رنگ امیزی یالی حل کرد. ما نیازهای اموزشی را به وسیله گراف دو بخشی G با بخشهای (x,y) معرفی کنیم، که در ان X =(x1,...,xm) و (y1,...,yn)=Y و راسهای Xi و Yj به وسیله یالهای pij به هم متوصل می‌شوند. اکنون در هر دوره، یک معلم حداکثر در یک کلاس می‌تواند تدریس کند. و تدریس در هر کلاس به وسیلهٔ حداکثر یک معلم میتواند انجام شود این، حداقل، پذیره ماست. لذا برنامه ریزی اموزشی برای یک دوره متناظر با جورسازی در گراف است و، بر عکس، هر جورسازی، متناظر با تخصیصی ممکن از معلمان به کلاسها برای یک دورا است. بنابراین، مسالهٔ ما افرازهای یالهای G به کمترین جورساری‌های ممکن، یا هم ارز ان، رنگ امیزی مناسب یالهای G با کمترین رنگ ممکن است. چون G دوبخشی است، می‌دانیم که x′ = ∆ لذا اگر هیچ معلمی برای بیش از p دوره درس ندهد، و اگر در هیچ کلاسی برای بیش ازp یوره تدریس نشود. نیازهای اموزشی را می‌توان در جدول زمانی p-دوره‌ای برنامه ریزی کرد.

در عمل بیشتر مسایل مربوط به جدول زمانی با تخصیص پیشین مسایلی مشکل اند. این تعمیم مساله جدول زمانی را دمپستر(1971)و دوورا(1970)مطالعه کرده‌اند.[۱]

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

  1. ۱٫۰ ۱٫۱ ۱٫۲ باندی، مورلی، نظریه گراف و کاربردهای ان، ترجمهٔ دارا معظمی، مرکز نشر دانشگاهی.
  • Total coloring، مشارکت‌کنندگان ویکی‌پدیای انگلیسی، برداشت شده در ۳۰ مه ۲۰۱۱.