سلام
هاول حکیمی چطوریه !? این سوال روش حلش هاول حکیمیه.چطوری حل میشه؟
http://images.tapatalk-cdn.com/15/07...a7b1631152.jpg
نمایش نسخه قابل چاپ
سلام
هاول حکیمی چطوریه !? این سوال روش حلش هاول حکیمیه.چطوری حل میشه؟
http://images.tapatalk-cdn.com/15/07...a7b1631152.jpg
با عرض سلام و وقت بخیر
به نظرم میشه این سوال رو از راه ساده تری هم حل کرد
مثلا در قسمت اول می دونیم که تعدا رئوس فرد باید عددی زوج باشه .... پس این قسمت رد میشه
یا مثلا در قسمت دوم می دونیم که اگه درجه راسی بخواد 6 باشه باید به 6 راس دیگه یال داشته باشه ..... که این هم رد میشه
برا اثباتش می تونین از همون الگوریتم هاول - حکیمی استفاده کنین :
اول دنباله راس ها را به صورت نزولی بنویسین : 1 / 1 / 1 / 2 / 3
حالا عدد 3 رو خط بزنین و از 3 راس بعدی یکی کم کنین ، به این صورت : 1 / 0 / 0 / 1
حالا دوباره دنباله رو نزولی کنین : 0 / 0 / 1 / 1
الان عدد 1 رو خط بزنین و از عدد بعدی یکی کم کنین به 0 / 0 / 0 می رسین .... پس دنباله اولیه گرافی بوده
دمت گرم. اين چطوريه؟
http://images.tapatalk-cdn.com/15/07...bf41a69c2b.jpg
مثال 31
چون گفته 9 یال داره پس مجموع اعداد در دنباله گرافی باید برابر 18 باشه
اعداد رو با هم جمع کنین .... به عدد 14 می رسین ... پس مجموع x و y باید 4 باشه ..... حالا اگه قرار بدین x = y = 2 شرایط مساله برقرار میشه
می تونین با الگوریتم هاول - حکیمی هم امتحان کنین که این دنباله گرافیه
داداش پويا دمت گرم! اينم بگو بى زحمتhttp://images.tapatalk-cdn.com/15/07...bf5cdd4376.jpg
اينم يکى بگه
ببینین برا به دست آوردن حداقل ، باید a و b رو کمترین مقدار ممکن قرار بدیم .... ولی چون در این گراف 6 راسی ، راسی از درجه 5 داریم پس باید درجه هر راس 1 باشه
پس تا اینجا a = b = 1 ...... ولی این گراف ساده نیست .... ضمنا یکی از a و b نمی تونه زوج باشه و دیگری فرد .... چون در این صورت تعداد رئوس فرد عددی فرد میشه که درست نیست
پس a و b رو برابر 2 قرار می دهیم ..... دنباله 2 / 2 / 2 / 3 / 4 / 5 گرافیه
برا حداکثرش هم به همین صورت عمل کنین