قضیه ویزینگ

در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ (به انگلیسی: Vadim G. Vizing) نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می‌کند که یال‌های هر گراف ساده را می‌توان با حداکثر یکی بیشتر از بیشترین درجه $Δ$ رئوس گراف رنگ کرد.

همواره حداقل $Δ$ رنگ لازم است، بنابراین گراف‌های ساده را می‌توان به دو رده افراز کرد: گراف‌های «ردهٔ اول» آنهایی هستند که $Δ$ رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که $Δ + ۱$ رنگ، برای رنگ‌آمیزی آن‌ها لازم است.

مثال‌ها

هنگامی که $Δ = ۱$ است، گراف $G$ خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف‌های با $Δ(G) = ۱$ جزء گرافهای ردهٔ اول هستند.

هنگامی که $Δ = ۲$ است، گراف $G$ اجتماع مجموعه‌های مجزای مسیرها و دورها است. اگر همهٔ دورها زوج باشند، آن‌ها می‌توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. هر چند، اگر حداقل یک دور فرد وجود داشته باشد، هیچ ۲-رنگ آمیزی یالی ممکن نیست. پس، یک گراف با $Δ = ۲$ جزء گراف‌های ردهٔ اول است اگر و تنها اگر دوبخشی باشد.

قضیهٔ ویزینگ در حالت کلی برای گراف‌های چندگانه برقرار نمی‌باشد. برای مثال، گراف چندگانهٔ حاصل از مضاعف کردن هر یال یک مثلث، بیشینه درجهٔ چهار دارد اما نمی‌توان آن را با کمتر از شش رنگ، رنگ‌آمیزی کرد.

رده‌بندی گراف‌ها

چندین نویسنده شرایطی را برای رده‌بندی برخی گراف‌ها به ردهٔ اول یا ردهٔ دوم ارائه کرده‌اند اما رده‌بندی کاملی ارائه نشده‌است. برای مثال اگر مجموعهٔ رئوس با بیشینه درجهٔ $Δ$ در گراف $G$ یک مجموعه مستقل باشد، یا به‌طور کلی‌تر زیرگراف القایی این رئوس یک جنگل باشد، آنگاه $G$ باید جزء گراف‌های ردهٔ اول باشد.

اردوش و ویلسون (۱۹۷۷) نشان دادند که تقریباً همهی گراف‌ها جزء ردهٔ اول هستند. پس، در مدل اردوش-رنیِ (به انگلیسی: Erdős–Rényi model) گراف‌های تصادفی، که تقریباً تمام گراف‌های $n$ -راسی برابر هستند، $p (n)$ را احتمال کشیده شدن یک گراف $n$ -راسی از توزیع گراف‌های ردهٔ اول تعریف می‌کنیم، در نتیجه اگر $n$ به بینهایت میل کند $p (n)$ به یک نزدیک می‌شود. برای حدود بهتری که $p (n)$ به یک همگرا باشد، به Frieze et al. (1988) رجوع شود.

گراف‌های مسطح

ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف‌های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف‌های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گراف‌های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می‌توانند ساخته شوند.

در حدس گراف‌های مسطح ویزینگ، ویزینگ (۱۹۶۵) بیان می‌کند که گراف‌های سادهٔ مسطح که بیشترین درجهٔ رئوس آن‌ها شش یا هفت است، جزء گراف‌های ردهٔ اول هستند، و این موارد ممکن باقی‌مانده را تمام می‌کند. سندرز و ژاو (۱۹۶۵) با نشان دادن ردهٔ اول بودن تمام گراف‌های مسطح با بیشترین درجهٔ رئوس هفت، تقریباً حدس گراف‌های مسطح ویزینگ را اثبات کردند. بنابراین، تنها حالت حدس که حل نشده باقی‌مانده این است که بیشترین درجه، شش باشد. این حدس شامل دلایلی برای حدس رنگ‌آمیزی کامل گراف است.

گراف‌های مسطح ردهٔ دوم که با زیربخش‌های اجسام افلاطونی ساخته می‌شوند منظم نیستند: آن‌ها رئوس درجهٔ دو دارند همانطور که رئوس با درجهٔ بالاتر دارند. قضیه چهاررنگ، روی رنگ‌آمیزی راسی گراف‌های مسطح، معادل این گزاره است که هر گراف ۳-منظمِ مسطحِ بدون یال برشی جزء گراف‌های ردهٔ اول هستند (تایت ۱۸۸۰). این گزاره بعد از اثبات قضیه چهار رنگ توسط اپل و هاکن (۱۹۷۶) درست شناخته شد.

گراف‌های روی رویه‌های غیرمسطح

در سال ۱۹۶۹، برانکو گرانبام (به انگلیسی: Branko Grünbaum) حدس زد که تمام گراف‌های ۳-منظم با برازش چندوجهی روی هر خمینهٔ جهت‌دار دو بعدی مانند چنبره، باید جزو گراف‌های ردهٔ اول باشد. در این زمینه، برازش چندوجهی یک برازش گراف است که در آن هر ناحیه از برازش از نظر توپولوژیکی یک دیسک است و به طوری که گرافِ دوگانِ برازش ساده است، بدون حلقه و یال چندگانه. در صورت درست بودن، این حدس یک تعمیم قضیهٔ چهار رنگ است که توسط تایت، نشان داده شد معادل این گزاره است که گراف‌های ۳-منظم با برازش چندوجهی روی یک کره، جزء رده اول هستند. اگرچه کُچُل (۲۰۰۹) نشان داد که حدس غلط است اگر اسنارکی (به انگلیسی: snark) که دارای برازش چندوجهی بر روی رویهٔ جهت‌دار بالادسته وجود داشته باشد. بر این اساس، او همچنان نشان داده است که دانستن اینکه برازش چندوجهی جزو گراف‌ها ردهٔ اول است، ان‌پی کامل است.

الگوریتم‌ها

میسرا و گرایز (۱۹۹۲) یک الگوریتم با زمان چندجمله‌ای برای رنگ‌آمیزی هر گراف با $Δ + ۱$ رنگ ارائه کردند، که $Δ$ بیشینه درجهٔ گراف است. پس، الگوریتم برای گراف‌های ردهٔ دوم از تعداد رنگ‌های بهینه استفاده می‌کند، و حداکثر یکی بیشتر از تعداد رنگ‌های مورد نیاز برای همهٔ گراف‌ها. الگوریتم آن‌ها از روشی یکسان با اثبات اصلی ویزینگ برای قضیه‌اش پیروی می‌کند: این الگوریتم از یک گراف رنگ نشده شروع می‌کند، و سپس به‌طور مکرر راهی را برای رنگ‌آمیزی دوباره گراف پیدا می‌کند تا تعداد یال‌های رنگ شده را یک عدد افزایش دهد.

به‌طور خاص‌تر، فرض کنید که $uv$ یک یال رنگ نشده در یک گراف نیمه رنگ شده باشد. الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل (به انگلیسی: Pseudoforest) جهت‌دار $P$ (یک گراف که هر رأس آن حداکثر یک یال خارج‌شونده دارد.) روی همسایه‌های $u$ تفسیر شود: برای هر همسایهٔ $p$ از $u$ ، الگوریتم یک رنگ $c$ را می‌یابد که توسط هیچ یک از یال‌های مجاور $p$ استفاده نشده‌است، رأس $q$ را می‌یابد (در صورت وجود) که یال $uq$ رنگ $c$ را دارد و $pq$ را به عنوان یک یال به $P$ اضافه می‌کند. دو حالت وجود دارد:

اگر شبه جنگل $P$ که به این روش ساخته می‌شود شامل یک مسیر از $v$ به $w$ باشد که هیچ یال خروجی در $P$ نداشته باشد، آنگاه رنگ $c$ وجود دارد که در هر دو $u$ و $w$ قابل استفاده است. رنگ‌آمیزی دوباره یال $uw$ با رنگ $c$ اجازه می‌دهد که رنگ‌های یال باقی‌مانده در طول مسیر یک گام انتقال یابند: برای هر رأس $p$ در مسیر، یال $up$ رنگی را که قبلاً توسط تالی $p$ در مسیر استفاده شده بود را می‌گیرد. این منجر به یک رنگ‌آمیزی جدید می‌شود که شامل یال $uv$ نیز هست.
از سوی دیگر، اگر مسیری که از $v$ شروع می‌شود در شبه جنگل $P$ منجر به یک دور شود، فرض کنید $w$ همسایهٔ $u$ در شبه جنگل $P$ باشد در جایی که مسیر به دور می‌پیوندد، فرض کنید $c$ رنگ یال $uw$ باشد، و فرض کنید $d$ رنگی باشد که توسط هیچکدام از یال‌های راس $u$ استفاده نشده‌است. آنگاه جابجا کردن رنگ‌های $c$ و $d$ روی یک زنجیر کمپ (به انگلیسی: Kempe chain) یا دور را می‌شکند یا یالی که در آن مسیر به دور می‌پیوندد، منجر به حالت قبلی می‌شود.

با برخی از ساختمان داده‌های ساده برای پیگیری رنگ‌هایی استفاده شده و قابل استفاده در هر رأس، می‌توان ساختن $P$ و گام‌های رنگ‌آمیزی دوباره الگوریتم را با زمان $O(n)$ پیاده‌سازی کرد، که $n$ تعداد رئوس گراف ورودی است. چون در هر تکرار این گام‌ها تعداد یال‌های رنگ شده یکی افزایش می‌یابد، باید این گام‌ها را $m$ بار تکرار کرد، پس زمان مجموع برابر است با $O(mn)$ .

در یک گزارش فنی منتشر نشده، گابو و همکاران (۱۹۸۵) ادعای ارائهٔ یک محدودیت زمانی $O(m{\sqrt {n}}\log n)$ سریع‌تر را برای مسئلهٔ رنگ‌آمیزی یکسان با $Δ + ۱$ رنگ را کردند.

تاریخچه

در هر دو گوتین و تافت (۲۰۰۰) و سافیر (۲۰۰۸)، ویزینگ اشاره کرد که کارش انگیخته شده توسط یکی از قضایای شانون (۱۹۴۹) است که نشان می‌دهد گراف‌های چندگانه می‌توانند با حداکثر $(۳/۲)Δ$ رنگ، رنگ‌آمیزی شوند. هر چند حالا قضیه ویزینگ جزء مواد استاندارد بسیاری از کتاب‌های نظریه گراف است، ویزینگ در ابتدا برای انتشار نتایجش مشکل داشت، و مقاله‌اش در یک مجلهٔ گمنام به نام Diskret. Analiz. چاپ شد.

جستارهای وابسته

قضیه بروکس (به انگلیسی: Brooks' theorem)، رنگ‌آمیزی رأسی را به بیشترین درجه مرتبط می‌کند.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Vizing's theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۰ آذر ۱۳۹۲.
Frieze, Alan M.; Jackson, B.; McDiarmid, C. J. H.; Reed, B. (1988), "Edge-colouring random graphs", Journal of Combinatorial Theory, Series B, 45 (2): 135–149, doi:10.1016/0095-8956(88)90065-2, MR 0961145.

پیوند به بیرون

اثبات قضیه ویزینگ در پلنت‌مث.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.