گراف مسطح (Planar Graph)، در ریاضیات (Mathematics)
انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :
گراف مسطح (Planar Graph) :
گراف مسطح به گرافی گفته می شود که بتوان آن را روی صفحه (Page) یا کره (Sphere) به گونه ای رسم کرد که هیچ یک از یال ها (Edges) یکدیگر را قطع نکنند. به این نوع رسم، "نمایش مسطح" (Planar Embedding) می گویند. برای مثال، گراف کامل با ۴ رأس (
\[ K_4 \]) یک گراف مسطح است، زیرا می توان آن را بدون قطع شدن یال ها رسم کرد. در مقابل، گراف کامل با ۵ رأس (
\[ K_5 \]) مسطح نیست. قضیه معروف **کوراتوسکی (Kuratowski)** شرط لازم و کافی برای مسطح بودن یک گراف را بیان می کند: یک گراف مسطح است اگر و تنها اگر شامل زیرگرافی هم ریخت با تقسیم بندی (Subdivision)
\[ K_5 \]یا
\[ K_{3,3} \]نباشد. این مفهوم در طراحی مدارهای الکترونیکی و نقشه های جغرافیایی کاربرد دارد.
\[ K_5 \text{ غیرمسطح است.} \] نویسنده علیرضا گلمکانی
شماره کلید 5498
گزینه ها 
نظرات 0 0 0