گراف ماکسیمال مسطح (Maximal Planar Graph)، در ریاضیات (Mathematics)
انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :
گراف ماکسیمال مسطح (Maximal Planar Graph) :
گراف مسطحی است که با اضافه کردن حتی یک یال جدید، خاصیت مسطح بودن خود را از دست بدهد و دیگر نتوان آن را بدون تقاطع رسم کرد. به این گراف ها، گراف های **مثلثی شده (Triangulated)** نیز می گویند، زیرا در یک نمایش مسطح از این گراف، تمام وجوه (شامل وجه بیرونی) توسط سه یال محصور شده اند (مثلث هستند). رابطه معروفی برای تعداد یال ها در این گراف ها وجود دارد: اگر گراف
\[ n \]رأس داشته باشد (
\[ n \geq 3 \])، آنگاه حداکثر تعداد یال ها برابر
\[ 3n - 6 \]است. برای مثال، گراف
\[ K_4 \]یک گراف ماکسیمال مسطح است.
\[ E \leq 3n - 6 \quad (n \geq 3) \] نویسنده علیرضا گلمکانی
شماره کلید 5500
گزینه ها 
نظرات 0 0 0