سلام دوستان
تو گراف زیر می توان گفت : چون میشه داخلش مثلث پیدا کرد پس دو بخشی نیست؟
سوال دوم : حالا که فهمیدیم دو بخشی نیست آیا میشه مسطح نبودنم نتیجه گرفت؟ یا مسطح بودن یا نبودن ربطی به دوبخشی بودن نداره؟
[attachment=17439]
شرط لازم و کافی دو بخشی بودن نداشتن دور با طول فرد هست که اینجا داریم پس دو بخشی نیست ، ولی این ربطی به مسطح بودن نداره
هر گراف نا مسطح K5 یا k3,3 رو باید به عنوان زیر مجموعه از خودش داشته باشه
به نظر من با یه نگاه سر سری که کردم این گراف مسطح اومد
سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
(۲۶ آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
سلام. دوستان اگه نشه یه گراف رو با حداکثر ۴ رنگ رنگامیزی کرد میدونیم مسطح نیست. یعنی یه شرط کافی برای مسطح نبون گرافه. گراف [tex]K_{3,3}[/tex] دو رنگ پذیره و مسطح نیست.
شرط وجود حداقل یال هم یه شرط کافیه. اگه شرط برقرار باشه میدونیم مسطح نیست. میشه یه [tex]K_5[/tex] رو دونظر بگیرید که به یه راسش یه درخت با ۲۰ راس متصله. مسطح نیست ولی این شرط رو هم برقرار نمیکنه.
درمورد همبندی گراف: درنظر بگیرید [tex]A=\{V_1,V_3,V_6\},B=\{V_2,V_5,V_7\}[/tex]. این گراف رو میشه با درنظر گرفتن یه راس کمکی به یه [tex]K_{3,3}[/tex] تبدیل کرد که مجموعه رئوسش رو بفرم A و B نوشتم. گراف مسطج نیست.
(۲۶ آذر ۱۳۹۳ ۰۲:۱۸ ق.ظ)Densike نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
اگر این شرط E>3V-6 برقرار باشد حتما گراف مسطح نیست . و اگر برقرار نباشد گراف ممکن مسطح باشد یا نباشد .
گراف مسطح گرافی که بتوان ان را درصفحه به گونه ای رسم کرد که یال های آن یکدیگر را قطع نکنند ، این گراف را نمی توان به این گونه ترسیم کرد پس مسطح نیست.
این گراف که مسطح نیست
شرط لازم و کافی برای مسطح نبودن اینه که خود گراف یا هموئوتروف آن یا k5 یا k3,3 رو به صورت زیر گرافی از خودش داشته باشه
هوئمومرف این گراف k3,3 رو به صورت زیر گراف داره
حالا اگر میخواید تعریف دقیق هموئوتروف رو بگم
(۲۶ آذر ۱۳۹۳ ۰۷:۵۴ ب.ظ)masoomeh_s نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۲:۱۸ ق.ظ)Densike نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
اگر این شرط E>3V-6 برقرار باشد حتما گراف مسطح نیست . و اگر برقرار نباشد گراف ممکن مسطح باشد یا نباشد .
گراف مسطح گرافی که بتوان ان را درصفحه به گونه ای رسم کرد که یال های آن یکدیگر را قطع نکنند ، این گراف را نمی توان به این گونه ترسیم کرد پس مسطح نیست.
بله این گراف مسطح نیست بحث اینه که به همین راحتی نمیشه گفت فلان گراف رو نمیشه طوری ترسیم کرد که یالهاش یکدیگر را قطع نکنند
بهتر اینه که از شرط لازم و کافی که گفتم استفاده شه
ممنون از همه دوستان
(۲۶ آذر ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط: این گراف که همبند نیست
شرط لازم و کافی برای مسطح نبودن اینه که خود گراف یا هموئوتروف آن یا k5 یا k3,3 رو به صورت زیر گرافی از خودش داشته باشه
هموئوتروف این گراف k3,3 رو به صورت زیر گراف داره
حالا اگر میخواید تعریف دقیق هموئوتروف رو بگم
(۲۶ آذر ۱۳۹۳ ۰۷:۵۴ ب.ظ)masoomeh_s نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۲:۱۸ ق.ظ)Densike نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
اگر این شرط E>3V-6 برقرار باشد حتما گراف مسطح نیست . و اگر برقرار نباشد گراف ممکن مسطح باشد یا نباشد .
گراف مسطح گرافی که بتوان ان را درصفحه به گونه ای رسم کرد که یال های آن یکدیگر را قطع نکنند ، این گراف را نمی توان به این گونه ترسیم کرد پس مسطح نیست.
بله این گراف مسطح اینه بحث اینه که به همین راحتی نمیشه گفت فلان گراف رو نمیشه طوری ترسیم کرد که یالهاش یکدیگر را قطع نکنند
بهتر اینه که از شرط لازم و کافی که گفتم استفاده شه
سلام نه ممنون
فقط در پاسخ شما که گفته بودید به نظرتون مسطح بود گفتم که مسطح نیست ..
(۲۶ آذر ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط: این گراف که همبند نیست
شرط لازم و کافی برای مسطح نبودن اینه که خود گراف یا هموئوتروف آن یا k5 یا k3,3 رو به صورت زیر گرافی از خودش داشته باشه
هموئوتروف این گراف k3,3 رو به صورت زیر گراف داره
حالا اگر میخواید تعریف دقیق هموئوتروف رو بگم
(۲۶ آذر ۱۳۹۳ ۰۷:۵۴ ب.ظ)masoomeh_s نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۲:۱۸ ق.ظ)Densike نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
اگر این شرط E>3V-6 برقرار باشد حتما گراف مسطح نیست . و اگر برقرار نباشد گراف ممکن مسطح باشد یا نباشد .
گراف مسطح گرافی که بتوان ان را درصفحه به گونه ای رسم کرد که یال های آن یکدیگر را قطع نکنند ، این گراف را نمی توان به این گونه ترسیم کرد پس مسطح نیست.
بله این گراف مسطح اینه بحث اینه که به همین راحتی نمیشه گفت فلان گراف رو نمیشه طوری ترسیم کرد که یالهاش یکدیگر را قطع نکنند
بهتر اینه که از شرط لازم و کافی که گفتم استفاده شه
ممنون از جوابتون
ولی منظورتون رو از هموئوتروف نفهمیدم (همون ایزومورف نیست؟) ! اگه توضیح بدید ممنون میشم
(۲۷ آذر ۱۳۹۳ ۱۲:۰۵ ق.ظ)L3ic نوشته شده توسط:(26 آذر ۱۳۹۳ ۱۱:۴۴ ب.ظ)Densike نوشته شده توسط: این گراف که همبند نیست
شرط لازم و کافی برای مسطح نبودن اینه که خود گراف یا هموئوتروف آن یا k5 یا k3,3 رو به صورت زیر گرافی از خودش داشته باشه
هموئوتروف این گراف k3,3 رو به صورت زیر گراف داره
حالا اگر میخواید تعریف دقیق هموئوتروف رو بگم
(۲۶ آذر ۱۳۹۳ ۰۷:۵۴ ب.ظ)masoomeh_s نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۲:۱۸ ق.ظ)Densike نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۲۷ ق.ظ)masoomeh_s نوشته شده توسط: سلام
گراف دوبخشی:
هر گرافی را که بتوان با ۲ رنگ ، رنگ کرد گراف دوبخشی گوییم ..
گراف مسطح:
در گراف ساده و همبندو مسطح g اگر v=>3 باشد انگاه e<=3v-6 است .
در گراف ساده و همبندو مسطح g اگر v=>3 اگر حداقل دورها طولشان ۴ باشد (دور به طول ۳ نداشته باشد) ۴-e<=2v
در گراف ساده و همبند g اگر E>3V-6 انگاه گراف مسطح نیست .
هر گراف مسطح را می توان حداکثر با ۴ رنگ ، رنگ کرد.
این گراف مسطح نیست..
این گراف رو با ۳ رنگ میشه رنگ کرد ، در ضمن ۱۶ تا یال هست پس ： ۱۶<= 6 - 3*8 که این هم صادقه
اگر این شرط E>3V-6 برقرار باشد حتما گراف مسطح نیست . و اگر برقرار نباشد گراف ممکن مسطح باشد یا نباشد .
گراف مسطح گرافی که بتوان ان را درصفحه به گونه ای رسم کرد که یال های آن یکدیگر را قطع نکنند ، این گراف را نمی توان به این گونه ترسیم کرد پس مسطح نیست.
بله این گراف مسطح اینه بحث اینه که به همین راحتی نمیشه گفت فلان گراف رو نمیشه طوری ترسیم کرد که یالهاش یکدیگر را قطع نکنند
بهتر اینه که از شرط لازم و کافی که گفتم استفاده شه
ممنون از جوابتون
ولی منظورتون رو از هموئوتروف نفهمیدم (همون ایزومورف نیست؟) ! اگه توضیح بدید ممنون میشم
هومئوتروفی یعنی این :
اگر A به B یال داره و B به C یال داره و B درجه ۲ هست حق داری B رو حذف کنی و A رو مستقیم به C وصل کنی
حالا اگر تو یه زیر گراف از گرافت پیدا کنی که یه هومئوتروفی داشته باشه که k3,3 یا k5 رو به صورت زیر گراف داره حتما نامسطح است و اگر نداشت مسطح هست ( چون شرط لازم و کافی هست )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
توی این لینک وسطاش یه انیمیشن هست تحت عنوان : Kuratowski's theorem
توی این خیلی خوب نشون داده شده
ببخشید دوستان من همه پست های قبلی رو با گوشی بودم الان که اومدم دیدم کلی غلط تایپی داشتم و کلی چیز رو اشتباه نوشتم ... الان اصلاحشون کردم