سوالات گراف

شروع موضوع توسط مهسا.ق ‏2013/3/5 در انجمن المپیاد كامپيوتر

  1. rezaezio

    rezaezio کاربر فوق حرفه ای

    ارسال‌ها:
    1,168
    امتیازات:
    +2,036 / -77
    نام مرکز سمپاد:
    حلّیِ 2
    شهر:
    تهران
    دانشگاه:
    شریف
    رشته دانشگاه:
    نرم افزار
    پاسخ : سوالات گراف

    یک تورنمنت n راسی داریم،‌ یال ها رو با دو رنگ آبی و قرمز رنگ کرده ایم، ثابت کنید یک راس هست که به بقیه رئوس مسیر تکرنگ داره.
     
    • لایک لایک x 1
  2. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    سلام. یه جلسه یه معلم با قدرت انتقال پایین اومد سر کلاس یه سوال گفت (هنوز دقیق نمیدونم منظورش چی بود! - آخر این متن گفتم) که راه حلش این بود (ناقص مونده):

    میومد روی یک گراف همبند چهت دار بدون دور (گفت اسمش DAG) هستش (حداقل۱ راس بدون یال خروجی و حداقل ۱ راس بدون ورودی داره)، dfs می زد (از راسی بدون یال ورودی) و توی ۲ تا آرایه کمکی، زمان اولین بار ورود، و زمان خروج رو برای هر راس ذخیره می کنه. بعدش اگر بیایم آرایه ای که آخرین زمان عبور از یک گراف رو ذخیره کرده، سورت کنیم و راس های اون هم هم زمان swap شن، ترتیبی به دست میاد که یه ویژگی داره (این قسمت رو بد گفت): همه ی یال ها رو به جلو ان! یعنی هیچ یال جهت داری پیدا نمیشه که شماره ی ابتداش از انتهای بیشتر باشه! یعنی درواقع سوال این رو میخواست به راس ها، به ترتیبی شماره بدیم که این ویژگی رو داشته باشه.

    اگر منظور من رو متوجه شدید میشه یه دلیلی درباره ی صحت این الگوریتم بگید؟ سوال معروفی هستش؟ مرجعی برای خوندن کامل این سوال بگید؟ اگر نگرفتید چی میگم، بگید عکس چیزی رو که میگم بدارم!
     
  3. most wanted

    most wanted کاربر نیمه حرفه ای

    ارسال‌ها:
    215
    امتیازات:
    +686 / -25
    نام مرکز سمپاد:
    علامه حلی2
    شهر:
    تهران
    پاسخ : سوالات گراف

    اینی که میگی topological sort میگن بش ، که راس ها رو یه جور میچینه که جهت همه یال ها رو به جلو باشه ، سوالـه خاصی نیست ولی ممکنه تو سوالا دیگه بدرد بخوره ، الگوریتم ٍ چینشٍش هم جز اینی که معلم ٍتون گفته راحت ترش اینه که به ترتیب دلخواهی روی راس ها dfs بزنی ( مثل موقع چک کردن تعداد مولفه ها همبندی مثلا) بعد dfs ٍ هر راس که تموم شد(ینی آخره آخره تابع) بریزیش توی یه stack ، از سر تا ته ٍ این stack میشه همون ترتیبه.شرط این که چنین ترتیبی ام باشه اینه که گراف دور نداشته باشه .
     
  4. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف


    راسی رو به stack اضافه کنیم که ازش شروع کردیم dfs بزنیم؟ یعنی شبه کدش میشه این؟
    کد:
    for (int i=0;i<n;i++)
         if (!mark[i])
         {
              st.push_back(i);
              dfs(i);
         }
    
    ممنون تو ویکیپدیا دارم میخونم دربارش.
     
  5. most wanted

    most wanted کاربر نیمه حرفه ای

    ارسال‌ها:
    215
    امتیازات:
    +686 / -25
    نام مرکز سمپاد:
    علامه حلی2
    شهر:
    تهران
    پاسخ : سوالات گراف

    نه دیگع
    این dfs ٍ؟ :|
    کد:
    dfs(vert){
    for(.....){
    ...
    ..
    }
    st.push(vert);
    }
    این جوری :-"
     
  6. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    نه بابا این که dfs نبود. فرض کردم dfs رو نوشتیم. این کد باید میرفت تو main!
     
  7. most wanted

    most wanted کاربر نیمه حرفه ای

    ارسال‌ها:
    215
    امتیازات:
    +686 / -25
    نام مرکز سمپاد:
    علامه حلی2
    شهر:
    تهران
    پاسخ : سوالات گراف

    آره داخل مِین همونجوری dfs بزن ولی این جوری که من نوشتم بریز تو استک .
     
  8. Dark Eagle

    Dark Eagle کاربر حرفه ای

    ارسال‌ها:
    404
    امتیازات:
    +679 / -34
    نام مرکز سمپاد:
    helli 2
    شهر:
    Tehran
    پاسخ : سوالات گراف

    اینم کدش ... :-"

    کد:
    #include <bits/stdc++.h>
    
    #define mk make_pair
    #define pb push_back
    #define L first
    #define R second
    #define pii pair <int, int>
    
    using namespace std;
    
    const int maxn=1e5+5;
    int n, m, mark[maxn], tmp=1, dir;
    vector <int> scc, v[2][maxn];
    
    void dfs (int x)
    {
    	mark[x]=tmp;
    	for (int i=0;i<v[dir][x].size();i++)
    		if (!mark[v[dir][x][i]]) dfs(v[dir][x][i]);
    	if (!dir)
    		scc.pb(x);
    }
    
    int main ()
    {
    	cin>>n>>m;
    	for (int i=0;i<m;i++){
    		int fi, se;
    		cin>>fi>>se;
    		v[0][fi].pb(se);
    		v[1][se].pb(fi);
    	}
    	
    	for (int i=1;i<=n;i++) if (!mark[i]) dfs(i);
    	memset(mark, 0, sizeof mark), dir=1;
    	for (int i=1;i<=n;i++) if (!mark[i]) dfs(i), tmp++;
    	return 0;
    }
    
     
    • لایک لایک x 2
  9. TheBest444

    TheBest444 کاربر فوق فعال

    ارسال‌ها:
    89
    امتیازات:
    +70 / -4
    نام مرکز سمپاد:
    حلی3_علامه طباطبایی ادونس
    شهر:
    طهران
    رشته دانشگاه:
    فیزیک نوین _ علوم کامپیوتر
    پاسخ : سوالات گراف

    1_با مجموعه راس های V1 تا V6 چند گراف ساده میتوان رسم کرد که به V1 فرد تا یال وصل باشد؟

    2_ 1_با مجموعه راس های V1 تا V6 چند گراف ساده میتوان رسم کرد که به همه ی راس ها ذوج تا یال وصل باشد؟

    3_آقای X و خانم Y به نمایندگی کشور انگلستان در جلسه ای شرکت کرده اند. از 3 کشور دیگر نیز 2 نفر در آن جلسه وجود دارند. پس از دست دادن آنها آقای X از همه ی حاظرین درباره ی تعداد دست دادن هایشان میپرسد.با نهایت تعجب همه ی جواب ها متفاوت بود.آقای X با چند نفر دست داده است؟(تعداد دست دادن ها از 0 تا 6 است)

    پ.ن: خیلی ممنون میشم اگه جواب بدین [-o<
     
  10. علی کوچولو!

    علی کوچولو! کاربر فوق فعال

    ارسال‌ها:
    168
    امتیازات:
    +1,022 / -243
    نام مرکز سمپاد:
    شهید دستغیب 2
    شهر:
    شيراز
    سال فارغ التحصیلی:
    94
    پاسخ : سوالات گراف

    فعلا سوال يك، بقيشم برا بعد:
    جواب نهايي 16*10^2
    توجه كن: انتخاب يك از 5 برا پيدا كردن يه سر يال بعد با5 راس ديگه 10 يال داريم يعد 2 به توان 10 گراف الي اخر... >:D<
     
    • لایک لایک x 2
    • دیسلایک دیسلایک x 1
  11. علی کوچولو!

    علی کوچولو! کاربر فوق فعال

    ارسال‌ها:
    168
    امتیازات:
    +1,022 / -243
    نام مرکز سمپاد:
    شهید دستغیب 2
    شهر:
    شيراز
    سال فارغ التحصیلی:
    94
    پاسخ : سوالات گراف

     
    • لایک لایک x 1
    • دیسلایک دیسلایک x 1
  12. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات گراف

    اولن دقت کنید که دو نفر از یه کشور با هم دست نمیدن!
    ثانین که هیچ کس با خودش دست نمیده!
    ثالثن که هر دو نفر حداکثر یه بار با هم دست میدن!
    (الآن اینا رو جدی گفتم، واسه بامزگی نبود)
    خب با توجه به این حرفا یه گراف ساده ی 4 بخشی درست میکنیم، توی این گراف هر فرد رو با یه راس متناظر میکنیم و هر دو نفر از یک کشور در یک بخش از این گراف قرار دارند.
    اگه دو نفر با هم دست بدن، رئوس متناظرشون رو به هم وصل میکنیم.
    وقتی تعداد دست دادن های همه متفاوت هست، یعنی 7 راس گراف(همه افراد به جز آقای ایکس) درجه ی متفاوتی دارند و همچنین میدونیم که درجه ی هر راس حداقل صفر و حداکثر 6 هست.
    اونی که درجه ش 6 هست، با همه به جز فردِ درجه صفر دست داده، پس دو راس درجه 6 و درجه 0 با هم دست ندادن و در نتیجه متعلق به یه کشورن
    اونی که درجه ش 5 هست، با همه ی افراد باقی مانده به جز فردِ درجه 1 دست داده، پس دو راس درجه 1 و 5 متعلق به یه کشورن
    اونی که درجه ش 4 هست، با همه ی افراد باقی مانده به جز فردِ درجه 2 دست داده، پس دو راس درجه 4 و 2 متغلق به یه کشورن
    این وسط میمونه یه راس با درجه ی 3 که به رئوسی با درجه ی 4 و 5 و 6 یال داره و همون خانم ایگرگ هست
    اگه گراف 4 بخشی رو رسم کنیم، متوجه میشیم که اون یه نفری که باقی مونده(آقای ایکس) هم درجه ش 3 هست، یعنی به همه رئوس با درجه 4 و 5 و 6 وصل شده
    [​IMG]
     
    • لایک لایک x 3
  13. TheBest444

    TheBest444 کاربر فوق فعال

    ارسال‌ها:
    89
    امتیازات:
    +70 / -4
    نام مرکز سمپاد:
    حلی3_علامه طباطبایی ادونس
    شهر:
    طهران
    رشته دانشگاه:
    فیزیک نوین _ علوم کامپیوتر
    پاسخ : سوالات گراف

    سلام. خیلی ممنون از اینکه سوالای قبلیم رو برام توضیح داد و حل کردید. اگه میشه این سوال رو هم برام حل کنید.(اگه دوست داشتین یه توضیحی بدین) ;)

    سوال: گرافی داریم که دنباله درجات راس های آن 8_7_6_5_4_3_3_2_1_1 است. از روی این گراف گرافی جدید میسازیم به این صورت که به ازای هر یال این گراف یک راس قرار میدیم و 2 تا یالی که در گراف اولیه راس مشترک دارند , در گراف جدید به هم وصل میکنیم. گراف جدید چند یال دارد؟
     
  14. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    سلام. ۲ تا سوال از وست دارم. یکیش رو تا حدی خودم تونستم حل کنم اما هنوز مشکل دارم:

    ۱ ۰ فرض کنیم G یک گراف ساده همبند است که کامل نیست. ثابت کنید که هر راس از G متعلق به یک زیرگراف القایی 3 راسی یکریخت یا یک مسیر ۳ راسی می باشد.

    راه حل خودم: یک راس دلخواه v1 را انتخاب می کنیم. چون گراف همبند هستش، درجه ی این راس نمیتونه صفر باشه. پس به v2 یال داره. دوباره چون همبند هستش، v2 به v3 یال داره (مگر اینکه گراف ۲ راسی باشه که نیست). پس یعنی تا الان اثبات کردیم هر زیر گراف ۳ راسی از G، تشکیل یک مسیر میده. یعنی هر زیرگراف القایی ۳ راسی هم از این گراف برداریم، تشکیل یک مسیر میده. چون در انتخاب این ۳ راس، فرض اضافی نکردیم، هر راسی از G متعلق به یک زیرگراف القایی یکریخت با یک مسیر ۳ راسی است.

    این اثبات کلا غلطه؟ بعضی جاهاش غلطه؟ کسی میتونه درستش رو بگه؟

    ۲ - فرض کنیم G یک گراف ساده است که هیچ راسی ازش، درجه ی صفر نداره و هیچ زیرگراف القایی با دو یال ندارد. ثابت کنید G گراف کامل است.

    این سوال آخریه با برهان خلف حل نمیشه؟ درجه ی همه ی راس تو گراف کامل n راسی، برابر n-1 هستش. اما چون اینجا گراف کامل نیست، راسی وجود داره که درجه اش از n-1 کمتر هستش. بعد...
     
    • لایک لایک x 2
  15. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات گراف

    1- این قسمتی که قرمز کردم درسته؟ :-" فرض کن کل گرافت یه مسیر به طول 4 باشه، یعنی 4 تا راس و سه تا یال داشته باشه، توی این گراف هر زیرگراف القایی سه راسی تشکیل مسیر میده؟
    راه حل من باسه این سواله این بود که برهان خلف زدم، با استقرا ثابت کردم اگه حکم برقرار نباشه رئوس اول و آخر هر مسیر از گرافمون به هم وصلن، حالا چون بین هر دو راسی مسیر هست، حتمن گراف کامل میشه که با فرض مسئله تناقض داره. (ولی دیدم بقیه از راهای دیگه هم رفتن، مثلن استقرا روی تعداد رئوس(ولی این راه باگ خورش بالائه :-"))

    2- آره برهان خلفه، ولی راه تو رو دقیق نفهمیدم چیه :-" دو تا راس که به همدیگه وصل نیستن رو درنظر میگیری بعد اثبات میشه (فک کنم راه تو هم همین بود)
     
    • لایک لایک x 2
  16. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    درمورد سوال دوم: برهان خلف می زنیم: فرض می کنم گراف کامل نیست. ۲ تا راس هستند (همون ۲ تایی که به هم وصل نیستند) که درجه اشون نمی تونه بیشتر از n-2 باشه (n تعداد راس هاست). حالا چجوری برهان خلف رو ادامه بدیم که به تناقض برسیم؟ فکر کنم تناقضش اینه: یه زیرگراف القایی با دو یال پیدا میشه...
     
    • لایک لایک x 2
  17. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات گراف

    تناقضش که همینه
    فرض کن راس 1 و 2 به هم وصل نباشن
    درجه ی این دو تا طبق فرض مسئله بزرگتر از صفره
    اگر این دو تا راس یه همسایه مشترک داشته باشن و شماره ی اون همسایه هه 3 باشه، الآن یه زیرگراف القایی دو راسی داریم
    پس راس 1ام و 2ام هر کدوم حداقل یه همسایه دارن که مشترک نیستن!
    فرض کن شماره ی همسایه راس 1ام، 3 باشه و شماره ی همسایه ی راس 2ام 4 باشه
    فرض کردیم راس 2 به راس 3 وصل نیست و راس 1 به راس 4 وصل نیست
    حالا چی میمونه؟ اگر رئوس 3 و 4 به هم وصل باشن، زیرگراف القایی متشکل از رئوس 1 و 3 و 4 دو یال داره
    وگرنه زیر گراف القایی متشکل از رئوس 1 و 2 و 3 و 4 زیرگرافی القایی با دو یال هستش
    تناقض!
    پس هر دو راسی به همدیگه وصل هستن

    +این عکسو هم ببین :-"
    [​IMG]
     
    • لایک لایک x 1
  18. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف


    2 قسمتشو نفهمیدم. همونایی که قرمز شده اند.
    1 - چرا و چه زمانی فرض کردیم 1 به 4 وصل نیست و 2 به 3 وصل نیست؟
    2 - 1 و 2 و 3 و 4 چجوری میشه یه زیرگراف القایی؟ دقیقا کدوم راس ها تو این زیرگراف القایی به هم وصل هستند؟

    *ویرایش: مشکل ام حل شد!!! ممنون.
     
  19. daneshvar.amrollahi

    daneshvar.amrollahi کاربر حرفه ای

    ارسال‌ها:
    327
    امتیازات:
    +133 / -4
    نام مرکز سمپاد:
    راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
    شهر:
    تهران
    سال فارغ التحصیلی:
    1397
    پاسخ : سوالات گراف

    سوال اول، راهی به جز استفرا نداره؟ چون باید بشه یا همون اطلاعات بخش 1 فصل 1 وست بشه این ها رو جواب داد :D

    دقیقا روی چی باید استفرا زد؟ استفرای ضعیف؟ فرض استفرا چیه؟
     
  20. Anita H

    Anita H کاربر حرفه ای

    ارسال‌ها:
    568
    امتیازات:
    +2,909 / -42
    نام مرکز سمپاد:
    Hell(i) 2
    شهر:
    تهران
    سال فارغ التحصیلی:
    96
    دانشگاه:
    شریف
    رشته دانشگاه:
    مهندسی کامپیوتر
    پاسخ : سوالات گراف

    جواب خط اولت رو نمیدونم
    ولی برای خط دومت روی طول مسیر استقرای ضعیف بزن
     
    • لایک لایک x 1