سلام. تا اونجا که یادمه هردو سوال در انجمن مطرح شدن.
هر گراف غیر همبند از چند مولفه همبند تشکیل میشه. درواقع هر "زیرمجموعه از رئوس بهمراه یالهای متصل همبند" از یک گراف غیر همبند که با هیچ راس دیگری مجاورت نداشته باشن یک مولفه محسوب میشن.

سوال ۹:
سوال از ما کمترین تعداد یال را میخواد
یک گراف همبند زمانی که درخت باشد کمترین یال را داره
پس طبق صورت سوال k مولفه یعنی k درخت داریم که تعداد یال هر درخت مساوی ست با: [tex]n-1[/tex]
پس:


پس: [tex]m\geq n-k[/tex]

--------------------------------------------------------------------------------------------------------------------------------------------------
سوال ۲۷:
اول تو ذهنتون شماره گذاری کنید راس بالا=۱ , راس پایین اولی از چپ=۲ , راس پایین دومی از چپ=۲ , سومی=۴ , چهارمی=۵
گراف دارای هفت یال و پنج راس میباشد و برای اینکه درخت باشه باید تعداد یالها ۴تا باشه(یکی کمتر از تعداد راس ها). پس باید سه یال را حذف کنیم.تعداد راههایی که میتوان سه یال را حذف کنیم: [tex]\binom{7}{3}=35[/tex]
ولی از این ۳۵تا بعضی مواقع ممکنه که سه یال حذف کنیم ولی باز هم دارای دور باشه:
وقتی دویال متصل به راس۲ و یک یال دیگر حذف شود: [tex]\binom{5}{1}=5[/tex]
وقتی دویال متصل به راس۵ و یک یال دیگر حذف شود: [tex]\binom{5}{1}=5[/tex]
وقتی هر سه یال متصل به راس ۳ حذف شود: [tex]1[/tex]

وقتی هر سه یال متصل به راس ۴ حذف شود: [tex]1[/tex]

تعداد زیر درختهای فراگیر: [tex]35-5-5-1-1=23[/tex]

با تشکر از دوستمون آقای mhm-pc باید بگم توی سوال دوم شرط همبندی رو درنظر نگرفتید. یالهای ۱|۵ (بین رئوس ۱ و ۵) و ۱|۴ و ۳|۴ رو حذف کنیم همبند نیست. و بطور متقارن ۱|۲ و ۱|۳ و ۳|۴ رو هم همینطور. جواب میشه ۲۱ که البته من به یه روش دیگه رفتم. ۳ یال پایینی رو درنظر بگیرید. ۸ حالت برای انتخاب یا حذفشون داریم. به ازای هرکدوم از این ۸ حالت ببینیم چند حالت برای ۴ یال بالایی داریم. جواب مسئله میشه جمع این حالت ها.

تشکر میکنم از دوستان به خاطر محبتی که به من داشتن و با حوصله تمام به سوالاتم جواب دادن

جواب آقای Jooybari خیلی پیچیده هست
و جواب آقای mhm-pc یکی درست که از ین بابت بسیار سپاس گزارم و دیگری اشتباه ،اگر امکان داره بگید از روش خودتون پاسخ صحیحش چطوری میشه؟ مطمئنم راه صحیحی از این روش شما هم وجود دارد اما فعلا به آن فکر نکرده ام

اما روش شما آقای Jooybari من حلش کردم اما به جواب ۲۰ رسیدم اشکال در چیست؟ اشتباه کجاست؟ راه ساده تری وجود ندارد؟ برخلاف دیگر پاسخ های راحت و شیوا و سریعتان این یکی خیلی زمان میبرد . راستی شما چگونه به این درس مسلط شدید و این گونه زیبا پاسخ میدهید؟


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۱۸ مرداد ۱۳۹۲ ۰۲:۴۵ ب.ظ)learned نوشته شده توسط:  و جواب آقای mhm-pc یکی درست که از ین بابت بسیار سپاس گزارم و دیگری اشتباه ،اگر امکان داره بگید از روش خودتون پاسخ صحیحش چطوری میشه؟

خوب آقای جویباری که توضیح دادند که من شرط همبندی را در نظر نگرفته بودم. این دو حالتو که در نظر بگیری جواب همون ۲۱ میشه

(۱۷ مرداد ۱۳۹۲ ۰۷:۵۹ ب.ظ)Jooybari نوشته شده توسط:  با تشکر از دوستمون آقای mhm-pc باید بگم توی سوال دوم شرط همبندی رو درنظر نگرفتید. یالهای ۱|۵ (بین رئوس ۱ و ۵) و ۱|۴ و ۳|۴ رو حذف کنیم همبند نیست. و بطور متقارن ۱|۲ و ۱|۳ و ۳|۴ رو هم همینطور.

حالت شماره ۳ در شکل شما اشکال داره. تعداد ۴ تاست که شما نوشتید ۳ تا. وقتی یال وسطی رو نداشته باشیم باید یکی از دویال سمت چپ و یکی از دو یال سمت راست انتخاب بشه. میشه ۴ حالت.

اینی که از این روش رفتم بخاطر این بود که راحت میشه تمام حالات رو ازهم جدا کرد. حالت تکراری نداریم و تمام حالات درنظر گرفته میشن. روش آقای mhm-pc سریعتره ولی امکان اشتباه توش هست.

(۱۸ مرداد ۱۳۹۲ ۱۰:۵۵ ب.ظ)Jooybari نوشته شده توسط:  حالت شماره ۳ در شکل شما اشکال داره. تعداد ۴ تاست که شما نوشتید ۳ تا. وقتی یال وسطی رو نداشته باشیم باید یکی از دویال سمت چپ و یکی از دو یال سمت راست انتخاب بشه. میشه ۴ حالت.

اینی که از این روش رفتم بخاطر این بود که راحت میشه تمام حالات رو ازهم جدا کرد. حالت تکراری نداریم و تمام حالات درنظر گرفته میشن. روش آقای mhm-pc سریعتره ولی امکان اشتباه توش هست.

عالی بود مرسیییییییییی
مشکلم حل شد