سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:55:49 -0500 امیر شکریآمار پرسش:
- پرسیده شده: 2016-02-07 06:20:09 -0500
- مشاهده شده: 368 بار
- بروز شده: 2016-02-07 20:16:46 -0500
پرسش‌های مشابه:
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یالهای گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
گرافی جهت دار وقویا همبند با$ 2*n-1$ یال و$ n $ راس داریم
گرافی جهت دار وقویا همبند با$ 2*n-1$ یال و$ n $ راس داریم ثابت کنید یالی وجود دارد که با حذف آن گراف قویا همبند خواهد ماند
2016-02-07 06:20:09 -0500
حمیدرضاه 2979 ● 20 ● 26 ● 52
نظرات
1 پاسخ
راس v رو در نظر میگیریم.
خوب اگه گرافی قویا همبند باشه :
میدونیم شرط قویا همبند بودن اینه که از با شروع حرکت از v بتوان همه ی راسها رو مشاهده کرد و سپس با معکوس کردن گراف و دوباره حرکت از v بتوان همه راسها رو مشاهده کرد و بالعکس.
یعنی حالا که گرافمون قویا همبنده میتونیم از v به همه جا بریم(توی خودش و معکوسش)
حالا اگه ما بیایم دو تا درخت به شیوه های گفته شده تشکیل بدیم(۲ تا dfs روی خود گراف و معکوسش!!) هر درخت n-1 یال خواهد داشت و در صورتی که درخت دوم با درخت اول هیچ اشتراکی نداشته باشد(بدترین حالت ممکن!!) مجموعا گرافی با n+n-2 یال خواهیم داشت که میفهمیم یدونه از یالهای گراف اولیه اضافیه.
ممنون
2016-02-07 20:13:47 -0500
کنکوری 1683 ● 13 ● 27 ● 40
نظرات