آمار پرسش:
- پرسیده شده: 2015-05-05 13:09:21 -0600
- مشاهده شده: 231 بار
- بروز شده: 2015-05-10 06:26:10 -0600
پرسش‌های مشابه:
چرا گراف بدون دور با n - 1 یال ، همبند است ؟
من با ترجمه ی گراف وست مشکل دارم :(
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
چون که باید حداقل سی کاراکتر باشه بیا اینم گرافه آقا!
گراف g با 2d+1 راس موجود است بطوریکه درجه هر راس ان d می باشد. ثابت کنید این گراف اویلری است. منبع: جلوه هایی از ترکیبیات ، ویکتور برایانت
شرح حال: my mama always said the life was like a box of chocolates. you never know what you are gonna get
2015-05-05 13:09:21 -0600
آقای جابز 71 ● 2 ● 3 ● 6
نظرات
1 پاسخ
اثبات همبند بودن گراف : دو راس مانند $u$ و $v$ را در نظر بگیرید. مجموعه همسایه های $u$ را $X$ و مجموعه همسایه های $v$ را $Y$ می نامیم. می دانیم سایز هر دو مجموعه $d$ است. اگر $X,Y$ هیچ اشتراکی نداشته باشند پس تعداد راس های کل گراف $2d+2$ می شود که از $2d+1$ بیشتر است که این تناقض است. پس قطعن این دو مجموعه اشتراک دارند پس اگر مثلن راس $w$ در اشتراک آنها باشد مسیر $uwv$ یک مسیر ار $u$ به $v$ است :)
اثبات اویلری بودن گراف : اگر $d$ زوج باشد که خب گراف اویلری است چون هر گرافی اویلری است اگر و تنها اگر درجه هر راسش زوج باشد و همبند باشد. حالا ثابت می کنم $d$ نمی تواند فرد باشد. فرض کنیم فرد باشد. مجموع درجات همه راس ها می شود $d(2d+1)$ که فرد است اما ما می دانیم که مجموع درجات در هر گرافی زوج است پس تناقض :)
تمام!
2015-05-05 14:09:02 -0600
ناسحا 345 ● 3 ● 4 ● 10
نظرات
سلام ممنون از حلت فقط اون تیکه دوم ریاضی وارش یعنی دی ضربدر یه چیزی رو میشه قشنگ تر بنویسی ممنون میشم
2015-05-08 14:25:39 -0600 آقای جابزپاسخ خوبی بود. اما به نظرم برای این که کامل باشه باید ثابت کنیم این گراف «همبند» هم هست. گرافی که همبند نباشه اویلری نیست.
2015-05-09 23:57:37 -0600 کلاه قرمزی