موضوع مقاله: قضیه ویزینگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه ویزینگ | مقدمه: در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می‌کند که یال‌های هر گراف ساده را می‌توان با حداکثر یکی بیشتر از بیشترین درجه رئوس گراف رنگ کرد. | ## بخش 1: قضیه ویزینگ | همواره حداقل رنگ لازم است، بنابراین گراف‌های ساده را می‌توان به دو رده افراز کرد: گراف‌های «ردهٔ اول» آنهایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها لازم است. مثال‌ها هنگامی که است، گراف خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. اگر همهٔ دورها زوج باشند، آن‌ها می‌توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. برای مثال، گراف چندگانهٔ حاصل از مضاعف کردن هر یال یک مثلث، بیشینه درجهٔ چهار دارد اما نمی‌توان آن را با کمتر از شش رنگ، رنگ‌آمیزی کرد. رده‌بندی گراف‌ها چندین نویسنده شرایطی را برای رده‌بندی برخی گراف‌ها به ردهٔ اول یا ردهٔ دوم ارائه کرده‌اند اما رده‌بندی کاملی ارائه نشده‌است. برای مثال اگر مجموعهٔ رئوس با بیشینه درجهٔ در گراف یک مجموعه مستقل باشد، یا به‌طور کلی‌تر زیرگراف القایی این رئوس یک جنگل باشد، آنگاه باید جزء گراف‌های ردهٔ اول باشد. پس، در مدل اردوش-رنیِ گراف‌های تصادفی، که تقریباً تمام گراف‌های -راسی برابر هستند، را احتمال کشیده شدن یک گراف -راسی از توزیع گراف‌های ردهٔ اول تعریف می‌کنیم، در نتیجه اگر به بینهایت میل کند به یک نزدیک می‌شود. گراف‌های مسطح ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف‌های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف‌های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گراف‌های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می‌توانند ساخته شوند. در حدس گراف‌های مسطح ویزینگ، ویزینگ (۱۹۶۵) بیان می‌کند که گراف‌های سادهٔ مسطح که بیشترین درجهٔ رئوس آن‌ها شش یا هفت است، جزء گراف‌های ردهٔ اول هستند، و این موارد ممکن باقی‌مانده را تمام می‌کند. | ## بخش 2: قضیه ویزینگ | سندرز و ژاو (۱۹۶۵) با نشان دادن ردهٔ اول بودن تمام گراف‌های مسطح با بیشترین درجهٔ رئوس هفت، تقریباً حدس گراف‌های مسطح ویزینگ را اثبات کردند. گراف‌های مسطح ردهٔ دوم که با زیربخش‌های اجسام افلاطونی ساخته می‌شوند منظم نیستند: آن‌ها رئوس درجهٔ دو دارند همانطور که رئوس با درجهٔ بالاتر دارند. قضیه چهاررنگ، روی رنگ‌آمیزی راسی گراف‌های مسطح، معادل این گزاره است که هر گراف ۳-منظمِ مسطحِ بدون یال برشی جزء گراف‌های ردهٔ اول هستند (تایت ۱۸۸۰). گراف‌های روی رویه‌های غیرمسطح در سال ۱۹۶۹، برانکو گرانبام حدس زد که تمام گراف‌های ۳-منظم با برازش چندوجهی روی هر خمینهٔ جهت‌دار دو بعدی مانند چنبره، باید جزو گراف‌های ردهٔ اول باشد. در این زمینه، برازش چندوجهی یک برازش گراف است که در آن هر ناحیه از برازش از نظر توپولوژیکی یک دیسک است و به طوری که گرافِ دوگانِ برازش ساده است، بدون حلقه و یال چندگانه. در صورت درست بودن، این حدس یک تعمیم قضیهٔ چهار رنگ است که توسط تایت، نشان داده شد معادل این گزاره است که گراف‌های ۳-منظم با برازش چندوجهی روی یک کره، جزء رده اول هستند. اگرچه کُچُل (۲۰۰۹) نشان داد که حدس غلط است اگر اسنارکی که دارای برازش چندوجهی بر روی رویهٔ جهت‌دار بالادسته وجود داشته باشد. بر این اساس، او همچنان نشان داده است که دانستن اینکه برازش چندوجهی جزو گراف‌ها ردهٔ اول است، ان‌پی کامل است. الگوریتم‌ها میسرا و گرایز (۱۹۹۲) یک الگوریتم با زمان چندجمله‌ای برای رنگ‌آمیزی هر گراف با رنگ ارائه کردند، که بیشینه درجهٔ گراف است. پس، الگوریتم برای گراف‌های ردهٔ دوم از تعداد رنگ‌های بهینه استفاده می‌کند، و حداکثر یکی بیشتر از تعداد رنگ‌های مورد نیاز برای همهٔ گراف‌ها. الگوریتم آن‌ها از روشی یکسان با اثبات اصلی ویزینگ برای قضیه‌اش پیروی می‌کند: این الگوریتم از یک گراف رنگ نشده شروع می‌کند، و سپس به‌طور مکرر راهی را برای رنگ‌آمیزی دوباره گراف پیدا می‌کند تا تعداد یال‌های رنگ شده را یک عدد افزایش دهد. | ## بخش 3: قضیه ویزینگ | الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل جهت‌دار (یک گراف که هر رأس آن حداکثر یک یال خارج‌شونده دارد.) روی همسایه‌های تفسیر شود: برای هر همسایهٔ از ، الگوریتم یک رنگ را می‌یابد که توسط هیچ یک از یال‌های مجاور استفاده نشده‌است، رأس را می‌یابد (در صورت وجود) که یال رنگ را دارد و را به عنوان یک یال به اضافه می‌کند. دو حالت وجود دارد: اگر شبه جنگل که به این روش ساخته می‌شود شامل یک مسیر از به باشد که هیچ یال خروجی در نداشته باشد، آنگاه رنگ وجود دارد که در هر دو و قابل استفاده است. رنگ‌آمیزی دوباره یال با رنگ اجازه می‌دهد که رنگ‌های یال باقی‌مانده در طول مسیر یک گام انتقال یابند: برای هر رأس در مسیر، یال رنگی را که قبلاً توسط تالی در مسیر استفاده شده بود را می‌گیرد. از سوی دیگر، اگر مسیری که از شروع می‌شود در شبه جنگل منجر به یک دور شود، فرض کنید همسایهٔ در شبه جنگل باشد در جایی که مسیر به دور می‌پیوندد، فرض کنید رنگ یال باشد، و فرض کنید رنگی باشد که توسط هیچکدام از یال‌های راس استفاده نشده‌است. آنگاه جابجا کردن رنگ‌های و روی یک زنجیر کمپ یا دور را می‌شکند یا یالی که در آن مسیر به دور می‌پیوندد، منجر به حالت قبلی می‌شود. با برخی از ساختمان داده‌های ساده برای پیگیری رنگ‌هایی استفاده شده و قابل استفاده در هر رأس، می‌توان ساختن و گام‌های رنگ‌آمیزی دوباره الگوریتم را با زمان پیاده‌سازی کرد، که تعداد رئوس گراف ورودی است. چون در هر تکرار این گام‌ها تعداد یال‌های رنگ شده یکی افزایش می‌یابد، باید این گام‌ها را بار تکرار کرد، پس زمان مجموع برابر است با . در یک گزارش فنی منتشر نشده، گابو و همکاران (۱۹۸۵) ادعای ارائهٔ یک محدودیت زمانی سریع‌تر را برای مسئلهٔ رنگ‌آمیزی یکسان با رنگ را کردند. تاریخچه در هر دو گوتین و تافت (۲۰۰۰) و سافیر (۲۰۰۸)، ویزینگ اشاره کرد که کارش انگیخته شده توسط یکی از قضایای شانون (۱۹۴۹) است که نشان می‌دهد گراف‌های چندگانه می‌توانند با حداکثر رنگ، رنگ‌آمیزی شوند. | ## جمع‌بندی | هر چند حالا قضیه ویزینگ جزء مواد استاندارد بسیاری از کتاب‌های نظریه گراف است، ویزینگ در ابتدا برای انتشار نتایجش مشکل داشت، و مقاله‌اش در یک مجلهٔ گمنام به نام Diskret.