اثبات همبند بودن مکمل گراف ناهمبند
پیدا کردن مولفه های قویا همبند گراف جهت دار
یافتن کوتاه ترین دور در گراف ساده
جزوه ی برنامه نویسی قسمت (گراف)
آشنایی مهمان‌ها پس از $n$ مهمانی
یافتن موقعیت ایستگاه های قطار با پرسیدن فاصله آنها
پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا
جیان جیا و می یو یک بازی انجام میدهند: ابتدا آنها یک عدد طبیعی $n$ انتخاب میکنند و سپس جیان جیا یک کشور با $n$ شهر را در نظر میگیرد که بین بعضی از زوج شهرهای آن پرواز دوطرفه وجود دارد. می یو در $r=n(n-1)/2$ مرحله، هر بار یک زوج شهر را انتخاب میکند و از جیان جیا میپرسد آیا بین آن دو شهر پرواز مستقیم وجود دارد یا خیر، جیان جیا باید بلافاصله به او پاسخ بله و خیر دهد.
هدف می یو آن است که در کمترین زمان ممکن متوجه شود که آیا شبکه پروازهای این کشور همبند است یا خیر. به عبارت دیگر آیا میتوان بین هر دو شهر از این کشور با چند پرواز مسافرت کرد؟ اگر می یو بتواند قبل از پرسیدن $r$ سوال اطمینان کسب کند که این شبکه همبند است یا خیر برنده میشود، و اگر برای فهمیدن این موضوع همه $r$ پرسش لازم باشد جیان جیا برنده میشود.
جیان جیا میتواند در طول بازی شبکه را ترسیم کند و هر سوال می یو را بر اساس سوالها و پاسخهای قبلی، پاسخ دهد. الگوریتمی ارایه دهید که به جیان جیا کمک کند تا برنده بازی شود.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:37:50 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:05:51 -0500 امیر شکریاین ایده ی من :
اگه گراف مسیر n راسی داشته باشیم ، درجه ی n-2 راس 2 خواهد بود و درجه ی دو راس یک خواهد بود.
حال درباره ی هر راسی میتوان n_1 سوال پرسید که ما تا جایی پاسخ خیر میدهیم که که امکان همبند بودن و گراف مسیر بودن گراف از بین نرود و هر کجا دیدیم که اگر پاسخ خیر بدهیم گراف دیگر نمیتواند همبند و یا مسیر باشد ، پاسخ بله میدهیم.(همان طور که مشخص است ،دلتای بزرگ برابر دو است و دلتای کوچک بسته به سوال آخر ممکن است یک و یا صفر باشد)
در این صورت همیشه همبند بودن گراف به سوال آخر بستگی پیدا می کند و پس از پرسیدن سوال r ، دو حالت ممکن است پیش بیاید:
1.یک گراف مسیر(همبند) به وجود بیاید.
2.گراف همیند نباشد.
ببخشید اگه بد توضیح دادم...یه مقدار پیچیده شد اما کد زدنش خیلی سخت نیست.
موفق باشید.
