درود و سلام
چون این منبع مهمی هستش تا روزهای باقیمانده کنکور سوالات رو این تیپی مطرح میکنم
حداکثر تعداد یال های یک گراف جهت دار ساده بدون دور با n راس چند تاست ؟
۱) n-1
۲) ۳n
۳) (انتخاب ۲ از n) *
۴) n (n-1)
چرا جوابش میشه گزینه ۳ ؟
سلام
گراف ساده ست. یال چندگانه و طوقه نداریم. پس هر راسی میتونه به بقیه ی رئوس به جز خودش وصل بشه. پس اگه n تا راس باشه، هر کدوم به n-1 راس دیگه وصل میشه. پس شدn در n-1 اما از اونجا که بین دو راس نمیتونه دو تا یال باشه پس این مقدار به ۲ تقسیم میشه.
شاید فک کنیم که خب میشه گراف کامل و دور داره. اما اینطور نیست چون گراف جهت دار هست. طبق کتاب اگه راس ها رو شماره گذاری کنید کافی هست هر راس با شماره ی کمتر به رئوس با شماره ی بیشتر وصل بشه و جهتش به این صورت باشه. کافی هست مثلا با ۴ راس امتحان کنید. اینطوری اصلا توی دور نمیفتیم. پس میشه انتخاب ۲ از n