گراف ۱-مسطح

منبع}}

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه، محتوای آن را بهبود بخشید.

در نظریه توپولوژیک گراف، یک گراف ۱-مسطح گرافی است که می‌توان آن را طوری در صفحهٔ اقلیدسی ترسیم کرد که هر یال حداکثر یک تقاطع با یال‌های دیگر داشته باشد. به عبارت دیگر، هیچ یالی با دو یال دیگر متقاطع نباشد. به چنین ترسیمی هم یک ترسیم ۱-مسطح از گراف می‌گویند (گرافی که حداقل یک ترسیم ۱-مسطح داشته باشد، گراف ۱-مسطح نامیده می‌شود).

گرهارد رینگل (۱۹۹۵) اولین کسی بود که به مطالعهٔ گراف‌های ۱-مسطح پرداخت. او نشان داد که این گراف‌ها را می‌توان با حداکثر ۷ رنگ رنگ‌آمیزی کرد. بعداً مشخص شد که تعداد دقیق رنگ‌های مورد نیاز برای رنگ‌آمیزی این گراف‌ها در بدترین حالت، عدد ۶ است. گراف کامل K_۶ نمونه‌ای است که نشان می‌دهد تعداد ۶ رنگ در بعضی حالات مورد نیاز است. با این حال، اثبات اینکه ۶ رنگ همیشه کافی خواهد بود، پیچیده‌تر از اینهاست.

انگیزهٔ رینگل این بود که بتواند نوعی از رنگ‌آمیزی کامل را برای گراف‌های مسطح حل کند، که در آن تمام رئوس و وجوه یک گراف مسطح را همزمان طوری رنگ می‌کنیم که هیج دو رأس مجاوری همرنگ نبوده، هیج دو وجه مجاوری همرنگ نبوده، و هیچ رأس و وجهی که مجاور هستند همرنگ نباشند. این کار به وضوح توسط ۸ رنگ قابل انجام است، کافی است قضیه چهاررنگ را بر روی گراف داده شده و گراف همزاد (dual) آن با دو مجموعهٔ مجزا از ۴ رنگ به‌طور مجزا اعمال کنیم. با این حال، برای دستیابی به تعداد کمتری از رنگ‌ها می‌توان یک گراف کمکی تشکیل داد که یک رأس به ازای هر رأس یا وجه گراف مسطح داده شده دارد، و دو رأس این گراف کمکی مجاور هستند اگر و فقط اگر دو رأس/وجه متناظر آن‌ها در گراف اصلی مجاور باشند. یک رنگ‌آمیزی رأسی این گراف کمکی معادل یک رنگ‌آمیزی رأسی-وجهی گراف مسطح اصلی است. این گراف کمکی یک گراف ۱-مسطح است، و از اینجا بود که مسئله رنگ‌آمیزی رأسی-وجهی رینگل منجر به رنگ‌آمیزی رأسی گراف ۱-مسطح شد، و اکنون می‌دانیم که هر دوی این مسائل با ۶ رنگ قابل حل هستند. گرچه گراف کامل K_۶ را نمی‌توان به عنوان یک گراف کمکی تشکیل داد، اما برای نمونه اگر گراف مسطح منشور مثلثی را بخواهیم رنگ‌آمیزی وجهی-رأسی کنیم، یازده رأس و وجه آن به ۶ رنگ نیاز دارند، چون به هیچ سه تایی از آن‌ها نمی‌توان یک رنگ اختصاص داد.

هر گراف ۱-مسطح با n رأس حداکثر ۴n − ۸ یال دارد. قوی‌تر اینکه، هر ترسیم ۱-مسطح حداکثر n − ۲ تقاطع دارد؛ حذف یک یال از هر زوج یال‌های متقاطع، یک گراف مسطح را باقی می‌گذارد، که می‌تواند حداکثر ۳n − ۶ یال داشته باشد، که بلافاصله نتیجه می‌دهد گراف ۱-مسطح اصلی حداکثر می‌توانست ۴n − ۸ یال داشته باشد. با این حال، بر خلاف گراف‌های مسطح (که تمام گراف‌های مسطح بیشینه روی یک مجموعه از رئوس مشخص، تعداد یکسانی از یال‌ها دارند)، گراف‌های ۱-مسطح بیشینه‌ای (که هیچ یال جدیدی با حفظ ۱-مسطح بودن نمی‌توان به آن‌ها اضافه کرد) وجود دارند که تعداد یال بسیار کمتری از ۴n − ۸ دارند. محدودیت ۴n − ۸ برای حداکثر تعداد یال‌ها در یک گراف ۱-مسطح می‌تواند نشان دهد که گراف کامل K_۷ یک گراف ۱-مسطح نیست، چون دارای ۷ رأس و ۲۱ یال بوده و ۴n − ۸ = ۲۰ < ۲۱.

یک گراف ۱-مسطح را یک گراف ۱-مسطح بهینه می‌گویند اگر دقیقاً ۴n − ۸ یال داشته باشد، که حداکثر تعداد ممکن است. در یک زیرگراف از یک گراف ۱-مسطح بهینه، یال‌های بدون تقاطع لزوماً تشکیل یک گراف مربعی می‌دهند (یک گراف چندوجهی که هر وجه آن یک چهارضلعی است). از این طریق هر گراف مربعی با اضافه کردن دو قُطر به هر یک از وجوه چهارضلعی‌اش یک گراف ۱-مسطح بهینه را تولید می‌کند. در نتیجه هر گراف ۱-مسطح بهینه یک گراف اویلری است (تمام رئوسش درجهٔ زوج دارند)، که حداقل درجهٔ رئوس در آن ۶ است. همچنین هر گراف ۱-مسطح بهینه حداقل ۸ رأس با درجهٔ دقیقاً ۶ دارد. به علاوه، هر گراف ۱-مسطح بهینه یک گراف ۴-رأس-همبند بوده، و هر بُرش ۴-رأسی در چنین گرافی یک حلقهٔ جداکننده در گراف مربعی زیرین است.

گراف‌هایی که ترسیم ۱-مسطح مستقیم دارند (ترسیمی که هر یال یک خط مستقیم است با حداکثر یک تقاطع) محدودهٔ تنگ‌تری برای تعداد یال‌ها دارند؛ این گراف‌ها حداکثر ۴n − ۹ یال می‌توانند داشته باشند.

زیرمجموعه‌ای از گراف‌های ۱-مسطح که گراف کامل، گراف دوبخشی کامل یا به‌طور کلی گراف چندبخشی کامل هستند در دسته‌های شناخته‌شده‌ای قرار دارند. هر گراف دوبخشی کامل در شکل K_۲،n یک گراف ۱-مسطح است، همینطور هر گراف سه‌بخشی کامل به شکل K_۱،۱،n. غیر از این مجموعه‌های نامتناهی از نمونه‌ها، تنها گراف‌های چندبخشی کامل ۱-مسطح این گراف‌ها:
K_۶ , K_{۱،۱،۱،۶} , K_{۱،۱،۲،۳} , K_{۲،۲،۲،۲} , K_{۱،۱،۱،۲،۲}
و زیرگراف‌های آن‌ها هستند.
گراف‌های کمینهٔ غیر-۱-مسطح چندبخشی کامل این‌ها هستند:
K_۳،۷ , K_۴،۵ , K_۱،۳،۴ , K_۲،۳،۳ , K_{۱،۱،۱،۱،۳}
به عنوان مثال، گراف دوبخشی کامل K_۳،۶ گراف ۱-مسطح است چون زیرگرافی از K_{۱،۱،۱،۶} است، اما K_۳،۷ گراف ۱-مسطح نیست.

ویکی‌پدیای انگلیسی