کدوم اولی یا دومی؟
فکر کنم شما تعریف همبند قویو رو فراموش کردین. برای اینکه ببینی یه گراف چند جز همبند قوی داره باید نعداد دورها رو بشمرین.
یعنی با انتخاب زیرمجموعه ای از راسها بتونیم از هر راس به راس دیگه بریم یعنی مسیر وجود داسته باشه
برای سوال یک هیچ دوری نداریم پس تعداد اجزای همبند میشه صفر
یعنی هیچ زیرمجموعه ای از راسها رو نمیشه انتخاب کرد که بشه از هر راس به راس دیگه بریم اما با اضافه کردن اون یال قرمز میبینین که تعداد دورها میشه سه تا پس سه جز همبند داریم. بنابراین با اضافه شدن یال تعداد اجزا بیشتر شد
دومیم که کلا نشون میده تعداد اجزای همبند میتونه با اضافه شدن یال تغییری نکنه در اینجا قبل و بعد از اضافه کردن یال تعداد اجزا صفر هست ..
منم نفهمیدم اون منظورش چیه از میانگین و O من زدم دوتا گزینه صحیحه
)
ولی سنجشم خوددرگیری داره. هنوز یاد نگرفته دقیق بگه نه مبهم
شاید منظورش در حالت میانگین و بدترین بود که هر دو به نظر ON هست
کی اون سواله NP HARD زد!!
تطابق بشینه منظورشو دقیق نفهمیدم. اگه اینو میفهمیدم منظورش چیه سوالرو جواب داده بودم
تعریف اجزای همبند قوی
اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار از u به v یا از v به u، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار هم از u به v و هم از v به u داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.
اون تعداد min cut در درخت میشه یک یعنی با برداشتن یک یال میشه درخت رو ناهمبند کرد درسته؟
و تعداد انتخاب اون میشه n-1 یال . یعنی یکی از اون n-1 یال رو برداریم .
( هنگ بودم برای سوالای ساده. لگ زمانی اضافه میشه که دو جمله از نظر مرتبه چندجمله ای مثل هم باشن..
