المپیاد سوالات گراف

[مهسا.ق]

خوب کلا این که همه می دونیم که اصلی ترین کتاب برای مبحث گرافی که تو المپیاد مطرح می شه west هست
خوب کلا با هدف پویایی انجمن و خوندن west دور هم از صفر این تاپیک رو ایجاد می کنیم
تا مرجعی برای حل سوال های west باشه.
کلا روند این طوریه که از ۱-۱ که خوب خیلی آسون و ایناس شرو می کنیمو سوال ها و قضیه ها رو با هم بررسی می کنیم
شاید اولش براتون خسته کننده باشه ولی کمکم که بره جلو می بینید چه قضیه و سوال های پیش پا افتاده ای رو اثبات کاملشو دقیق یادتون نبود و یه دوره ای هم می شه.
اگه همکاری کنید با سرعت خوبی می شه از قسمت خسته کننده و آسون اولش جلو رفت.
نظرتون چیه؟
- لطفا هر سوالی رو که حل می کنید ترجمه سوال بعدی رو بذارید اگه می تونید

- می دونم سوالا آسونن اولش و براتون سخته سوالای آسون حل کنید ولی لطفا به ترتیب پیش برید یه کم همت کنید می رسیم به جاهای خوبش هم

۱-۱-۱) تعیین کنید کدام گراف ها ی کامل ۲ بخشی، گراف کامل نیز هستند؟

 

[most wanted]

پاسخ : سوالات گراف

س1-1-2) برای مسیر با 3راس همه ی ماتریس های مجاورت و وقوع را بنویسید. همچنین برای یکی از مسیر های با 6 راس و یکی از دور ها با 6 راس ماتریس مجاورت بنویسید.

ج1-1-1)
گراف با دو راس هر بخش یک راس

 

[meli]

پاسخ : سوالات گراف

سوالِ یک:

شرط لازم کامل دو بخشی بودن اینه که هر بخش حداقل یک راس داشته باشه و تمام رئوس این دو بخش بهم یال داشته باشن.

شرطِ لازم کامل بودنشم اینه که تو هر بخش حداکثر یک راس باشه. چون اگه بیشتر از یک راس باشه چون این راس ها تو یه بخشن به هم یال ندارن و کامل بودنِ گرافمون نقض میشه.

در نتیجه این اتفاق تنها در گراف های دو بخشی ای میفته که هر بخش دقیقا یک راس داره که به راس بخش دیگر هم متصل شده.

اینایی که گفتم یکم شهودیه بیشتر اثباتِ ریاضی ترشم قک کنم بشه نوشت

+ عه ندیدم بالایی هم ویرایش کرده جوابُ داده

 

[مهسا.ق]

پاسخ : سوالات گراف

ج۲)
چیزه راستش قسمت اول حس خوبی ندارم چون که یه جوریه ینی گفته همه ولی یه حالت بیشتر نیس چون هر گراف ۳ راسی که دور نداره بکشی و مسیر داره با این یه ریختن! دور هم از قسمت دوم فهمیدم منظورش اینه. کلا حسم اینه که سوال رو از مسخرگیش ممی تونم گاف داده باشم
مجاورت
۰۱۱
۱۰۰
۱۰۰
وقوع
۱۱۰
۱۰۱

مسیر با ۶ راس
۱۲۳۴۵۶
۰۱۰۰۰۰
۱۰۱۰۰۰
۰۱۰۱۰۰
۰۰۱۰۱۰
۰۰۰۱۰۱
۰۰۰۰۱۰
دور با ۶ راس
۰۱۰۰۰۱
۱۰۱۰۰۰
۰۱۰۱۰۰
۰۰۱۰۱۰
۰۰۰۱۰۱
۱۰۰۰۱۰

۳.۱.۱)ماتریس مجاورت km,n را توسط بلوک هایی توصیف کنید که تمام درایه های هر بلوک با هم برابرند.

 

[most wanted]

پاسخ : سوالات گراف

ج1-1-3) فک کنم توضیحی بگم بهتره
خوب راس های بخشn تایی رو از یک تا n و بخش بعدی رو از n+1تاm شماره گذاری میکنیم.
راس های بخش اول به همه ی بخش دوم وصل اند و برعکس
پس واضحه که یه مربع n*n داریم که همه درایه هاش صفره چون هیچکدام از بخش اول بهم وصل نیستن
2تا هم مستطیل n*m که سمت راستو پایین مربع چون همه ی بخش اول به بخش دوم یال دارن و بر عکس
و در آخر هم یه مربع گوشه پایین راست که نشانه وصل نبودن راس های بخش دوم به همه .

1-1-4) نشان دهید دو گراف یک ریخت هستند اگر و تنها اگر مکمل آنها یریخت باشند.

 

[kia.celever]

پاسخ : سوالات گراف

1-1-4) نشان دهید دو گراف یک ریخت هستند اگر و تنها اگر مکمل آنها یریخت باشند.

فرض کنید گراف G و H یکریختن. یعنی تابع یک به یک

وجود دارد به طوری که

ثابت می کنیم تابع f برای مکمل G و مکمل H هم صدق می کنه.

برای ثابت کردن عکس قضیه هم از می شه از این حکم استفاده کرد. چون مکمل مکمل یه گراف خود گرافه!

1-1-5) ثابت یا رد کنید: اگر هر راس گراف ساده G درجه ی 2 داشته باشد، آنگاه G یک دور است.

پ.ن. نمی شه فقط سوالایی رو که به نظر نکته دارن بگیم؟ این سوالا رو هرکسی خودش تو خونه می تونه حل کنه. (و راه حل همه هم یکیه!)

 

[عمو ژپتو]

پاسخ : سوالات گراف

1-1-5) ثابت یا رد کنید: اگر هر راس گراف ساده G درجه ی 2 داشته باشد، آنگاه G یک دور است.

پ.ن. نمی شه فقط سوالایی رو که به نظر نکته دارن بگیم؟ این سوالا رو هرکسی خودش تو خونه می تونه حل کنه. (و راه حل همه هم یکیه!)

من یه راه حل میگم نظرتون رو راجبش بگید
خوب ابنتدا ثابت میکنیم که G بک دور دارد :
بلند ترین مسیر در G را در نظر میگیریم راس انتهایی آن در جه اش دو است پس یک یال به داخل مسیر دارد آن یال را در نظر میگیریم و دورمان به صورت واضح مشخص میشود(به دلیل نبودن شکل عذر خواهی میشود )
بعد من الان به یه چیزی پی بردم اگر گراف همبند نباشه میتونه چند تا مولفه دور باشه
فرض میکنیم گراف همبند باشد
میخواهیم ثابت کنیم اون یال که گفتم راس ابتدا و انتهای دور رو به هم وصل میکنه . برهان خلف :فرض میکنیم راس انتها را به یکی از رئوس میانی دور وصل کند آن زمان در جه آن راس بزرگتر از 2 میشود که خلاف فرض مسئله است پس فرض خلف باطل و فرض مسئله ثابت میشود
حال ثابت میکنیم تمامی رئوس گراف (در صورت همبند بودن) در این دور هستند
برهان خلف :فرض میکنیم راسی مانند uدر دور وجود نداشته باشد و با توجه به همبند بودن گراف با مسیری به راس v که در دور است میآید
می دانیم که تمامی راس ها داخل دور دارای درجه 2هستند (بدیهیه جدا ) پس راس v دارای درجه ای بیشتر از 2 میشود پس فرض خلف باطل و فرض مسئئله ثابت میشود .
درنتیجه گراف حاصل یک دور است #.

 

[most wanted]

پاسخ : سوالات گراف

1-1-6) آیا گراف شکل زیر قابل تجزیه به مسیر هایی به طول 4 است؟

پ.ن:سوال ه بعد رو هم بزارید موقع جواب

 

[عمو ژپتو]

پاسخ : سوالات گراف

1-1-6) آیا گراف شکل زیر قابل تجزیه به مسیر هایی به طول 4 است؟

خیر
زیرا در هر مسیر به طول 4 2 راس زوج و دوراس با درجه فرد دارد اما در سکل مقابل 6 راس درجه فرد دارد که چنین چیزی امکان پذیر نیست

 

[most wanted]

پاسخ : سوالات گراف

1-1-7) ثابت کنید اگر گرافی بیش از 6 راس درجه فرد داشته باشد نمیتوان آن را به سه مسیر تجزیه کرد.
پ.ن) دقیقا م3 سواله قبله حل نمیشه پس
1-1-8) نشان دهید! گراف زیر به p4 وk1,3 تجزیه پذیر است.

پ.ن: یکیم سوال بزاره ما بجوابیم

 

[عمو ژپتو]

پاسخ : سوالات گراف

1-1-7) ثابت کنید اگر گرافی بیش از 6 راس درجه فرد داشته باشد نمیتوان آن را به سه مسیر تجزیه کرد.
پ.ن) دقیقا م3 سواله قبله حل نمیشه پس
1-1-8) نشان دهید! گراف زیر به p4 وk1,3 تجزیه پذیر است.

پ.ن: یکیم سوال بزاره ما بجوابیم

اینجور که مشخص سوال رو اشتباه خوندم
آقا مثل سوال قبل حل مشه ها
خوب در هر مسیر دو راس درجه فرد داریم و باقی راس ها دارای درجه زوجی هستند .
پس با 3 مسیر حداکثر میتوان 6 تا راس درجه فرد ایجاد کرد و باقی راس ها زوج اند
میگم سوال برام پ.خ کن من میذارم خوب
k1,39 ?????? واقعا میشه ؟؟ اینقدر راس نداریما

 

[most wanted]

پاسخ : سوالات گراف

مسیره که با استدلال مشابه نمیشه ولی اون یکی :

1-1-9) نشان دهید گراف زیر با متمم گراف سوال قبل یریخت است.


پ.ن: 39 نیست اون واوه نه 9

 

[عمو ژپتو]

پاسخ : سوالات گراف

تو این سوال قبل P4 ش کوو ؟؟

 

[most wanted]

پاسخ : سوالات گراف

تو این سوال قبل P4 ش کوو ؟؟

مسیره که با استدلال مشابه نمیشه ولی اون یکی:

منظورم استدلال سوال قبل که تو حل کرده بودی بود.

 

[عمو ژپتو]

پاسخ : سوالات گراف

منظورم استدلال سوال قبل که تو حل کرده بودی بود.

نفهمیدم
من احساس کرده بودم با استفاده از هر دوشون باید شکلرو بسازیم

 

[مهسا.ق]

پاسخ : سوالات گراف

خیر
زیرا در هر مسیر به طول 4 2 راس زوج و دوراس با درجه فرد دارد اما در سکل مقابل 6 راس درجه فرد دارد که چنین چیزی امکان پذیر نیست

دروغه می شه این کارو کرد
اینم شکلش:

حتما خودتون دلیلو متوجه شدید که چرا استدلالتون غلطه نه؟

1-1-7) ثابت کنید اگر گرافی بیش از 6 راس درجه فرد داشته باشد نمیتوان آن را به سه مسیر تجزیه کرد.
پ.ن) دقیقا م3 سواله قبله حل نمیشه پس

سوال قبل استدلال اشتباه بود کلا! ولی این جا می شه گفت هر مسیر حداکثر 2 راس با درجه فرد می پوشونن پس بیشتر از 6 راس درجه فرد نمی شه ولی استدلال سوال قبل به کل اشتباهه که شما روش حرف زدید استدلال سوال قبل حتی اگه درست بود که نیست اثبات می کرد با کمتر از 6 راس نمی شه و می دونیم که دروغه

مسیره که با استدلال مشابه نمیشه ولی اون یکی :

دروغه این هم برادر من! سوال می گه ثابت کنید می شه شما می گید نمی شه؟


خلاصه ی کلام این که این جا قراره یه مرجع خوب برامون بشه رو چیزایی که می گیم دقت کنیم بقیه هم بخونن بقیه سوال ها رو ممکنه غلط باشه حتی همین سوال های خیلی ساده!

پ.ن: شکلام خیلی تمیزه می دونم نیاز به یادآوری نیست

 

[مهسا.ق]

پاسخ : سوالات گراف

1-1-9) نشان دهید گراف زیر با متمم گراف سوال قبل یریخت است.

شکله گنده شد یه کم ولی خوبه
سمت راستیه گرافیه که قراره ثابت کنیم با مکمل سمت چپیه یکریخته!
در واقع جوری نام گذاری کردم راس ها رو که اگه فقط اگه رو گراف سمت راستی بین 2 راس A , B یال نباشه رو گراف سمت چپی بین A,B یال خواهد بود و بلعکس!
این طوری می شه ادعا کرد قرینه ی سمت چپی با گراف سمت راستی یکریخته

1.1.10) ثابت یا رد کنید: مکمل یک گراف ساده ی ناهمبند ، گرافی همبند است.

 

[A.MR.P]

پاسخ : سوالات گراف

1.1.10) ثابت یا رد کنید: مکمل یک گراف ساده ی ناهمبند ، گرافی همبند است.

گراف اولیه ناهمبند است ،مولّفه های آن را در نظر بگیرید، همه یِ این مولفه ها در گراف مکمل به هم وصل اند،پس اگر مولفه ها را راس در نظر بگیریم،گراف همبند شده است،پس می ماند راس های درون هر مولفه: هر راس هر مولفه را که در نظر بگیریم این چنین است: آن راس به همه یِ راس های همه یِ مولفه ها(به جز مولفه خودش) وصل است از آنجا که مولفه ها همبند بودند این راس هم به همبندی آنها اضافه می شود.
پس ثابت شد دیگه

 

[مهسا.ق]

پاسخ : سوالات گراف

گراف اولیه ناهمبند است ،مولّفه های آن را در نظر بگیرید، همه یِ این مولفه ها در گراف مکمل به هم وصل اند،پس اگر مولفه ها را راس در نظر بگیریم،گراف همبند شده است،پس می ماند راس های درون هر مولفه: هر راس هر مولفه را که در نظر بگیریم این چنین است: آن راس به همه یِ راس های همه یِ مولفه ها(به جز مولفه خودش) وصل است از آنجا که مولفه ها همبند بودند این راس هم به همبندی آنها اضافه می شود.
پس ثابت شد دیگه

بابا جدی اگه امکان دارید سوال بعد رو هم ترجمشو بذارید!
سوال بعد:
1.1.11) اندازه بزرگ ترین خوشه و بزرگ ترین مجموعه مستقل را در گراف زیر تعیین کنید

 

[A.MR.P]

پاسخ : سوالات گراف

1.1.11) اندازه بزرگ ترین خوشه و بزرگ ترین مجموعه مستقل را در گراف زیر تعیین کنید

مجموعه مستقل: دو راس بالا و پایین قطعا در مجموعه نیستند چون به همه رئوس یال دارند ،پس باید از سه راس وسط انتخاب کنیم،در آن ها هم واضح است که بیش از دوتا از آنها را نمی توان انتخاب کرد،چون اگر 3 تا را ورداریم یکی از آنها از 2 تای وسط تر بوده که به دوتا از وسطی ها ( نه خیلی ها ) یال دارد که تناقض است . پس همان دوتای بالا و پایین و دوتا از وسطی ها یکی در میان جواب است.
خوشه ماکسیمال: دو راس بالا و پایین در خوشه هستند چون اگر نباشند می توانیم آن ها را اضافه کنیم ( چون به همه رئوس یال دارند) . وبا ماکسیمال بودن در تناقض است
از رئوس وسطی هم حداکثر دوتا را میتوان برداشت چون اگر سه تا بر داریم یکی از کناری ها است که درجه 1 در بین وسطی ها دارند که تناقض است . پس دوتای بالایی و پایینی و هر کدام از متوالی های وسط جواب است.
1.1.12) نشان دهید گراف پترسن دو بخشی است ، سایز بزرگترین مجموعه مستقل را پیدا کنید.