گراف دو بخشی کامل مسطح (Complete Bipartite Planar Graph)، در ریاضیات (Mathematics)
انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :
گراف دو بخشی کامل مسطح (Complete Bipartite Planar Graph) :
این نوع گراف، یک گراف دو بخشی (Bipartite) است که بخش اول دارای
\[ m \]رأس و بخش دوم دارای
\[ n \]رأس است و همه رئوس بخش اول به همه رئوس بخش دوم متصل هستند (نشان دهی:
\[ K_{m,n} \]) و خاصیت مسطح بودن را دارد. این گراف ها در صورتی مسطح هستند که حداقل یکی از اعداد
\[ m \]یا
\[ n \]کمتر از ۳ باشد. برای مثال،
\[ K_{2,n} \](مانند
\[ K_{2,5} \]) همیشه مسطح است و می توان آن را به راحتی رسم کرد. اما
\[ K_{3,3} \]مسطح نیست و همراه با
\[ K_5 \]، دو مثال اصلی در قضیه کوراتوسکی برای تشخیص گراف های غیرمسطح محسوب می شوند.
\[ K_{3,3} \text{ مسطح نیست.} \] نویسنده علیرضا گلمکانی
شماره کلید 5505
گزینه ها 
نظرات 0 0 0