۰
subtitle
ارسال: #۱
  
نحوه تشخیص گراف های مسطح
آقا من تو تشخیص گراف های مسطح مسئله ای دارم، لطفا راهنمایی کنید که چجوری تشخیص بدم که گرافی مسطح هست یا نه؟
من مثالی براتون پیوست کرده ام، لطفا توضیحات را در قالب این مثال بفرمایید.
من مثالی براتون پیوست کرده ام، لطفا توضیحات را در قالب این مثال بفرمایید.
۴
ارسال: #۲
  
RE: نحوه تشخیص گراف های مسطح
میدونیم که
گراف مسطح گرافی است که میتواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را میتوان به گونهای رسم کرد که یالهایش یکدیگر را تنها در راسها قطع کنند.
یک گراف غیر مسطح گرافی است که نمیتوان آن را به گونهای رسم کرد که یالهایش یکدیگر را در نقاطی غیراز راسها قطع نکنند.
یه راه اینه که بدونیم شکل [tex]K_{3,3}[/tex] یا [tex]k_{5}[/tex] یا زیر گرافی از اینها هستن نه! ( شرط لازم و کافی)
راه دوم : (این فرمول شرط کافی برای مسطح نبودن است و یک شرط لازم نیست. )
[tex]e>3v-6[/tex] اگر برقراره مسطح نیست!
(در یک گراف ساده و همبند ، e : تعداد یالها و v : تعداد رئوس و v بزرگتر مساوی ۳)
گراف مسطح گرافی است که میتواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را میتوان به گونهای رسم کرد که یالهایش یکدیگر را تنها در راسها قطع کنند.
یک گراف غیر مسطح گرافی است که نمیتوان آن را به گونهای رسم کرد که یالهایش یکدیگر را در نقاطی غیراز راسها قطع نکنند.
یه راه اینه که بدونیم شکل [tex]K_{3,3}[/tex] یا [tex]k_{5}[/tex] یا زیر گرافی از اینها هستن نه! ( شرط لازم و کافی)
راه دوم : (این فرمول شرط کافی برای مسطح نبودن است و یک شرط لازم نیست. )
[tex]e>3v-6[/tex] اگر برقراره مسطح نیست!
(در یک گراف ساده و همبند ، e : تعداد یالها و v : تعداد رئوس و v بزرگتر مساوی ۳)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close