قضیه ویزینگ

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

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

مثال‌ها

هنگامی که الگو:Math است، گراف الگو:Math خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف‌های با الگو:Math جزء گرافهای ردهٔ اول هستند.

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

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

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

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

اردوش و ویلسون (۱۹۷۷) نشان دادند که تقریباً همهی گراف‌ها جزء ردهٔ اول هستند. پس، در مدل اردوش-رنیِ الگو:به انگلیسی گراف‌های تصادفی، که تقریباً تمام گراف‌های الگو:Math-راسی برابر هستند، الگو:Math را احتمال کشیده شدن یک گراف الگو:Math-راسی از توزیع گراف‌های ردهٔ اول تعریف می‌کنیم، در نتیجه اگر الگو:Math به بینهایت میل کند الگو:Math به یک نزدیک می‌شود. برای حدود بهتری که الگو:Math به یک همگرا باشد، به الگو:Harvtxt رجوع شود.

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

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

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

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

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

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

الگوریتم‌ها

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

به‌طور خاص‌تر، فرض کنید که الگو:Math یک یال رنگ نشده در یک گراف نیمه رنگ شده باشد. الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل الگو:به انگلیسی جهت‌دار الگو:Math (یک گراف که هر رأس آن حداکثر یک یال خارج‌شونده دارد.) روی همسایه‌های الگو:Math تفسیر شود: برای هر همسایهٔ الگو:Math از الگو:Math، الگوریتم یک رنگ الگو:Math را می‌یابد که توسط هیچ یک از یال‌های مجاور الگو:Math استفاده نشده‌است، رأس الگو:Math را می‌یابد (در صورت وجود) که یال الگو:Math رنگ الگو:Math را دارد و الگو:Math را به عنوان یک یال به الگو:Math اضافه می‌کند. دو حالت وجود دارد:

• اگر شبه جنگل الگو:Math که به این روش ساخته می‌شود شامل یک مسیر از الگو:Math به الگو:Math باشد که هیچ یال خروجی در الگو:Math نداشته باشد، آنگاه رنگ الگو:Math وجود دارد که در هر دو الگو:Math و الگو:Math قابل استفاده است. رنگ‌آمیزی دوباره یال الگو:Math با رنگ الگو:Math اجازه می‌دهد که رنگ‌های یال باقی‌مانده در طول مسیر یک گام انتقال یابند: برای هر رأس الگو:Math در مسیر، یال الگو:Math رنگی را که قبلاً توسط تالی الگو:Math در مسیر استفاده شده بود را می‌گیرد. این منجر به یک رنگ‌آمیزی جدید می‌شود که شامل یال الگو:Math نیز هست.
• از سوی دیگر، اگر مسیری که از الگو:Math شروع می‌شود در شبه جنگل الگو:Math منجر به یک دور شود، فرض کنید الگو:Math همسایهٔ الگو:Math در شبه جنگل الگو:Math باشد در جایی که مسیر به دور می‌پیوندد، فرض کنید الگو:Math رنگ یال الگو:Math باشد، و فرض کنید الگو:Math رنگی باشد که توسط هیچکدام از یال‌های راس الگو:Math استفاده نشده‌است. آنگاه جابجا کردن رنگ‌های الگو:Math و الگو:Math روی یک زنجیر کمپ الگو:به انگلیسی یا دور را می‌شکند یا یالی که در آن مسیر به دور می‌پیوندد، منجر به حالت قبلی می‌شود.

با برخی از ساختمان داده‌های ساده برای پیگیری رنگ‌هایی استفاده شده و قابل استفاده در هر رأس، می‌توان ساختن الگو:Math و گام‌های رنگ‌آمیزی دوباره الگوریتم را با زمان الگو:Math پیاده‌سازی کرد، که الگو:Math تعداد رئوس گراف ورودی است. چون در هر تکرار این گام‌ها تعداد یال‌های رنگ شده یکی افزایش می‌یابد، باید این گام‌ها را الگو:Math بار تکرار کرد، پس زمان مجموع برابر است با الگو:Math.

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

تاریخچه

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

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

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

منابع

• الگو:یادکرد ویکی
• الگو:Citation.

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

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