دانلود مقالات ISI درباره گراف مسطح + ترجمه فارسی

گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه‌ای که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند. به این گراف هامنی نیز گفته می‌شود. در بین گراف های کامل فقط گراف هایی با تعداد راس مساوی یا کمتر از 5 (p≤5) را، می توان به صورت مسطح رسم کرد. گراف مسطحی که بدون تقاطع یال‌ها در صفحه ترسیم شده باشد را صفحه گراف یا گراف محاط در صفحه می‌نامند. یک صفحه گراف را می‌توان به صورت یک گراف مسطح تعریف کرد که هر گره‌ای را به نقطه‌ای در فضای دوبعدی و هر یالی را به خمی در صفحه می‌نگارد به گونه‌ای که نقاط انتهایی هر خم نقاطی هستند که از گره‌ها نگاشته شده‌اند و خم‌ها هیچ اشتراکی با یکدیگر ندارند مگر در نقاط انتهایی. گراف‌های مسطح بیرونی: یک گراف، مسطح بیرونی نامیده می‌شود اگر در صفحه محاط شده باشد به گونه‌ای که راس‌ها بر روی یک دایره قرار گرفته باشند و یال‌ها داخل قرصی از دایره قرار گرفته باشند و یکدیگر را قطع نکنند. به‌طور مشابه وجوهی وجود دارند که هر یک از راس‌ها را دربرمی گیرند. هر گراف مسطح بیرونی یک گراف مسطح نیز هست اما عکس این مطلب درست نیست: گراف دومی که در مثال‌های بالا نشان داده شده‌است (K4) یک گراف مسطح است اما گراف مسطح بیرونی نیست. این گراف کوچکترین گرافی است که مسطح بیرونی نیست. نظریه‌ای مشابه با نظریه کوراتوسکی بیان می‌دارد که یک گراف متناهی، مسطح بیرونی است اگر و تنها اگر شامل زیرگرافی نباشد که بسطی از K4 (گراف کامل با ۴ راس) یا K2،3 (گراف دوبخشی کامل با ۵ راس و ۶ یال) ویژگی‌های گراف‌های مسطح بیرونی: تمام درخت‌ها متناهی یا نامتناهی شمارش پذیر، گراف مسطح بیرونی و از این رو گراف مسطح هستند. یک گراف مسطح بیرونی بدون حلقه دارای یک راس با درجه حداکثر ۲ است. تمامی گراف‌های مسطح بیرونی بدون حلقه را می‌توان با ۳ رنگ، رنگ آمیزی کرد. این حقیقت به‌طور برجسته‌ای در اثبات ساده شده نظریه Chvátal's art gallery توسط فیسک نشان داده شد. یک روش برای رنگ کردن گراف با سه رنگ می‌تواند به سادگی با برداشتن راس درجه ۲ و رنگ کردن باقی گراف به صورت بازگشتی و سپس اضافه کردن راس برداشته شده و رنگ کردن آن با رنگی متفاوت از دو راس همسایه‌اش صورت پذیرد.