(۱۶ اسفند ۱۳۹۳ ۰۱:۲۱ ق.ظ)cavalier نوشته شده توسط: فکر کنم شما تعریف همبند قویو رو فراموش کردین. برای اینکه ببینی یه گراف چند جز همبند قوی داره باید نعداد دورها رو بشمرین.
یعنی با انتخاب زیرمجموعه ای از راسها بتونیم از هر راس به راس دیگه بریم یعنی مسیر وجود داسته باشه
برای سوال یک هیچ دوری نداریم پس تعداد اجزای همبند میشه صفر
یعنی هیچ زیرمجموعه ای از راسها رو نمیشه انتخاب کرد که بشه از هر راس به راس دیگه بریم اما با اضافه کردن اون یال قرمز میبینین که تعداد دورها میشه سه تا پس سه جز همبند داریم. بنابراین با اضافه شدن یال تعداد اجزا بیشتر شد
دومیم که کلا نشون میده تعداد اجزای همبند میتونه با اضافه شدن یال تغییری نکنه در اینجا قبل و بعد از اضافه کردن یال تعداد اجزا صفر هست ..
تعریف اجزای همبند قوی
اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار از u به v یا از v به u، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار هم از u به v و هم از v به u داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.
شما به ماکسیمال بودن تعریف توجه نکردین.
یک گراف با n راس و بدون یال، n جزء همبند قوی داره. با نفی مقدم(زیرگراف تک راسی دارای دو راس نیست که به هم وصل باشند یا نباشند!).
یک راه دیگه بررسی الگوریتم پیدا کردن مولفه همبند قوی روی گراف بالا هست: یک بار DFS میزنیم از یک راس دلخواه که فقط خود راس میشه. حالا روی ترانهاده گراف DFS میزنیم(بر اساس ترتیب خروج در DFS قبلی) که اونم میشه همون راس. زیر گرافهای باقی مونده میشه مجموعه مولفه های همبند قوی!
گراف کامل یک جزء همبند قوی داره که اونم خودشه، تعداد دورها برای n های بزرگتر از ۳ مطمئنا بیش از ۱ هست، پس لزوما تعداد دورها مشخص کننده اجزا همبند قوی نیست.
). من نمی دونم چجوری گزینه درست رو رد کردم. فکر کنم تا h(5) رو بررسی کردم فقط
