سلام
درجه a طبق گفته سوال ۴ هست .پس به جز b و c بادوراس دیگه هم ارتباط داره.این دوراس دیگه می تونن هرکدوم ازرئوس زیردرخت هایی که ریشه آنها b و c هستند باشن.
گزینه ۲ درست نیست چون بالاخره a با یکی ازرئوس این دوزیردرخت ارتباط داره واین یعنی وجوددور.
گزینه ۳ الزامادرست نیست.اگر گراف G رو همین درخت پوشا به اضافه دویال حذف شده a درنظربگیریم اونوقت با حذف a گراف همبندنیست.
گزینه ۱ درست نیست چون باهمون استدلالی که برای گزینه ۳ آوردم گراف داری دومولفه همبندمیشه نه سه تا.
گزینه ۴ درسته.

سلام
ب نظرم گزینه ۴ و ۲ درست
مفهوم همبند:همبند یعنی باید در گراف بین همه رئوس مسیر وجود داشته باشه ورئوس گراف از یکدیگر قابل دسترس باشند.
حالا تو این سوال گراف اصلی هم بند بوده است

حالا رد یکی یکی گزینه ها:
گزینه یک: وقتی a در گراف اصلی درجه ۴ بوده یعنی دویال دیگه داشته که ب نودهای فرزند b یا c وصل بوده ک در پیمایش عمقی این یالها حذف شده حالا اگر در گراف gگره a رو حذف کنیم سه تا درخت جداگونه (منظورم ۳ تا مولفه همبند )نمیتونه باقی بمونه و دو مولفه هم بند میشه.میبینی ک b ,c هیچ مسیری دیگه بینشون نیست وهمبندی گراف G ازبین میره.

گزینه دو: داخل گراف dfs ک G نام گرفته من دوری نمیبینم یعنی فک میکنم این گزینه درست هست دور نداره ک

گزینه سوم :توضیحاتش همون توضیحات گزینه اوله با حذف a همبندی از بین میره


گزینه چهار :این گزینه اگر b را از گراف dfs حذف کنیم همبندی گراف dfs ازبین میره و درخت ب جنگل تبدیل میشه

اگر تحلیلم مورد داره لطفا اصلاح کنید.

(۲۹ آذر ۱۳۹۳ ۰۳:۲۸ ب.ظ)monji_421 نوشته شده توسط:  سلام
ب نظرم گزینه ۴ و ۲ درست
مفهوم همبند:همبند یعنی باید در گراف بین همه رئوس مسیر وجود داشته باشه ورئوس گراف از یکدیگر قابل دسترس باشند.
حالا تو این سوال گراف اصلی هم بند بوده است

حالا رد یکی یکی گزینه ها:
گزینه یک: وقتی a در گراف اصلی درجه ۴ بوده یعنی دویال دیگه داشته که ب نودهای فرزند b یا c وصل بوده ک در پیمایش عمقی این یالها حذف شده حالا اگر در گراف gگره a رو حذف کنیم سه تا درخت جداگونه (منظورم ۳ تا مولفه همبند )نمیتونه باقی بمونه و دو مولفه هم بند میشه.میبینی ک b ,c هیچ مسیری دیگه بینشون نیست وهمبندی گراف G ازبین میره.

گزینه دو: داخل گراف dfs ک G نام گرفته من دوری نمیبینم یعنی فک میکنم این گزینه درست هست دور نداره ک

گزینه سوم :توضیحاتش همون توضیحات گزینه اوله با حذف a همبندی از بین میره


گزینه چهار :این گزینه اگر b را از گراف dfs حذف کنیم همبندی گراف dfs ازبین میره و درخت ب جنگل تبدیل میشه

اگر تحلیلم مورد داره لطفا اصلاح کنید.

اینکه G دور داره فکر میکنم واضحه.چون ما دوراه برای رسیدن به یکی ازرئوس گراف ازطریق a داریم.

(۲۹ آذر ۱۳۹۳ ۰۴:۴۷ ب.ظ)King2 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۳:۲۸ ب.ظ)monji_421 نوشته شده توسط:  سلام
ب نظرم گزینه ۴ و ۲ درست
مفهوم همبند:همبند یعنی باید در گراف بین همه رئوس مسیر وجود داشته باشه ورئوس گراف از یکدیگر قابل دسترس باشند.
حالا تو این سوال گراف اصلی هم بند بوده است

حالا رد یکی یکی گزینه ها:
گزینه یک: وقتی a در گراف اصلی درجه ۴ بوده یعنی دویال دیگه داشته که ب نودهای فرزند b یا c وصل بوده ک در پیمایش عمقی این یالها حذف شده حالا اگر در گراف gگره a رو حذف کنیم سه تا درخت جداگونه (منظورم ۳ تا مولفه همبند )نمیتونه باقی بمونه و دو مولفه هم بند میشه.میبینی ک b ,c هیچ مسیری دیگه بینشون نیست وهمبندی گراف G ازبین میره.

گزینه دو: داخل گراف dfs ک G نام گرفته من دوری نمیبینم یعنی فک میکنم این گزینه درست هست دور نداره ک

گزینه سوم :توضیحاتش همون توضیحات گزینه اوله با حذف a همبندی از بین میره


گزینه چهار :این گزینه اگر b را از گراف dfs حذف کنیم همبندی گراف dfs ازبین میره و درخت ب جنگل تبدیل میشه

اگر تحلیلم مورد داره لطفا اصلاح کنید.

اینکه G دور داره فکر میکنم واضحه.چون ما دوراه برای رسیدن به یکی ازرئوس گراف ازطریق a داریم.

آخه این گرافی ک تو تصویر گراف G ، منظور گراف اصلی نیست وگرنه ۱۰۰درصد در گراف اصلی باتوجه ب درجه ۴ گره a دور وجود داره شاید من اشتباه میکنم ولی میشه دور رو داخل تصویر ب من نشون بدید از طریق راسها ممنون

(۲۹ آذر ۱۳۹۳ ۰۴:۵۵ ب.ظ)monji_421 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۴:۴۷ ب.ظ)King2 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۳:۲۸ ب.ظ)monji_421 نوشته شده توسط:  سلام
ب نظرم گزینه ۴ و ۲ درست
مفهوم همبند:همبند یعنی باید در گراف بین همه رئوس مسیر وجود داشته باشه ورئوس گراف از یکدیگر قابل دسترس باشند.
حالا تو این سوال گراف اصلی هم بند بوده است

حالا رد یکی یکی گزینه ها:
گزینه یک: وقتی a در گراف اصلی درجه ۴ بوده یعنی دویال دیگه داشته که ب نودهای فرزند b یا c وصل بوده ک در پیمایش عمقی این یالها حذف شده حالا اگر در گراف gگره a رو حذف کنیم سه تا درخت جداگونه (منظورم ۳ تا مولفه همبند )نمیتونه باقی بمونه و دو مولفه هم بند میشه.میبینی ک b ,c هیچ مسیری دیگه بینشون نیست وهمبندی گراف G ازبین میره.

گزینه دو: داخل گراف dfs ک G نام گرفته من دوری نمیبینم یعنی فک میکنم این گزینه درست هست دور نداره ک

گزینه سوم :توضیحاتش همون توضیحات گزینه اوله با حذف a همبندی از بین میره


گزینه چهار :این گزینه اگر b را از گراف dfs حذف کنیم همبندی گراف dfs ازبین میره و درخت ب جنگل تبدیل میشه

اگر تحلیلم مورد داره لطفا اصلاح کنید.

اینکه G دور داره فکر میکنم واضحه.چون ما دوراه برای رسیدن به یکی ازرئوس گراف ازطریق a داریم.

آخه این گرافی ک تو تصویر گراف G ، منظور گراف اصلی نیست وگرنه ۱۰۰درصد در گراف اصلی باتوجه ب درجه ۴ گره a دور وجود داره شاید من اشتباه میکنم ولی میشه دور رو داخل تصویر ب من نشون بدید از طریق راسها ممنون

دقت کنید شکلی که درصورت سوال به ماداده گراف G نیست بلکه درخت حاصل ازپیمایش DFS است.

(۲۹ آذر ۱۳۹۳ ۰۵:۲۰ ب.ظ)King2 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۴:۵۵ ب.ظ)monji_421 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۴:۴۷ ب.ظ)King2 نوشته شده توسط:  

(29 آذر ۱۳۹۳ ۰۳:۲۸ ب.ظ)monji_421 نوشته شده توسط:  سلام
ب نظرم گزینه ۴ و ۲ درست
مفهوم همبند:همبند یعنی باید در گراف بین همه رئوس مسیر وجود داشته باشه ورئوس گراف از یکدیگر قابل دسترس باشند.
حالا تو این سوال گراف اصلی هم بند بوده است

حالا رد یکی یکی گزینه ها:
گزینه یک: وقتی a در گراف اصلی درجه ۴ بوده یعنی دویال دیگه داشته که ب نودهای فرزند b یا c وصل بوده ک در پیمایش عمقی این یالها حذف شده حالا اگر در گراف gگره a رو حذف کنیم سه تا درخت جداگونه (منظورم ۳ تا مولفه همبند )نمیتونه باقی بمونه و دو مولفه هم بند میشه.میبینی ک b ,c هیچ مسیری دیگه بینشون نیست وهمبندی گراف G ازبین میره.

گزینه دو: داخل گراف dfs ک G نام گرفته من دوری نمیبینم یعنی فک میکنم این گزینه درست هست دور نداره ک

گزینه سوم :توضیحاتش همون توضیحات گزینه اوله با حذف a همبندی از بین میره


گزینه چهار :این گزینه اگر b را از گراف dfs حذف کنیم همبندی گراف dfs ازبین میره و درخت ب جنگل تبدیل میشه

اگر تحلیلم مورد داره لطفا اصلاح کنید.

اینکه G دور داره فکر میکنم واضحه.چون ما دوراه برای رسیدن به یکی ازرئوس گراف ازطریق a داریم.

آخه این گرافی ک تو تصویر گراف G ، منظور گراف اصلی نیست وگرنه ۱۰۰درصد در گراف اصلی باتوجه ب درجه ۴ گره a دور وجود داره شاید من اشتباه میکنم ولی میشه دور رو داخل تصویر ب من نشون بدید از طریق راسها ممنون

دقت کنید شکلی که درصورت سوال به ماداده گراف G نیست بلکه درخت حاصل ازپیمایش DFS است.

بله شما درست میگید من برداشتم از سوال بد بود ممنون