آقا من تو تشخیص گراف های مسطح مسئله ای دارم، لطفا راهنمایی کنید که چجوری تشخیص بدم که گرافی مسطح هست یا نه؟
من مثالی براتون پیوست کرده ام، لطفا توضیحات را در قالب این مثال بفرمایید.
میدونیم که
گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند.
یک گراف غیر مسطح گرافی است که نمی‌توان آن را به گونه‌ای رسم کرد که یال‌هایش یکدیگر را در نقاطی غیراز راس‌ها قطع نکنند.
یه راه اینه که بدونیم شکل [tex]K_{3,3}[/tex] یا [tex]k_{5}[/tex] یا زیر گرافی از اینها هستن نه! ( شرط لازم و کافی)
راه دوم : (این فرمول شرط کافی برای مسطح نبودن است و یک شرط لازم نیست. )
[tex]e>3v-6[/tex] اگر برقراره مسطح نیست!
(در یک گراف ساده و همبند ، e : تعداد یالها و v : تعداد رئوس و v بزرگتر مساوی ۳)