سوالات گراف

[rezaezio]

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

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


پاسخ :
گراف پترسن دو بخشی نیست ، چون دور با طول فرد داره

بزرگترین زیر مجموعه مستقل گراف پترسن 4 عضو داره
اثبات اینکه از 4 بیشتر نمیشه :
اگر راس سبز در شکل زیر در مجموعه مستقل باشه ؛ آنگاه بقیه عضو های مجموعه باید از بین عضو های درون دایره های قرمز در شکل زیر انتخاب بشن و چون از هر دایره حداکثر 1 عضو را می توان انتخاب کرد ، 4=3+1 عضو انتخاب شده است.
اگر راس سبز در مجموعه مستقل نیاید ؛ آنگاه دوری به طول 9 داریم که بدیهی است از دوری به طول 9 برای قرار گرفتن در مجموعه مستقل حداکثر میتوان 4 عضو را انتخاب کرد.

شکل زیر هم مثالی برای 4 راس

1.1.13)نشان دهید که گراف k مکعب دو بخشی است .


پاسخ :
ثابت می کتم این گراف دور به طول فرد نداره و از این حرف میشه نتیجه گرفت که دو بخشیه
در گراف k مکعب هر راس با راس های مجاورش از نظر زوجیت تعداد یک ها متفاوت است پس پس اگر دور با شروع از راس A باشد چون پایانش هم راس A هست ؛ پس باید زوج بار تغییر زوجیت بدیم ، پس طول دور ما زوج است. (می دونم که بد توضیح دادم )




1.1.14) ثابت کنید که با حذف کردن مربع های گوشه و رو به رو ( به نظرم منظورش مربع گوشه بالا و چپ و مربع گوشه پایین و راست هست ) از یک جدول شطرنجی 8 در 8 ، تخته ای به دست می آید که نمی توان آن را با دومینو پوشاند.این مساله را با استفاده از گراف های دو بخشی تعمیم دهید.


پاسخ :
نمیتوان زیرا 30 خانه با رنگ سیاه و 32 مهره با رنگ سفید داریم و هر دومینو یک خانه سفید و یک خانه سیاه را می پوشاند.

در حالت کلی اگر با حذف تعدادی خانه بتوان جدول را با دومینو پر کرد ؛ آنگاه تعداد خانه های سیاه حذف شده برابر با تعداد خانه های سفید حذف شده است.




1.1.15) چهار خانواده رو به رو در گراف را در نظر بگیرید. A = { مسیر ها } , B = { دور ها } , C = { خوشه ها } , D = { گراف های دو بخشی } . برای هر جفت از این خانواده ها ، کلاس های یکریختی که هر دو خانواده را شامل می شوند را تعیین کنید. ( خودم هم نفهمیدم )



1.1.16)یکریخت بودن شکل های زیر را بررسی کنید.

پاسخ :
یکریخت نیستند زیرا اگر گراف های مکمل آن ها را در نظر بگیریم یکی از دوری به طول 8 تشکیل شده است و دیگری از دو دور به طول 4





1.1.17)تعداد زده های یکریختی گرافی با 7 راس که درجه هر راس آن 4 است را بدست آورید.


پاسخ :
گراف مکمل این گراف را در نظر می گیریم ، چون درجه هر راس در این جا 2 است پس حتما از دور تشکیل شده است و با بررسی می فهمیم که یا دوری به طول 7 است و یا اینکه دو دور به طول های 3 و 4





1.1.18) بررسی کنید که کدامین جفت های زیر یکریخت هستند.

پاسخ :
سمت راست ترین گراف دو بخشی نیست چون دور به طول فرد داره ولی گراف وسط و گراف سمت چپ یکریخت هستند .

1.1.19) بررسی کنید که کدامین جفت های زیر یکریخت هستند.

پاسخ :
گراف سمت چپ دو بخشی است ولی گراف های وسط و گراف سمت راست دور به طول فرد دارند.
گراف سمت راست و وسط با هم یکریخت هستند.

1.1.20) بررسی کنید که کدامین جفت های زیر یکریخت هستند.

پاسخ :
گراف وسط دور با طول فرد داره پس دوبخشی نیست ولی گراف های راست و چپ دو بخشی هستند.
همچنین گراف های چپ و وسط یکریخت هستند.

1.1.21) دو بخشی بودن و یک ریخت بودن گراف های زیر را بررسی کنید.

1.1.22) تعیین کنید کدام یک از جفت های زیر یکریخت هستند ، اثباتی ارائه دهید که در آن کمترین تعداد ممکن آزمایش را انجام داده باشید.

پاسخ :
گراف مکمل هر کدام از 5 گراف را رسم می کنیم ، گراف ها را از چپ به راست با شماره های 1 تا 5 نامگذاری می کنیم ،
متمم گراف های 1 و 2 و 5 دوری به طول 7 هستند ولی مکمل گراف های 3 و 4 دو دور به طول های 3 و 4 هستند. پس گراف های 1 و 2 و 5 با هم پیکریخت هستند و گراف های 3 و 4 با هم.



1.1.23 ) در هر کلاس رده زیر ؛ کوچک ترین n را چنان بیابید که حداقل 2 گراف با مجموعه درجات یکسان با n راس داشته باشیم که یکریخت نباشند.
1- همه ی گراف ها 2- گراف های بدون طوقه ( لوپ ) 3- گراف های ساده

پ.ن) در ضمن اینا سوال های آسونش بودن ، واسه اینکه این جا مرجع هست جوابا رو پشت هم نوشتم تا به سوالات نسبتا جون دارش برسیم !
پ.ن 2) به درخواست تعداد زیادی از کاربران سایت از جمله علیرضا پاسخ ها رو سفید کردم که ملت خودشون فکر کنند ! در ضمن عکس ها سفید نمیشن ملت از جمله علیرضا مواظب چشماشون باشند

 

[عمو ژپتو]

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

ابتدا رئوس گراف kمکعب را به دنباله های باینری به طول k تبدیل میکنیم
حال بر روی k استقرا میزنیم
سمت چپ ترین رقم را در نظر نمیگیریم
طبق فرض استقرا گراف حاصل (دنباله های حاصل ) را میتوان دوبخشی کرد
حال ابتدای همه ی این دنباله ها 0 میگذاریم و دنباله متناظر آنها(همان دنباله قبلی با سمت چپ ترین رقم 1) را در بخش مقابل می اندازیم
گراف حاصل نیز 2 بخشی است
(آقا میدونیم خیلی بد گفتم یه نفر دیگه هم بگه بد نیست )

 

[A.MR.P]

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

1.1.23 ) در هر کلاس رده زیر ؛ کوچک ترین n را چنان بیابید که حداقل 2 گراف با مجموعه درجات یکسان با n راس داشته باشیم که یکریخت نباشند.
1- همه ی گراف ها 2- گراف های بدون طوقه ( لوپ ) 3- گراف های ساده

با توجه به راهنمایی ـه سوال که گفته سه جواب دنباله یِ ناکاهشی میسازن تقریبا بدیهی میشه اثباتِش.

1.1.24)
فک کنم با ربون بی زبونی می خواست ـه بگه : ثابت کنید گراف های زیر یریخت ان!


پ.ن. : یاد بگیرید اینجوری اَکس میزارن
سوال ـو چرا ناقص میزاری؟ هینت داره سوال


@

 

[rezaezio]

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

راهنماییش بدیهی بود

1.1.24)
فک کنم با ربون بی زبونی می خواست ـه بگه : ثابت کنید گراف های زیر یریخت ان!





1.1.25) ثابت کنید گراف پترسن ؛ دور به طول 7 ندارد .



پ.ن : با تشکر از آموزشتون
سوال ـو چرا ناقص میزاری ؟ هینت داره سوال

 

[kia.celever]

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

1.1.25) ثابت کنید گراف پترسن ؛ دور به طول 7 ندارد .

برهان خلف می زنیم.
فرض کنید C یه دور به طول 7 تو گراف پترسن باشه. هیچ دو رأسی تو C به هم یال ندارن چون اگه یال داشتن یه دور طول حداقل 4 ایجاد می شه ولی کمر گراف پترسن 5 ـه. چون گراف پترسن 10 تا رأس داره پس 3 تا رأس بیرون دور وجود دارن. چون این گراف 3 منتظمه از هر رأس تو C یه یال به V - C وجود داره. طبق اصل لانه کبوتری یه رأس v وجود داره که حداقل 3 تا از این 7 یال که از دور خارج می شن به v وصلن. بین 3 تا رأس از C هم حداقل 2 رأس وجود دارن که یا همسایه همن یا یه همسایه مشترک دارن. این 2 تا رأس با v یه دور 3 یا 4 می سازن که تناقضه.

1.1.26) فرض کنید G یه گراف k منتظم با کمر 4 ـه. ثابت کنید G حداقل 2k تا رأس داره.

 

[rezaezio]

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

1.1.26) فرض کنید G یه گراف k منتظم با کمر 4 ـه. ثابت کنید G حداقل 2k تا رأس داره.


راس دلخواه X را در نظر بگیرید ، چون گراف k منتظم هست ، پس k راس به X وصل هستند. این k راس را مجموعه A می نامیم.
واضح است که بین اعضای مجموعه A یالی نیست چون اگه باشه دور به طول 3 پیدا میشه ؛ و چون گراف k منتظم است هر کدام از راس های مجموعه A به k راس بیرون مجموعه A وصل است ؛ پس حداقل k راس بیرون A داریم ; k+k=2k

با 2k راس هم فقط یه گراف دو بخشی کامل می تونیم بسازیم ، که k راس یک طرف و k راس طرفی دیگر باشند.

1.1.27) فرض کنید G یه گراف باشه که با کمر 5 و درجه هر راس حداقل k باشه ؛ ثابت کنید که G حداقل K^2+1 راس داره !


راس دلخواه X را در نظر بگیرید ، چون گراف k منتظم هست پس k راس به X وصل هستند ، این k راس را مجموعه A می نامیم.
واضح است که بین اعضای مجموعه A هم یالی نیست چون اگه باشه دور به طول 3 پیدا می شه ؛ همچنین هیچ کدام از راس های مجموعه A به جز راس X همسایه مشترکی ندارند پس k-1 همسایه دیگرشان متفاوت است پس حداقل k^2-k راس به جز مجموعه A و راس X داریم ؛ که همراه با مجموعه A و راس X می شود k^2+1 راس !


1.1.28) فرض کنید O k گرافی باشه که هر کدوم از راس هاش زیر مجموعه ای k عضوی از مجموعه { 1 , 2 , . . . , 2k+1 } هستند . دو راس همسایه هستند فقط اگر جدا از هم باشند ( اشتراک نداشته باشند ) ! ثابت کنید اگر k>=3 باشه ، آنگاه کمر گراف 6 است .

 

[مهسا.ق]

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

1.1.28
چیزه یه کم حالت بندی کثیفیه ولی خوب دیگه حالا
می یایم اول می خوایم بگیم دور کم تری از 6 نیست!
هر دسته که نام می بریم به عنوان یک راس در نظر می گیریم و هر دو راسی که پشت هم می نویسیم یعنی به هم یال دارند پس عضو مشترک ندارند
a1,1,a1,2,...,a1,kدسته ی 1
a2,1,a2,2,...,a2,kدسته ی 2
a3

دسته ی 1
دسته ی 2
a3, همه ی دسته ی 1 به جز a1,i(به اولین راس وصل نمی شوند چون همه ی دسته ی 1 به جز یکی را دارند پس دور به طول 3 نداریم)
a1,i, همه ی دسته ی 2 به جز a2,j(به اولین راس نمی تواند وصل شود چون یکی از دسته ی 1 را دارد پس دور به طول 4 نداریم)
این جا 3 حالت داریم برا پنج امین راس که جدا بررسی می کنیم
1) a2,j, همه دسته ی 1 به جز a1,i(به اولین راس وصل نمی شوند چون همه ی دسته ی 1 به جز یکی را دارند پس دور به طول 5 نداریم)
- a3, همه ی دسته ی 2 به جز a2,j(به اولین راس وصل می شود پس دور به طول 6 داریم و این دور کوچک ترین دور گراف و کمر گراف استو نیاز به برسی حالت های دیگر برای 6 نیست)
2)a3 , همه دسته ی 1 به جز a1,i(به اولین راس وصل نمی شوند چون همه ی دسته ی 1 به جز یکی را دارند پس دور به طول 5 نداریم)
3)a3,a2,j[/sub , همه دسته ی 1 به جز a[sub]1,iوa1,w(به اولین راس وصل نمی شوند چون همه ی
دسته ی 1 به جز دو تا را دارند پس دور به طول 5 نداریم)

به روم نیارید زیادی کثیفه

1.1.29) ثابت کنید در هر جمع 6 نفره یا دست کم 3 نفر هستند که هر 3 با هم آشنایند یا دست کم 3 نفر هستند که هر 3 با هم غریبه اند.(رابطه آشنایی 2 طرفه است)

 

[A.MR.P]

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

1.1.29) ثابت کنید در هر جمع 6 نفره یا دست کم 3 نفر هستند که هر 3 با هم آشنایند یا دست کم 3 نفر هستند که هر 3 با هم غریبه اند.(رابطه آشنایی 2 طرفه است)
بزرگترین درجه را در نظر بگیرید:
اگر بزرگتر یا مساویِ 3 بود:اگر دوتا از آنها بهم وصل باشند که مسئله حل ـه پس فرض میکنیم هیچ یک به هم وصل نباشند که در این صورت آن 3 راس از اینها نا آشنای دو طرفِ تشکیل می دهند.
اگر همه ی درجه ها کمتر مساوی 2 بود تو مکمل گراف همین استدلال رو میاریم(آشنایی و نا آشنایی رابطه معکوس اند یعنی دوستی در خود گراف نا آشنایی در مکمل آن است)

 

[most wanted]

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

1.1.30) گراف ساده G با ماتریس مجاورت A و ماتریس وقوع M در نظر بگیرید. نشان دهید درجه یِ راس i اُم همان i اُم ـین درایه قطر اصلی در A2 , MMt است.
درایه یِ {i,j} یِ A[sup]2 , MMt چه چیزی راجع به گراف G را بیان می کند.؟
درایه یِ (i،i) ماترس MM[sup]t مجموع حاصلضرب درایه های متناظرِ سطر i اُم M و ستون i اُم M[sup]t است(که این دو با هم برابرند) پس جواب مجموع مربّعات سطر i اُم M است. از آنجا که گراف ساده است همه یِ درایه ها 0 و 1 اند پس مربعات ـِشون خودشون ان . پس جواب میشه مجموع درایه های سطرِ i اُم M که نشان دهنده یِ تعداد یال های متصّل به i است که همان درجه ان است.
برای A[sup]2 هم از آنجا که ماتریس مجاورت نسبت به قطر اصلی قرینه است. جواب همان مجموع توان 2 ـِه سطر i اُم میشود که طبق استدلال مشابه بدست می آید.


درایه یِ {i,j} یِ A[sup]2 , MM[sup]t نشانه یِ تعداد یال های میان i,j است.
طبق استدلال مشابه درایه یِ i,j همان مجموع ضرب نظیر به نظیر سطرi اُم در سطرj اُم است. از طرفی واضح است هر دو درایه یِ هم ستون همزمان 1 اَند اگر بین i,j یال باشد. پس این مجموع نشان دهنده یِ تعداد یال های بین i,j است.
1.1.31)ثابت کنید گراف n راسی خود مکمل[nb]با مکمل خود یکریخت باشد[/nb] است اگر و فقط اگر n همنهشت با 0 یا 1به پیمانه 4 باشد.(n یا n-1 به 4 بخشپذیر باشد.)

 

[A.MR.P]

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

1.1.31)ثابت کنید گراف n راسی خود مکمل است اگر و فقط اگر n همنهشت با 0 یا 1به پیمانه 4 باشد.(n یا n-1 به 4 بخشپذیر باشد.)
شرطِ لازم برای یریخت بودنِ دو گراف برابری تعداد یال هایشان است،و چ.ن مجموع یال های یک گراف و مکملش (2,n) cاست. و برای این که بتوان یال هارا دوقسمت کرد باید این مقدار بر 2 بخشپذیر باشد که ایجاب میکند طرف اول حکم مسئله را.
حالا باید نشان دهیم برای هر n با شرایط مسئله چنین گرافی موجود است.فرض کنید:
n=4k:

n=4k+1:

 

[rezaezio]

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

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

در گراف K m,n اگر یکی از m یا n زوج باشند این کار شدنیه ، فرض کنید m زوج باشه می شه گراف رو به دو زیر گراف
K m/2,n تبدیل کرد.
اگه m و n هر دو فرد باشند ، تعداد فردی یال داریم ، پس به دو زیر گراف یکریخت تجزیه نمیشه

1.1.33) برای n=5 و n=7 و n=9 ، گراف Kn را به تعدادی گراف Cn تجزیه کنید.

 

[A.MR.P]

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

1.1.33) برای n=5 و n=7 و n=9 ، گراف Kn را به تعدادی گراف Cn تجزیه کنید.

1.1.34)گراف پترسن را به سه زیر گراف یکریخت(همبند) تجزیه کنید.همچنین به p4

 

[rezaezio]

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

1.1.34)گراف پترسن را به سه زیر گراف یکریخت(همبند) تجزیه کنید.همچنین به P4



1.1.35) ثابت کنید گراف Kn تجزیه میشه به 3 تا گراف دو به دو یک ریخت اگر و فقط اگر n+1 بر 3 بخش پذیر نباشد.

اگر n بر 3 بخش پذیر باشه راس ها رو به سه دسته A , B , C تقسیم می کنیم ، هر کدام از این دسته ها بین خودشان کامل هستند ولی تمامی یال های بین A , B را به دسته A نسبت می دهیم ، یال های بین B , C را به دسته B نسبت می دهیم و همه یال های بین A , C را به دسته C نسبت می دهیم ! واضح است که حکم برقرار است ، حال اگر n عددی 3k+1 باشد یکی از اعضا را کنار می گذاریم و همان کار های بالا را انجام می دهیم و یال های بین راس کنار گذاشته شده و هر دسته را به همان دسته نسبت می دهیم .

و اگر n عددی 3k+2 باشد آنگاه تعداد یال ها بر 3 بخش پذیر نیست پس به 3 زیرگراف مجزا تجزیه نمی شوند.

1.1.36)ثابت کنید اگر Kn به تعدادی مثلث تجزیه شود ، n-1 یا n-3 بر 6 بخش پذیر است.


چون هر مثلث به هر راس درجه ۲ اضافه می کنه پس درجه هر راس زوجه پس تعداد رئوس گراف فرده پس
n = 6k+1 یا n = 6k+3 یا n = 6k+5
خوب اگه n = 6k+5 باشه ٬ تعداد یال ها بر ۳ بخش پذیر نیست پس 6k+5 هم رد میشه

1.1.37) فرض کنید G گرافی باشه که درجه همه راس هاش ۳ هستند . ثابت کنید نمیشه به تعدادی مسیر تجزیش کرد که طول هر کدام حداقل 5 باشه !

 

[kia.celever]

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

1.1.37) فرض کنید G گرافی باشه که درجه همه راس هاش ۳ هستند . ثابت کنید نمیشه به تعدادی مسیر تجزیش کرد که طول هر کدام حداقل 5 باشه !

برهان خلف می زنیم. فرض کنید G رو به k تا مسیر حداقل 5 رأسی تجزیه کردیم. هر مسیر حداقل 3 تا رأس میانی داره. چون گراف 3 منتظمه هیچکدوم از رأسا 2 بار جای رأسای میانی ظاهر نشدن (چون درجشون بیشتر از 3 می شه). همچنین هرکدوم از این رأس ها باید دقیقا جای رأس پایانی یه مسیر دیگه اومده باشن. پس حداقل 3k تا رأس پایانی می خوایم. ولی k تا مسیر حداکثر 2k تا رأس پایانی دارن که تناقضه.

1.1.38) فرض کنید G یه گراف 3 منتظمه. ثابت کنید G به K1,3 تجزیه می شه اگر و فقط اگر دوبخشی باشه.

 

[most wanted]

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

1.1.38) فرض کنید G یه گراف 3 منتظمه. ثابت کنید G به K1,3 تجزیه می شه اگر و فقط اگر دوبخشی باشه.
لم:اگر گرافی دوبخش مستقل B,A داشته باشد و گراف منتظم باشد نتیجه می دهد: |A|=|B|
اگر گراف 3 منتظم و دو بخشی(B,A )باشد،طبق لم دو بخش از تعداد مساوی رئوس برخوردارند.از طرفی تعداد یال ها برابر با3m ( نصف مجموع درجات(|m=|A|=|B) ) است ، از طرفی هر K1,3 سه یال را در بر میگیرد،پس نیاز به m تا از آنها داریم.
طرف 1 راسی همه K1,3 ها را روی یکی از B,A می گذاریم،حال یال های خارج شده برابر 3m است که واضح است می توان آن ها را بین مجموعه ی دیگر طوری وصل کرد که درجه همه رئوس 3 باشد.
اگر گراف سه منتظم باشد و به K1,3 تجزیه شده باشد; چون درجه هر راس 3 است یا در یک K1,3 نقش راس درجه 3 را ایفا می کند یا در 3 تا K1,3 نقش راس درجه 1;همه یِ آنهایی که در دسته اول هستند را یک مجموعه در نظر بگیرید(مثلا A) واضح است A مستقل است،اگر راس های دسته دوم را هم B در نظر بگیریم بین آنها هم یالی وجود ندارد چون اگر وجود داشته باشد با دسته بندی ما در تناقض است و اگر وصل باشند در واقع به جای دو یال دو مجموعه دوم عمل می کنه که در این صورت مجموع درجات با 3 منتظم بودن گراف در تناقض است.
پس چون گراف را به دو مجموعه مستقل شامل همه رئوس تقسیم کردیم،گراف دو بخشی است .
1.1.39)مشخَّص کنید گراف k6 به کدام یک از گراف های زیر تجزیه می شود،به طوری که همه ی آن ها دو به دو یکریخت باشند.

 

[Dark Eagle]

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

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

صفحه 98 از تبصره 9.2.2 .... تا .... تعریف 12.2.2 .... ینی چی ؟....

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

و .... اثبات قضیه ی حال .... صفحه ی 148 ..... (7.1.3)

ما نیاز مند توضیح گرمتان هستیم .... (م ف ه و م ی !)

 

[مهدی]

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

صرفا برای ادغام
در آینده چند تا سوال میذارم

 

[Phanntom]

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

شاید بعضیاشون تکراری باشن

*کشوری 1001 شهر دارد .بین هر دو شهر از این کشور یک جاده ی یک طرفه وجود دارد. از 1000 جاده ی متصل به هر شهر 500تا در یک جهت و 500 تا در جهت دیگرند. 668 شهر از این کشور اعلام استقلال کرده و تشکیل یک جمهوری داده اند. ثابت کنید از هر شهر این جمهوری بدون خارج شدن از جمهوری میتوان به هر شهر دیگر آن رفت.

** در یک گراف همبند با 1993 راس درجه ی هر راس حداقل 93 است.ثابت کنید بین هر دو راس مسیری وجود دارد که طول آن از 62 بیشتر نیست.

*** در یک گروه 1990 نفری هر نفر 1327 دوست دارد. ثابت کنید، در این گروه چهار نفر وجود دارند که دو به دو با هم آشنا باشند.

**** تعدادی مهره در یک جدول n*n قرار دارد به طوریکه هر خانه ای که مهره ندارد.با حداقل یک خانه مهره دار همسایه است و برای هر دوخانه ی مهره دار مانند aوb دنباله ای از خانه های مهره دار با شروع از a و پایان در b وجود دارد که در لین دنباله هر دو خانه متوالی یک ضلع مشترک دارند.
ثابت کنید حداقل n^2-2 ÷3 مهره در جدول وجود دارد.

***** در یک جمع 1999 نفر حضور دارند.در بین هر 50 نفر حداقل 2 نفر همدیگر را نمی‌شناسند.
ثابت کنید حداقل 41 نفر هستند در این مجموعه به طوریکه حداکثر 1958 نفر را بشناسند.

 

[mhjh]

یک سوال

سلام ، یک سوال راجع به تطابق بیشینه گرافهای دوبخشی داشتم.
آیا این گزاره ای که مینویسم درسته ؟
" فرض کنید گرافی دوبخشی داریم که هر بخش آن i راس داشته باشد. یعنی کلا 2i راس داشته باشد .
و همچنین فرض کنید که این گراف c یال داشته باشد .
آیا این درست است که بگوییم که تطابق بیشینه این گراف i/c است ؟

 

[Phanntom]

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

عزیزان دل یا سوالات رو حل کنید یا سوال بذارید