سوال از هاول حکیمی گراف

[پویا دقتی]

مهندس! 1 بزارىم تعداد رئوس فرد عددى زوجه که!

اگه هم a و هم b رو 1 بذاریم ، تعدا رئوس فرد عددی زوج میشه و از این جهت مشکلی نداره .... ولی اگه با الگوریتم بررسیش کنین ، متوجه میشین که این گراف ساده نیست

چیزی که عرض کردم این بود که نمی تونیم مثلا a رو 1 بذاریم و b رو 2 .... چون در این حالت تعداد رئوس فرد عددی زوج میشه

[GUST]

اگه هم a و هم b رو 1 بذاریم ، تعدا رئوس فرد عددی زوج میشه و از این جهت مشکلی نداره .... ولی اگه با الگوریتم بررسیش کنین ، متوجه میشین که این گراف ساده نیست

چیزی که عرض کردم این بود که نمی تونیم مثلا a رو 1 بذاریم و b رو 2 .... چون در این حالت تعداد رئوس فرد عددی زوج میشه

از کدوم الگوريتم فهميدين ساده نيست! ؟

[پویا دقتی]

از کدوم الگوريتم فهميدين ساده نيست! ؟

می تونین مستقیما از الگوریتم هاول - حکیمی استفاده کنین

البته با کمی دقت هم می تونین متوجه بشین این دنباله ساده نیست .... چرا ؟ ... چون که شما دنباله 1 / 1 / 2 / 3 / 4 / 5 رو در نظر بگیرین

راس درجه 5 باید به تمام 5 راس دیگر متصل شده باشد ... درست ؟ ..... حالا راس درجه 4 رو در نظر بگیرین ... این راس هم باید به 4 راس دیگر متصل شده باشد

این راس هم به راس با درجه 5 و هم به راس با درجه 3 و هم به راس با درجه 2 متصل شده ولی دیگه نمی تونه به راس با درجه 1 متصل بشه چون اونا قبلا به راس درجه 5 وصل شدن

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