گراف ۱-مسطح

منبع}}

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

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

بندانگشتی|چپ|رنگ‌آمیزی رئوس و وجوه گراف منشور مثلثی، نیازمند ۶ رنگ است

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

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

K۶ , K۱،۱،۱،۶ , K۱،۱،۲،۳ , K۲،۲،۲،۲ , K۱،۱،۱،۲،۲

و زیرگراف‌های آن‌ها هستند.

گراف‌های کمینهٔ غیر-۱-مسطح چندبخشی کامل این‌ها هستند:

K۳،۷ , K۴،۵ , K۱،۳،۴ , K۲،۳،۳ , K۱،۱،۱،۱،۳

به عنوان مثال، گراف دوبخشی کامل K۳،۶ گراف ۱-مسطح است چون زیرگرافی از K۱،۱،۱،۶ است، اما K۳،۷ گراف ۱-مسطح نیست.

## منابع

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

رده:توپولوژی
رده:چندوجهی‌ها
رده:چهارضلعی‌ها
رده:رنگ‌آمیزی گراف
رده:گراف‌های مسطح
رده:نظریه گراف
رده:مسئله‌های ان‌پی کامل