از دوستان کسی میتونه لطف کنه و این سوال رو برام توضیح بده؟
(۲۶ اردیبهشت ۱۳۹۴ ۰۸:۳۲ ب.ظ)setarehfb نوشته شده توسط: از دوستان کسی میتونه لطف کنه و این سوال رو برام توضیح بده؟
سوالش کو
سوال ۴۶ ای تی ۹۴'
چندتا از گزاره های زیر درباره همبند قوی یگ گراف جهتدار درست است؟؟ اگر g دور نداشته باشد تعداد اجزای همبند قوی ان برابرv است
اگر یک یال از g حذف شود، تعداد اجزای همبند قوی g حد اکثر دو واحد کم می شود
از دوستان کی میتونه راهنماییم کنه؟؟؟؟؟؟؟؟؟؟؟?؟؟؟؟؟؟
گزینه ۱ صحیح است: نداشتن دور در گراف جهتدار : هیچ مسیر رفت و برگشتی نداریم بین رئوس.
پس هر راس یک جزء همبند قوی است. پس n جزء همبند قوی داریم.
گزینه ۲ هم صحیح است.
حذف یال نمیتواند باعث کاهش اجزای قویا همبند باشد. حذف یالها فقط میتواند باعث حذف دورها شود و در نتیجه تعداد اجزای قویا همبند را افزایش میدهد یا تعداد اجزای قویا همبند ثابت می ماند.
همبند قوی تعریفش این بود: از راس اول ب راس دوم و از راس دوم ب راس اول مسیر باشد. پس چطور همبند قوی میشه؟
توجه داشته باشید که هر راس به تنهایی یه جز همبند قوی حساب میشه مگه اینکه زیرمجموعه یه جزء همبند قویتر باشه، اوون وقت اون مجموعه بزگتر رو به عنوان یه جز همبند قوی میشناسیم.
متوجه نشدم!
اوون جایی رو که متوجه نشدید علامت بزنید یا بگید با این قسمت توضیحات مشکل دارم
هر راس چطور میتونه یک جزع همبند قوی باشه؟؟
شما یه گراف تک راسی رو در نظر بگیرید. این گراف یه جزء همبند قوی داره: اوون جزء همبند قوی فقط یه راس داره. چون یالی نداره تا بخواد شرایط همبند بودن رو براش تست کنه.
ضمنا میدونیم که یه گراف با یه راس همبند حساب میشه. اینطوری فرض کنید که یه راس از خودش قابله دسترسه.