گراف صفحه ای (Planar Graph)، در ریاضیات (Mathematics)
انواع گراف ساده (Simple Graph) را در آموزش زیر شرح دادیم :
گراف صفحه ای (Planar Graph) :
گراف صفحه ای گرافی است که می توان آن را روی یک صفحه (Page) یا کره (Sphere) به گونه ای رسم کرد که هیچ یک از یال ها یکدیگر را جز در نقاط پایانی (رأس ها) قطع نکنند. به عبارت دیگر، امکان رسم گراف بدون تقاطع یال ها (Crossing) وجود دارد. برای مثال، گراف
\[ K_4 \](کامل ۴ رأسی) صفحه ای است، اما گراف
\[ K_5 \](کامل ۵ رأسی) صفحه ای نیست. همچنین گراف دو بخشی
\[ K_{3,3} \]نیز صفحه ای نیست. این دو گراف (
\[ K_5 \]و
\[ K_{3,3} \]) به عنوان موانع اصلی صفحه ایی بودن (Planarity) شناخته می شوند. قضیه کوراتوسکی (Kuratowski's Theorem) بیان می کند که یک گراف صفحه ای است اگر و تنها اگر شامل زیرگرافی نباشد که با تقسیم کردن یال ها (Subdivision) بتوان آن را به
\[ K_5 \]یا
\[ K_{3,3} \]تبدیل کرد. فرمول معروف اویلر (Euler's Formula) برای گراف های صفحه ای همبند به صورت
\[ V - E + F = 2 \]است که در آن
\[ V \]تعداد رأس ها،
\[ E \]تعداد یال ها و
\[ F \]تعداد نواحی (Faces) است.
\[ V - E + F = 2 \]