۰
subtitle
ارسال: #۱
  
مولفه همبند قوی
سلام
روش کنکوری و سریع برای بدست اوردن مولفه ی همبند قوی وجود داره؟!
مثلاً سوالهایی مثل این سوال پیوست شده رو چطوری میشه بدون اجرای الگوریتم طولانی، حل کرد؟
روش کنکوری و سریع برای بدست اوردن مولفه ی همبند قوی وجود داره؟!
مثلاً سوالهایی مثل این سوال پیوست شده رو چطوری میشه بدون اجرای الگوریتم طولانی، حل کرد؟
۱
ارسال: #۲
  
RE: مولفه همبند قوی
سلام
راه حل غیر سریع :
تا جایی که من خوندم نه . نکته کنکوری برای این وجود نداره . ولی این راحت حل میشه .
گرافشو شما بکش
خواهی دید که راس F و راس D نمیتونن به عنوان رئوس همبند قوی انتخاب بشن
(( چون F فقط خروجی داره و D فقط ورودی داره ))
و تو همبند قوی باید مسیر رفت و برگشت داشته باشیم .
پس ۱ و ۳ و ۴ میرن
میمونه ۲ . گزینه ۲ صحیحه
راه حل سریع :
بدون کشیدن گرافم میشه فهمید که از هیچ یالی به F مسیر نداریم . همشون ۰ هستن . پس F یکطرفه هستش
D هم به بقیه راس ها همش ۰ هستش پس مسیری به سایر رئوس از D نداریم ( یکطرفه )
راه حل غیر سریع :
تا جایی که من خوندم نه . نکته کنکوری برای این وجود نداره . ولی این راحت حل میشه .
گرافشو شما بکش
خواهی دید که راس F و راس D نمیتونن به عنوان رئوس همبند قوی انتخاب بشن
(( چون F فقط خروجی داره و D فقط ورودی داره ))
و تو همبند قوی باید مسیر رفت و برگشت داشته باشیم .
پس ۱ و ۳ و ۴ میرن
میمونه ۲ . گزینه ۲ صحیحه
راه حل سریع :
بدون کشیدن گرافم میشه فهمید که از هیچ یالی به F مسیر نداریم . همشون ۰ هستن . پس F یکطرفه هستش
D هم به بقیه راس ها همش ۰ هستش پس مسیری به سایر رئوس از D نداریم ( یکطرفه )
ارسال: #۳
  
RE: مولفه همبند قوی
ممنون
آره این سوال راحته.
جواب هم که گفتید همون گزینه ۲ هست.
ولی ممکنه سواله دیگه باشه که نشه به این راحتی گزینه هاشو حذف کرد و جواب رو پیدا کرد.
میخواستم ببینم در اون صورت راه حل دیگه ای هم هست یا نه.
آره این سوال راحته.
جواب هم که گفتید همون گزینه ۲ هست.
ولی ممکنه سواله دیگه باشه که نشه به این راحتی گزینه هاشو حذف کرد و جواب رو پیدا کرد.
میخواستم ببینم در اون صورت راه حل دیگه ای هم هست یا نه.
ارسال: #۴
  
RE: مولفه همبند قوی
(۲۳ دى ۱۳۹۳ ۱۰:۴۱ ب.ظ)Ametrine نوشته شده توسط: ممنون
آره این سوال راحته.
جواب هم که گفتید همون گزینه ۲ هست.
ولی ممکنه سواله دیگه باشه که نشه به این راحتی گزینه هاشو حذف کرد و جواب رو پیدا کرد.
میخواستم ببینم در اون صورت راه حل دیگه ای هم هست یا نه.
انشالله که نمیشه . ولی نکته کنکوری ندیدم من برای این
تو آزمون ها هم عین همینه
مثلا یک نمونشو براتون پیوست کردم که تو آزمون ۱۰۰ درصد اول پارسه دادن
ارسال: #۶
  
RE: مولفه همبند قوی
ارسال: #۷
  
RE: مولفه همبند قوی
(۲۳ دى ۱۳۹۳ ۱۱:۴۳ ب.ظ)ardaaalan نوشته شده توسط: نهالان g چرا اومد اینجا؟
گزینه ۴ جوابه
تا یه جایی درست رفتی
ببین اینجا {C,F,E} همبند قوی هستش . و {A,E.D}
ولی چون این ها هر دوشون عنصر مشترک دارن با هم ادغام میشن و میشه a,c,d,e,f,g
و b هم که تنهاس
یعنی گزینه ۴
شما فقط ادغام نکردی اینه دو تا رو
تو هیچ کدوم نبود که
۰
ارسال: #۸
  
RE: مولفه همبند قوی
شرمنده بادم رفت
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
ارسال: #۹
  
RE: مولفه همبند قوی
(۲۳ دى ۱۳۹۳ ۱۱:۵۴ ب.ظ)ardaaalan نوشته شده توسط: شرمنده بادم رفتمنم این مسیر رو دیدم ولی گفتم شاید سوال اینو نمیخواد دیگه!
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
پس وقتی بین همبندها اشتراک بود باید با هم ادغام بشن.
ممنون
ارسال: #۱۰
  
RE: مولفه همبند قوی
(۲۳ دى ۱۳۹۳ ۱۱:۵۸ ب.ظ)Ametrine نوشته شده توسط:(23 دى ۱۳۹۳ ۱۱:۵۴ ب.ظ)ardaaalan نوشته شده توسط: شرمنده بادم رفتمنم این مسیر رو دیدم ولی گفتم شاید سوال اینو نمیخواد دیگه!
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
پس وقتی بین همبندها اشتراک بود باید با هم ادغام بشن.
ممنون
بله . خواهش میکنم
یه چیزی تو مایه های کلید خارجیه اون عنصر e
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close