موضوع مقاله: گراف ۱-مسطح | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف ۱-مسطح | مقدمه: در نظریه توپولوژیک گراف، یک گراف ۱-مسطح گرافی است که می‌توان آن را طوری در صفحهٔ اقلیدسی ترسیم کرد که هر یال حداکثر یک تقاطع با یال‌های دیگر داشته باشد. | ## بخش 1: گراف ۱-مسطح | به چنین ترسیمی هم یک ترسیم ۱-مسطح از گراف می‌گویند (گرافی که حداقل یک ترسیم ۱-مسطح داشته باشد، گراف ۱-مسطح نامیده می‌شود). رنگ‌آمیزی گرهارد رینگل (۱۹۹۵) اولین کسی بود که به مطالعهٔ گراف‌های ۱-مسطح پرداخت. بعداً مشخص شد که تعداد دقیق رنگ‌های مورد نیاز برای رنگ‌آمیزی این گراف‌ها در بدترین حالت، عدد ۶ است. گراف کامل K۶ نمونه‌ای است که نشان می‌دهد تعداد ۶ رنگ در بعضی حالات مورد نیاز است. این کار به وضوح توسط ۸ رنگ قابل انجام است، کافی است قضیه چهاررنگ را بر روی گراف داده شده و گراف همزاد (dual) آن با دو مجموعهٔ مجزا از ۴ رنگ به‌طور مجزا اعمال کنیم. با این حال، برای دستیابی به تعداد کمتری از رنگ‌ها می‌توان یک گراف کمکی تشکیل داد که یک رأس به ازای هر رأس یا وجه گراف مسطح داده شده دارد، و دو رأس این گراف کمکی مجاور هستند اگر و فقط اگر دو رأس/وجه متناظر آن‌ها در گراف اصلی مجاور باشند. یک رنگ‌آمیزی رأسی این گراف کمکی معادل یک رنگ‌آمیزی رأسی-وجهی گراف مسطح اصلی است. | ## بخش 2: گراف ۱-مسطح | این گراف کمکی یک گراف ۱-مسطح است، و از اینجا بود که مسئله رنگ‌آمیزی رأسی-وجهی رینگل منجر به رنگ‌آمیزی رأسی گراف ۱-مسطح شد، و اکنون می‌دانیم که هر دوی این مسائل با ۶ رنگ قابل حل هستند. گرچه گراف کامل K۶ را نمی‌توان به عنوان یک گراف کمکی تشکیل داد، اما برای نمونه اگر گراف مسطح منشور مثلثی را بخواهیم رنگ‌آمیزی وجهی-رأسی کنیم، یازده رأس و وجه آن به ۶ رنگ نیاز دارند، چون به هیچ سه تایی از آن‌ها نمی‌توان یک رنگ اختصاص داد. قوی‌تر اینکه، هر ترسیم ۱-مسطح حداکثر n − ۲ تقاطع دارد؛ حذف یک یال از هر زوج یال‌های متقاطع، یک گراف مسطح را باقی می‌گذارد، که می‌تواند حداکثر ۳n − ۶ یال داشته باشد، که بلافاصله نتیجه می‌دهد گراف ۱-مسطح اصلی حداکثر می‌توانست ۴n − ۸ یال داشته باشد. با این حال، بر خلاف گراف‌های مسطح (که تمام گراف‌های مسطح بیشینه روی یک مجموعه از رئوس مشخص، تعداد یکسانی از یال‌ها دارند)، گراف‌های ۱-مسطح بیشینه‌ای (که هیچ یال جدیدی با حفظ ۱-مسطح بودن نمی‌توان به آن‌ها اضافه کرد) وجود دارند که تعداد یال بسیار کمتری از ۴n − ۸ دارند. محدودیت ۴n − ۸ برای حداکثر تعداد یال‌ها در یک گراف ۱-مسطح می‌تواند نشان دهد که گراف کامل K۷ یک گراف ۱-مسطح نیست، چون دارای ۷ رأس و ۲۱ یال بوده و ۴n − ۸ = ۲۰ < ۲۱. یک گراف ۱-مسطح را یک گراف ۱-مسطح بهینه می‌گویند اگر دقیقاً ۴n − ۸ یال داشته باشد، که حداکثر تعداد ممکن است. در یک زیرگراف از یک گراف ۱-مسطح بهینه، یال‌های بدون تقاطع لزوماً تشکیل یک گراف مربعی می‌دهند (یک گراف چندوجهی که هر وجه آن یک چهارضلعی است). | ## بخش 3: گراف ۱-مسطح | از این طریق هر گراف مربعی با اضافه کردن دو قُطر به هر یک از وجوه چهارضلعی‌اش یک گراف ۱-مسطح بهینه را تولید می‌کند. در نتیجه هر گراف ۱-مسطح بهینه یک گراف اویلری است (تمام رئوسش درجهٔ زوج دارند)، که حداقل درجهٔ رئوس در آن ۶ است. به علاوه، هر گراف ۱-مسطح بهینه یک گراف ۴-رأس-همبند بوده، و هر بُرش ۴-رأسی در چنین گرافی یک حلقهٔ جداکننده در گراف مربعی زیرین است. گراف‌هایی که ترسیم ۱-مسطح مستقیم دارند (ترسیمی که هر یال یک خط مستقیم است با حداکثر یک تقاطع) محدودهٔ تنگ‌تری برای تعداد یال‌ها دارند؛ این گراف‌ها حداکثر ۴n − ۹ یال می‌توانند داشته باشند. هر گراف دوبخشی کامل در شکل K۲،n یک گراف ۱-مسطح است، همینطور هر گراف سه‌بخشی کامل به شکل K۱،۱،n. غیر از این مجموعه‌های نامتناهی از نمونه‌ها، تنها گراف‌های چندبخشی کامل ۱-مسطح این گراف‌ها: K۶ , K۱،۱،۱،۶ , K۱،۱،۲،۳ , K۲،۲،۲،۲ , K۱،۱،۱،۲،۲ و زیرگراف‌های آن‌ها هستند. | ## جمع‌بندی | گراف‌های کمینهٔ غیر-۱-مسطح چندبخشی کامل این‌ها هستند: K۳،۷ , K۴،۵ , K۱،۳،۴ , K۲،۳،۳ , K۱،۱،۱،۱،۳ به عنوان مثال، گراف دوبخشی کامل K۳،۶ گراف ۱-مسطح است چون زیرگرافی از K۱،۱،۱،۶ است، اما K۳،۷ گراف ۱-مسطح نیست.