فرض کنید G(v,E) G یک گراف ۲بخشی باشد که در آن V به دو مجموعه X و Y افراز شده باشد؛ یک تطابق کامل از X به Y وجود دارد اگر وجود داشته باشه یک K عضو N:
deg(y) <= k <= deg(x
تو کتاب پوران همچین نکته ای هست , و من متوجه نمیشم منظورش چیه دقیقا, اون K چوری در نظر گرفته میشه؟ آیا اهمیتی داره k جند باشه؟؟ و اینکه اینجا گفته K عضو N باشه , یعنی صفر قبول نیست؟؟ (چون آقای یوسفی تو بعضی ویس هاشون بعضی جاها-اینجا رو نمیدونم- میگفتن من نوشتم N ولی شما صفر رو هم در نظر بگیرید)
میشه یکی توضیج بده؟
(۰۷ آذر ۱۳۹۳ ۰۹:۱۱ ق.ظ)zahra.s نوشته شده توسط: فرض کنید G(v,E) G یک گراف ۲بخشی باشد که در آن V به دو مجموعه X و Y افراز شده باشد؛ یک تطابق کامل از X به Y وجود دارد اگر وجود داشته باشه یک K عضو N:
deg(y) <= k <= deg(x
تو کتاب پوران همچین نکته ای هست , و من متوجه نمیشم منظورش چیه دقیقا, اون K چوری در نظر گرفته میشه؟ آیا اهمیتی داره k جند باشه؟؟ و اینکه اینجا گفته K عضو N باشه , یعنی صفر قبول نیست؟؟ (چون آقای یوسفی تو بعضی ویس هاشون بعضی جاها-اینجا رو نمیدونم- میگفتن من نوشتم N ولی شما صفر رو هم در نظر بگیرید)
میشه یکی توضیج بده؟
امیدوارم سوالتونو خوب متوجه شده باشم ولی اگه توضیحاتم بی ربط بگین تا دوباره توضیح بدم
تو کتاب گفته شده اگه بتونین حداقل یک k پیدا کنین که تو این عبارت درست باشه کفایت میکنه
k به دو دلیل نمی تونه صفر باشه
۱- چون خود کتاب گفته k عضو N (اعداد طبیعی)
۲-اگه k صفر باشه که دیگه گراف دو بخشی نمیشه چون خود کتاب گفته درجه رئوس یک بخش باید کوچکتر مساوی k و درجه رئوس بخش دیگه بزرگتر مساوی k باشند. پس اگه k صفر باشه درجه رئوس یک بخش باید کوچکتر مساوی صفر باشن یعنی گره منفرد باشند که همچین گرافی اصلا دو بخشی نیست
شما اگه تونستین تو یه گراف دو بخشی یه k بزرگتر از صفر پیدا کردین که این این عبارت رو درست کنه پس اون گراف تطابق کامل داره
اگه به مثال کتاب توجه کنین k رو ۲ گرفته و عبارت درست شده. چون درجه رئوس یک بخش کوچکتر مساوی ۲ و درجه رئوس دیگه بزرگتر مساوی ۲ هستند
نمی دونم خوب گفتم یا نه، ولی اگه چرت و پرت نوشتم ببخشید