گراف مسطح

گراف‌های نمونه
مسطح	غیرمسطح
گراف مسطح
گراف کامل K4 مسطح است

در نظریه گراف‌ها، گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در رأس‌ها قطع کنند.

یک گراف غیرمسطح گرافی است که نمی‌توان آن را به گونه‌ای رسم کرد که یال‌هایش یکدیگر را در نقاطی غیراز رأس‌ها قطع نکنند.

گراف مسطحی که بدون تقاطع یال‌ها در صفحه ترسیم شده باشد را صفحه گراف یا گراف محاط در صفحه می‌نامند. یک صفحه گراف را می‌توان به صورت یک گراف مسطح تعریف کرد که هر گره‌ای را به نقطه‌ای در فضای دوبعدی و هر یالی را به خمی در صفحه می‌نگارد به گونه‌ای که نقاط انتهایی هر خم نقاطی هستند که از گره‌ها نگاشته شده‌اند، و خم‌ها هیچ اشتراکی با یکدیگر ندارند مگر در نقاط انتهایی.

به سادگی دیده می‌شود که گرافی که قابل ترسیم در صفحه‌است را می‌توان در کره نیز ترسیم کرد.

نظریه‌های کوراتوسکی و واگنر

ریاضی‌دان لهستانی کازیمیر کوراتوسکی (به انگلیسی: Kazimierz Kuratowski) توصیفی از گراف‌های مسطح را تحت عنوان گراف‌های ممنوعه ارائه کرده‌است، که امروزه تحت عنوان نظریه کوراتوسکی شناخته می‌شود.

یک گراف متناهی مسطح است، اگر و تنها اگر شامل زیرگرافی نباشد که آن زیرگراف، زیربخشی از گراف K₅ (گراف کامل با ۵ رأس) یا K_3,3 (گراف کامل دوبخشی با ۶ رأس که ۳ رأس از آن در یک طرف به ۳ رأس دیگر در طرف مقابل متصل‌اند) باشد.

یک زیربخش از یک گراف نتیجه قراردادن رئوسی در میان یال‌هاست (برای مثال یال •——• به یال •—•—• تغییر یابد.) بدین ترتیب که این روند صفر مرتبه یا بیشتر تکرار شود. قواعد معادل این نظریه که تحت عنوان "نظریهٔ P" نیز شناخته می‌شوند می‌گویند: یک گراف متناهی مسطح است اگر و تنها اگر شامل زیرگرافی هم‌ریخت با K₅ یا K_3,3 نباشند.

در شوروی نظریه کوراتوسکی تحت عنوان نظریهٔ Pontryagin-Kuratowski شناخته می‌شود. زیرا گفته می‌شود که اثبات آن نخستین بار در دست نوشته‌های منتشر نشده Pontryagin بوده‌است. بنابر فهم‌های رایج آکادمیک چنین منابعی در اولویت قرار ندارند. از این رو نام روسی این نظریه به‌طور بین‌المللی مورد تأیید نیست.

به جای در نظر گرفتن زیربخش‌ها نظریهٔ واگنر با کهادها سر و کار دارد:

یک گراف مسطح است، اگر و تنها اگر دارای K₅ یا K_3,3 به‌عنوان کهاد نباشد.

واگنر به‌طور عمومی‌تری بیان کرد که هر دسته‌ای از بسته‌های کهاد با مجموعه‌ای محدود از کهادهای ممنوعه مشخص می‌شوند. این مسئله امروزه نظریه Robertson-Seymour نامیده می‌شود، که در صفحات فراوانی این نظریه به اثبات رسیده‌است. در ادبیات این نظریه K₅ و K_3,3 فرزندان ممنوعه‌ای برای دستهٔ گراف‌های مسطح متناهی هستند.

سایر ضوابط مسطح بودن

در عمل استفاده از معیارهای کوراتوسکی برای تشخیص سریع مسطح بودن یک گراف مشکل است. هر چند که الگوریتم‌های سریعی برای حل این مشکل وجود دارد: برای گرافی با n یال می‌توان در زمان O(n) (زمان خطی) تشخیص داد که آیا گراف مورد نظر مسطح است یا نه.

به عنوان یک مثال ساده یک گراف هم‌بند مسطح با v راس وe یال قاعدهٔ سادهٔ زیر برای مسطح بودن گراف به کار گرفته می‌شود:

نظریه 1. اگر v≥3 آن گاه e≤3v-6

نظریه2. اگر $v\geqslant 3$ و هیچ دوری به طول 3 وجود نداشته باشد آن گاه e≤2v-4

از این جهت گراف‌های مسطح گراف‌های پراکنده(کم پشت) هستند، چرا که آن‌ها تنها دارای $O\left(V\right)$ یال هستند که بسیار کوچکتر از O(v²) است. برای مثال گراف K_3,3 دارای 6 رأس، 9 یال است و دوری به طول 3 ندارد. بنابراین طبق نظریهٔ 2 نمی‌تواند مسطح باشد. لازم به توجه است که این نظریه‌ها شرط‌های لازم برای مسطح بودن را بیان می‌کند نه شرط‌های کافی، و به همین دلیل تنها می‌تواند برای اثبات مسطح نبودن یک گراف به کار گرفته شود و نه اثبات مسطح بودن آن. اگر هر دو نظریهٔ یک و دو شکست بخورند ممکن است روش‌های دیگری به کار گرفته شود. برای دو گراف با v راس می‌توان در زمان $O\left(V\right)$ تشخیص داد که آیا آن دو هم ریخت هستند یا نه.

قاعده اویلر

قاعدهٔ اویلر بیان می‌دارد که اگر یک گراف متناهی، همبند و مسطح در صفحه رسم شود به گونه‌ای که هیچ دو یالی یکدیگر را قطع نکنند و v تعداد رأس‌های آن باشد، e تعداد یال‌های آن باشد و f تعداد ناحیه‌های آن باشد (ناحیه‌هایی که به وسیله یال‌ها محدود شده‌اند و ناحیه بیرونی و بی‌نهایت بزرگ را در بر می‌گیرند) آن گاه داریم:

$v-e+f=2$

عبارت فوق بیان می‌کند که مشخصهٔ اویلر برابر 2 است. همان طور که در تصویر در اولین گراف داده شده در فوق می‌بینید، v=6، e=7 و f=3 است. اگر گراف دوم دوباره بدون تقاطع یال‌ها ترسیم شود، آن گاه داریم: v=4، e=6 و f=4. قاعدهٔ اویلر را می‌توان به این طریق اثبات کرد: اگر گراف یک درخت نیست، آن گاه یالی را که یک دور را کامل می‌کند بردارید. این کار e و f را یک واحد کاهش می‌دهد و از این رو v-e-f ثابت است. و این فرایند را تکرار کنید تا به یک درخت دست یابید؛ در درخت‌ها v=e+1 وf=1 است. از این رو v-e+f=2 می‌شود.

در یک گراف متناهی، هم‌بند، ساده و مسطح هر ناحیه‌ای (احتمالاً به جز ناحیهٔ بیرونی) حداقل با ۳ یال محدود شده‌است و هر یال حداکثر با دو ناحیه در تماس است. با به‌کارگیری قاعدهٔ اویلر می‌توان نشان داد که این گراف‌ها پراکنده‌اند(کم پشت‌اند) از آن جهت که اگرv≥3 آن گاه e≥3v-6.

یک گراف ساده، مسطح بیشین (maximal planar) نامیده می‌شود. اگر مسطح باشد اما اضافه کردن هر یالی این ویژگی را برهم زند. در این حالت تمام نواحی (حتی ناحیهٔ خارجی) با سه یال محدود شده‌اند که اصطلاح مثلثی برای این گراف‌ها به‌کار گرفته می‌شود. اگر یک گراف مثلثی v راس با v»2 داشته باشد آن‌گاه 3v-6 یال و 2v-4 ناحیه خواهد داشت.

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

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

یک گراف، مسطح بیرونی نامیده می‌شود، اگر در صفحه محاط شده باشد؛ به گونه‌ای که رأس‌ها بر روی یک دایره قرار گرفته باشند و یال‌ها داخل قرصی از دایره قرار گرفته باشند و یکدیگر را قطع نکنند. به‌طور مشابه وجوهی وجود دارند که هر یک از رأس‌ها را دربرمی گیرند. هر گراف مسطح بیرونی یک گراف مسطح نیز هست، اما عکس این مطلب درست نیست: گراف دومی که در مثال‌های بالا نشان داده شده‌است (K₄) یک گراف مسطح است اما گراف مسطح بیرونی نیست. این گراف کوچکترین گرافی است که مسطح بیرونی نیست. نظریه‌ای مشابه با نظریهٔ کوراتوسکی بیان می‌دارد که یک گراف متناهی، مسطح بیرونی است اگر و تنها اگر شامل زیرگرافی نباشد که بسطی از K₄ (گراف کامل با ۴ راس) یا K_2,3 (گراف دوبخشی کامل با ۵ راس و ۶ یال)

ویژگی‌های گراف‌های مسطح بیرونی

تمام درخت‌ها متناهی یا نامتناهی شمارش‌پذیر، گراف مسطح بیرونی و از این رو گراف مسطح هستند. یک گراف مسطح بیرونی بدون حلقه دارای یک رأس با درجه حداکثر ۲ است. تمامی گراف‌های مسطح بیرونی بدون حلقه را می‌توان با ۳ رنگ، رنگ‌آمیزی کرد. این حقیقت به‌طور برجسته‌ای در اثبات ساده شده نظریه Chvátal's art gallery توسط فیسک نشان داده شد. یک روش برای رنگ کردن گراف با سه رنگ می‌تواند به سادگی با برداشتن رأس درجه ۲ و رنگ کردن باقی گراف به صورت بازگشتی و سپس اضافه کردن رأس برداشته شده و رنگ کردن آن با رنگی متفاوت از دو رأس همسایه‌اش صورت پذیرد.

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

• کد الگوریتم مسطح بودن به زبان C
• سه پازل سودمند و گراف‌های مسطح
• یک پازل نمونه درباره مسطح بودن

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Planar graph». در دانشنامهٔ ویکی‌پدیای انگلیسی.
• http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf
• http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf
• http://cs.anu.edu.au/~bdm/plantri/