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

[GUST]

سلام
هاول حکیمی چطوریه !? این سوال روش حلش هاول حکیمیه.چطوری حل میشه؟

[پویا دقتی]

سلام
هاول حکیمی چطوریه !? این سوال روش حلش هاول حکیمیه.چطوری حل میشه؟

با عرض سلام و وقت بخیر

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

مثلا در قسمت اول می دونیم که تعدا رئوس فرد باید عددی زوج باشه .... پس این قسمت رد میشه

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

[GUST]

با عرض سلام و وقت بخیر

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

مثلا در قسمت اول می دونیم که تعدا رئوس فرد باید عددی زوج باشه .... پس این قسمت رد میشه

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

این دنباله گرافیکاله ?
3.2.1.1.1

[پویا دقتی]

این دنباله گرافیکاله ?
3.2.1.1.1

بله .... برای اطمینان می تونین رسمش کنین

[GUST]

بله .... برای اطمینان می تونین رسمش کنین

با روش تشریحی میخوام رسم جواب داد ! ولی تشریحیش چطوریه؟

[GUST]

با روش تشریحی میخوام رسم جواب داد ! ولی تشریحیش چطوریه؟

خیلی عجیبه ! رسم شد ولی !هاول حکیمی تو مرحله ۲ ارور داد ! عدد منفی پیدا شد !

[پویا دقتی]

با روش تشریحی میخوام رسم جواب داد ! ولی تشریحیش چطوریه؟

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

اول دنباله راس ها را به صورت نزولی بنویسین : 1 / 1 / 1 / 2 / 3

حالا عدد 3 رو خط بزنین و از 3 راس بعدی یکی کم کنین ، به این صورت : 1 / 0 / 0 / 1

حالا دوباره دنباله رو نزولی کنین : 0 / 0 / 1 / 1

الان عدد 1 رو خط بزنین و از عدد بعدی یکی کم کنین به 0 / 0 / 0 می رسین .... پس دنباله اولیه گرافی بوده

[GUST]

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

اول دنباله راس ها را به صورت نزولی بنویسین : 1 / 1 / 1 / 2 / 3

حالا عدد 3 رو خط بزنین و از 3 راس بعدی یکی کم کنین ، به این صورت : 1 / 0 / 0 / 1

حالا دوباره دنباله رو نزولی کنین : 0 / 0 / 1 / 1

الان عدد 1 رو خط بزنین و از عدد بعدی یکی کم کنین به 0 / 0 / 0 می رسین .... پس دنباله اولیه گرافی بوده

دمت گرم. اين چطوريه؟

مثال 31

[پویا دقتی]

چون گفته 9 یال داره پس مجموع اعداد در دنباله گرافی باید برابر 18 باشه

اعداد رو با هم جمع کنین .... به عدد 14 می رسین ... پس مجموع x و y باید 4 باشه ..... حالا اگه قرار بدین x = y = 2 شرایط مساله برقرار میشه

می تونین با الگوریتم هاول - حکیمی هم امتحان کنین که این دنباله گرافیه

[GUST]

چون گفته 9 یال داره پس مجموع اعداد در دنباله گرافی باید برابر 18 باشه

اعداد رو با هم جمع کنین .... به عدد 14 می رسین ... پس مجموع x و y باید 4 باشه ..... حالا اگه قرار بدین x = y = 2 شرایط مساله برقرار میشه

می تونین با الگوریتم هاول - حکیمی هم امتحان کنین که این دنباله گرافیه

داداش پويا دمت گرم! اينم بگو بى زحمت

[GUST]

اينم يکى بگه

[GUST]

مهندس عذر میخوام اگه هردوشون 2 باشن که تعداد رئوس زوج میشه یه عدد فرد؟مگه ما این قانون رو نداشتیم تو این فصل؟

نخىر! تعداد رئوس فرد بايد زوج باشه

[محمد3568]

نخىر! تعداد رئوس فرد بايد زوج باشه

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

[پویا دقتی]

اينم يکى بگه

ببینین برا به دست آوردن حداقل ، باید a و b رو کمترین مقدار ممکن قرار بدیم .... ولی چون در این گراف 6 راسی ، راسی از درجه 5 داریم پس باید درجه هر راس 1 باشه

پس تا اینجا a = b = 1 ...... ولی این گراف ساده نیست .... ضمنا یکی از a و b نمی تونه زوج باشه و دیگری فرد .... چون در این صورت تعداد رئوس فرد عددی فرد میشه که درست نیست

پس a و b رو برابر 2 قرار می دهیم ..... دنباله 2 / 2 / 2 / 3 / 4 / 5 گرافیه

برا حداکثرش هم به همین صورت عمل کنین

[GUST]

ببینین برا به دست آوردن حداقل ، باید a و b رو کمترین مقدار ممکن قرار بدیم .... ولی چون در این گراف 6 راسی ، راسی از درجه 5 داریم پس باید درجه هر راس 1 باشه

پس تا اینجا a = b = 1 ...... ولی این گراف ساده نیست .... ضمنا یکی از a و b نمی تونه زوج باشه و دیگری فرد .... چون در این صورت تعداد رئوس فرد عددی فرد میشه که درست نیست

پس a و b رو برابر 2 قرار می دهیم ..... دنباله 2 / 2 / 2 / 3 / 4 / 5 گرافیه

برا حداکثرش هم به همین صورت عمل کنین

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