زمان کنونی: ۰۳ تیر ۱۳۹۸, ۰۷:۴۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال : گسسته - گراف - قضیه اویلر

ارسال:
  

Morris پرسیده:

سوال : گسسته - گراف - قضیه اویلر

تمرین ۲۲ بخش ۴ از فصل یازدهم کتاب گریمالدی :

الف) فرض کنید [tex]G=(V,E)[/tex] گراف همبند بیطوقه ای باشد که در آن [tex]|V|\ge11[/tex] . ثابت کنید که یا G یا مکمل آن [tex]G^-[/tex] باید نامسطح باشد.
ب) نتیجه قسمت (الف) در واقع به ازای هر [tex]|V|\ge9[/tex] درست است، ولی اثبات آن به ازای [tex]|V|=9[/tex] و [tex]|V|=10[/tex] بسیار دشوارتر است. به ازای [tex]|V|=8[/tex] یک مثال نقض برای قسمت (الف) بیابید.


من با اثبات و مثال نقض مشکلی ندارم.

سوالم اینه :
من یه اثباتی بدست آوردم که نشون می ده به ازای [tex]|V|[/tex] برابر ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ می توان گرافی رسم نمود که خود و مکملش مسطح هستند و این به این معنی است که قضیه مطرح شده در قسمت الف به ازای تعداد راس های ۹ و ۱۰ درست نیست و این با ادعای آورده شده در قسمت (ب) در تناقض است.

اثبات مورد نظر به صورت زیر است :
قصد داریم گراف هایی را بیابیم که خود و مکمل آن ها مسطح است. بنابراین طبق فرع قضیه اویلر خواهیم داشت :
[tex]e\le3v-6[/tex]
و چون مکمل آن نیز مسطح است خواهیم داشت :
[tex]\frac{v(v-1)}{2}-e\le3v-6[/tex]

در نتیجه از ترکیب این دو خواهی داشت :


[tex]\frac{v(v-1)}{2}-3v 6\le e\le3v-6[/tex]
در نتیجه خواهیم داشت :
[tex]\frac{v(v-1)}{2}-3v 6\le3v-6[/tex]
بنابراین خواهیم داشت :
[tex]V^2-13V 24\le0[/tex]


ریشه های معادله فوق برابر با ۲ و خورده ای و ۱۰ و خورده ای است. بنابراین به ازای V های ۳ و ۴ و ۵ و ۶ و ۷ و ۸ و ۹ و ۱۰ این رابطه درست خواهد بود.



یعنی به ازای تعداد راس های ۹ و ۱۰ نیز گراف هایی موجود می باشند که هم خود و هم مکمل آن مسطح باشند. و این با قسمت ب در تناقض است.




اشتباهم چیست ؟

۱
ارسال:
  

Jooybari پاسخ داده:

RE: سوال : گسسته - گراف - قضیه اویلر

سلام. یه نکته بگم که اون رابطه شرط کافیه برای مسطح نبودن. همون k3,3 هم طبق رابطه نشون نمیده که مسطح نیست.

ارسال:
  

Morris پاسخ داده:

RE: سوال : گسسته - گراف - قضیه اویلر

(۱۳ مرداد ۱۳۹۳ ۰۱:۱۱ ق.ظ)Jooybari نوشته شده توسط:  سلام. یه نکته بگم که اون رابطه شرط کافیه برای مسطح نبودن. همون k3,3 هم طبق رابطه نشون نمیده که مسطح نیست.


بله حق با شماست. فهمیدم اشتباهم کجاست.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question سوال ۱۴ فصل ۲ ساختمانهای گسسته قلی زاده nrique ۷ ۲,۲۰۱ ۱۹ مهر ۱۳۹۳ ۰۷:۲۴ ب.ظ
آخرین ارسال: nrique
Tongue بخش گراف: محاسبه ماکزیمم طول دور یک گراف ashena1 ۱ ۱,۴۶۳ ۰۴ شهریور ۱۳۹۳ ۰۵:۰۷ ب.ظ
آخرین ارسال: fatemeh69
  سوال تعداد مسیرها در یک گراف دوبخشی amir2930 ۱ ۱,۱۶۷ ۱۳ مرداد ۱۳۹۳ ۰۷:۳۳ ب.ظ
آخرین ارسال: Morris
  نامساوی در گراف با دوری به طول ۵ amir2930 ۳ ۱,۲۰۳ ۲۷ خرداد ۱۳۹۳ ۰۸:۲۰ ق.ظ
آخرین ارسال: amir2930
  سوال تعداد یالهای گراف amir2930 ۴ ۱,۳۶۱ ۲۶ خرداد ۱۳۹۳ ۰۱:۳۹ ب.ظ
آخرین ارسال: amir2930
  سوال زوج مرتب در گراف همبند amir2930 ۴ ۱,۱۱۱ ۲۶ خرداد ۱۳۹۳ ۱۰:۰۰ ق.ظ
آخرین ارسال: amir2930
  سوال افراز گراف به مثلث amir2930 ۱ ۹۲۵ ۲۵ خرداد ۱۳۹۳ ۰۳:۴۰ ب.ظ
آخرین ارسال: Jooybari
  سوال از تطابق در گراف دوبخشی amir2930 ۳ ۱,۲۴۵ ۲۴ خرداد ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: Jooybari
  تست گسسته موضوع گراف hana.rahmati ۱ ۹۸۷ ۲۰ اسفند ۱۳۹۲ ۰۳:۱۲ ق.ظ
آخرین ارسال: Jooybari
  تست گسسته مبحث تابع hana.rahmati ۱ ۸۶۴ ۲۰ اسفند ۱۳۹۲ ۰۳:۰۵ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close