12 مرداد 1393, 09:39 ب.ظ
تمرین ۲۲ بخش ۴ از فصل یازدهم کتاب گریمالدی :
الف) فرض کنید [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]
ریشه های معادله فوق برابر با 2 و خورده ای و 10 و خورده ای است. بنابراین به ازای V های 3 و 4 و 5 و 6 و 7 و 8 و 9 و 10 این رابطه درست خواهد بود.
یعنی به ازای تعداد راس های 9 و 10 نیز گراف هایی موجود می باشند که هم خود و هم مکمل آن مسطح باشند. و این با قسمت ب در تناقض است.
اشتباهم چیست ؟
الف) فرض کنید [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]
ریشه های معادله فوق برابر با 2 و خورده ای و 10 و خورده ای است. بنابراین به ازای V های 3 و 4 و 5 و 6 و 7 و 8 و 9 و 10 این رابطه درست خواهد بود.
یعنی به ازای تعداد راس های 9 و 10 نیز گراف هایی موجود می باشند که هم خود و هم مکمل آن مسطح باشند. و این با قسمت ب در تناقض است.
اشتباهم چیست ؟