تالار گفتمان مانشت
به دست آوردن درجه یک گراف - نسخه‌ی قابل چاپ
به دست آوردن درجه یک گراف - nazanin2020 - 06 دى ۱۳۹۳ ۰۱:۱۵ ق.ظ

جواب گزینه دو هست.
کسی میتونه کامل اینو توضیح بده؟
از راه حل تشریحی ی چیزاییشو متوجه شدم. ولی با ی قسمتش مشکل دارم.
با تشکر

[تصویر: 323648_06308866655393928801.jpg]

RE: به دست آوردن درجه یک گراف - Pure Liveliness - 06 دى ۱۳۹۳ ۰۸:۵۲ ق.ظ

(۰۶ دى ۱۳۹۳ ۰۱:۱۵ ق.ظ)nazanin2020 نوشته شده توسط:  جواب گزینه دو هست.
کسی میتونه کامل اینو توضیح بده؟
از راه حل تشریحی ی چیزاییشو متوجه شدم. ولی با ی قسمتش مشکل دارم.
با تشکر

[تصویر: 323648_06308866655393928801.jpg]
ببخشید ممکنه پاسخ تشریحی رو بذارید؟ من دچار تناقض شدم!
تعداد یال ها * ۲ = مجموع درجات رأس های یک گراف =>> مجموع درجات رأس های گرافG میشود ۵۶*۲ = ۱۱۲= D1
مجموع درجات رأس های گراف'G برابر است با ۱۶۰ = D2
مجموع درجات رأس های گراف کامل برابر است با D1+D2 = ۱۶۰+۱۱۲= ۲۷۲
تعداد یال های گراف کامل با n رأس = انتخاب ۲ از n-1 )*n/2 = n)
مجموع درجات رأس های گراف کامل برابر است با دو برابر تعدا یال ها یعنی n-1 )*n)
n-1 *n = ۲۷۲ ==>> n= ۱۷
تعداد رأس های گراف ۱۷ تا است. در گراف کامل درجه ی هر رأس برابر است با تعداد رأس ها منهای ۱ ==>> درجه ی هر رأس در گراف کامل ۱۶
در این صورت حداکثر درجه ی گراف ۱۶ هست. ک اونم نمیشه.
پ ن : پس حداکثر درجه رو میخواسته ((-:
ولی یه چیزی! من الآن جوابشو دیدم. گراف از درجه ی‌n یعنی چند تا راس داره.ک میشه گزینه ی ۳
نه حداکثر درجه. چون حداکثر درجه شاید الزاما ۱۶‌ نباشه.

RE: به دست آوردن درجه یک گراف - MiladCr7 - 06 دى ۱۳۹۳ ۰۱:۳۹ ب.ظ

سلام
امیدوارم با توضیحم گیجتون نکنمSmileSmile

خب بریم حل.ببینید تعریف گراف کامل در گراف غیر جهت دار رو در نظر بگیرید.مثلا یه گراف کامل با ۴ راس رو در نظر بگیرید :
تعداد یال ها در گراف غیر جهت دار با توجه به رابطه [tex]\frac{n(n-1)}{2}[/tex] میشه [tex]\frac{(4\ast3)}{2}=6[/tex]
حالا یه گرافی رو در نظر بگیر که ۴ تا راس داره و ۳ تا یال!!حالا قبول داری مکمل این گراف هم ۳ تا یال داره؟؟؟(مرجع رو تعداد یال های گراف کامل فرض کن).پس تعداد یال های یه گراف + تعداد یال های گراف مکمل باید تعداد یال های گراف کامل رو بده(با تعداد رئوس مساوی)

حالا یه نکته دیگه.فرض کن دو تا راس داریم و یه یال مجموع درجات رئوس میشه ۲ درسته؟؟؟؟یا اگه سه تا راس داشته باشیم و دو تا یال مجموع درجات رئوس میشه ۴

پس داریم:مجموع درجات رئوس در گراف غیر جهت دار دو برابر تعداد یال هاست

حالا با اطلاعاتی که داریم سوالو حل میکنیم:گراف [tex]G[/tex] خودش ۵۶ یال داره و مجموع درجات رئوس گراف مکملش ۱۶۰ هستش یعنی گراف مکمل [tex]G[/tex] هم ۸۰ تا یال داره.
پس گراف کامل دارای [tex]80 56=136[/tex] یال هست
پس داریم:[tex]\frac{(n\ast(n-1))}{2}=136\rightarrow n=17[/tex]
پس گراف ما ۱۷ تا راس داره پس درجه اون حداکثر ۱۶ هستش
پس گزینه دوم درسته

دقت کنید مجموعه درجه رئوس رو نخواسته بلکه درجه گراف رو خواسته یعنی راسی رو پیدا کنیم که بیشترین تعداد یال رو از خودش عبور داده باشه

ببخشید اگه بد توضیح دادم

RE: به دست آوردن درجه یک گراف - nazanin2020 - 06 دى ۱۳۹۳ ۰۳:۱۴ ب.ظ

نه اتفاقا خیلی عالی توضیح دادید. کاملا متوجه ایرادم شدم Smile واقعا ممنون بخاطر وقتی ک گذاشتید.


(۰۶ دى ۱۳۹۳ ۰۸:۵۲ ق.ظ)pure liveliness نوشته شده توسط:  ببخشید ممکنه پاسخ تشریحی رو بذارید؟ من دچار تناقض شدم!

پ ن : پس حداکثر درجه رو میخواسته ((-:

آره حداکثر رو میخواسته منم اتفاقا با این موضوع درگیر بودم Big Grin
[تصویر: 323699_94434895558013720407.jpg]