معمای گرینگ برگ

[sa1378]

این معما رو اویلر حل کرده بود که مربوط به یه دهکده با 2 ساحل و دو جزیره و 7 پل بوده

مردم این شهر سالها فکر میکردن که چجوری میشه از یه قسمت a یا b یا c یا d شروع کرد و از هر پل فقط یک بار گذشت و سر آخر به همون نقطه بازگشت

گراف این مسئله رو میتونین اینجا ببینین

من هرچی فکر کردم نتونستم ولی این اویلر در قرن هجدهم تونسته

خواهشمند کمک ذهنی هستیم

 

[sa1378]

پاسخ : معمای گرینگ برگ

آره از هر یال یک بار
جواب چی شد
مثلا بگین اول از a به b ، بعد b به d و....

 

[sa1378]

پاسخ : معمای گرینگ برگ

خیلی راه است
مثلا یکیش:
abadbcb

اولا تو این روش یال cd طی نشده
دوما به جای اول برنگشتیم

 

[a$hk@n]

پاسخ : معمای گرینگ برگ

اولا تو این روش یال cd طی نشده
دوما به جای اول برنگشتیم

ببخشید الان تصحیحش میکنم!!!

---- دو نوشته به هم متصل شده است ----

آره از هر یال یک بار
جواب چی شد
مثلا بگین اول از a به b ، بعد b به d و....

این گراف که اویلری نیست؟؟
4 راس فرد داره که !!!

 

[sa1378]

پاسخ : معمای گرینگ برگ

پس اویلری چه شکلیه؟

 

[msaeids]

پاسخ : معمای گرینگ برگ

تا حدودی میشه گفت آسونه
راس a رو ببینید
سه تا یال بهش وارد میشه
باید از اون سه تا یال هم گذر کنیم
یه بار باید بهاین راس واردشیم
یه بار خارج شیم
دوباره وارد شیم
خوب حالا چون درجه ی a فرده نمیشه
یعنی ما یه بار میریم تو راس a ولی دیگه یالی نداریم که ازش خارج شیم

 

[sa1378]

پاسخ : معمای گرینگ برگ

تا حدودی میشه گفت آسونه
راس a رو ببینید
سه تا یال بهش وارد میشه
باید از اون سه تا یال هم گذر کنیم
یه بار باید بهاین راس واردشیم
یه بار خارج شیم
دوباره وارد شیم
خوب حالا چون درجه ی a فرده نمیشه
یعنی ما یه بار میریم تو راس a ولی دیگه یالی نداریم که ازش خارج شیم

حرف شما یعنی این حل نمیشه
ولی گراف اویلری حل شده
پس این گراف اویلری نیست
پس گراف اویلری رو اگه میشه بزارین اینجا

 

[a$hk@n]

پاسخ : معمای گرینگ برگ

پس اویلری چه شکلیه؟

---- دو نوشته به هم متصل شده است ----

این یه نمونشه

 

[sima98]

پاسخ : معمای گرینگ برگ

اینی که شما کشیدید
اویلر اثبات کرده که نمیشه این کارو کرد.
در سال1736
قضیه هم ماله یه شهر که فکر کنم7تا پل داشت.دقیق یادم نمی اد.
ولی اینی که شما کشیدید اثبات شده که غلطه.

 

[sa1378]

پاسخ : معمای گرینگ برگ

---- دو نوشته به هم متصل شده است ----

این یه نمونشه

اون وقت این چجوری حل میشه؟

 

[sinamosavi]

پاسخ : معمای گرینگ برگ

یه گراف اویلریه اگر و فقط اگر درجه همه راس هاش زوج باشه. گراف کونیگسبرگ همه راس هاش فرد هستن بنابراین نه تنها اویلری نیست بلکه نیمه اویلری هم نیست.
اینم که میگن گراف اویلری حل شده است یعنی اینکه ما شرط لازم و کافی برای اویلری بودن یه گراف رو می دونیم(همون شرط بالا) ولی هنوز شرط لازم و کافی برای اینکه یه گراف مثلا همیلتونی باشه پیدا نشده.

 

[sima98]

پاسخ : معمای گرینگ برگ

---- دو نوشته به هم متصل شده است ----

این یه نمونشه

اگر بتوان گرافي را به صورت پيوست ه از يك جا شروع به رسم كرد و دوباره به همان جا رسيد،
اويلري مي باشد
من اینطوری شنیدم.​

 

[sinamosavi]

پاسخ : معمای گرینگ برگ

اگر بتوان گرافي را به صورت پيوست ه از يك جا شروع به رسم كرد و دوباره به همان جا رسيد،
اويلري مي باشد
من اینطوری شنیدم.​

ببینید این درسته ولی جواب نیست. یعنی درواقع خود سواله که به شکل دیگه ای طرح شده(چون اگر ما از همه یال ها یک بار رد بشیم و به راس اولیه مون برگردیم در واقع معادل با اینه که اون گراف رو بدون ورداشتن مداد و دوبار طی کردن یک خط بکشیم)
ولی شرطی که برای اویلری بودن یک گراف لازم و کافیه همون زوج بودن درجات راس هاست.

 

[a$hk@n]

پاسخ : معمای گرینگ برگ

اگر بتوان گرافي را به صورت پيوست ه از يك جا شروع به رسم كرد و دوباره به همان جا رسيد،
اويلري مي باشد
من اینطوری شنیدم.​

خب درست است وقتی که بیش از 2 راس فرد داشته باشیم نمیتونیم این کارو انجام بدیم.

 

[sinamosavi]

پاسخ : معمای گرینگ برگ

خب درست است وقتی که بیش از 2 راس فرد داشته باشیم نمیتونیم این کارو انجام بدیم.

البته این شرط برای نیمه اویلری بودنه. چون توی گراف نیمه اویلری دیگه به راس اولیه بر نمی گردیم بنابراین باید دقیقا 2 تا راس فرد داشته باشیم.

 

[a$hk@n]

پاسخ : معمای گرینگ برگ

البته این شرط برای نیمه اویلری بودنه. چون توی گراف نیمه اویلری دیگه به راس اولیه بر نمی گردیم بنابراین باید دقیقا 2 تا راس فرد داشته باشیم.

کلا مگه در گراف اویلری بیش از 2 راس فرد ندارد درسته که این؟؟
من نیمه اویلری رو ندیدم ؟ میشه یه توضیح بدین لطفا؟؟ چه فرقی میکنه؟؟ممنون

 

[sinamosavi]

پاسخ : معمای گرینگ برگ

کلا مگه در گراف اویلری بیش از 2 راس فرد ندارد درسته که این؟؟
من نیمه اویلری رو ندیدم ؟ میشه یه توضیح بدین لطفا؟؟ چه فرقی میکنه؟؟ممنون

نه گراف اویلری دقیقا همه راس هاش زوج هستن. گراف نیمه اویلری تفاوتش با گراف اویلری اینه که در مرحله آخر به راس اولیه بر نمی گردیم و شرط نیمه اویلری بودن هم فرد بودن دقیقا 2 تا راسه. و واضحه که هیچ گرافی نیست که هم اویلری باشه و هم نیمه اویلری.

 

[sa1378]

پاسخ : معمای گرینگ برگ

یه سوال گراف هم داشتم گفتم دیگه تاپیک نزنم همینجا بپرسم
اگر تعداد یال ها یا اندازه گراف 4 باشه و {V={a,b,c,d,e,f ، چند گراف میتوان رسم کرد که A و B در آن مجاور باشند ولی A و C مجاور نباشند؟
باید از ترکیب رفت؟

 

[msaeids]

پاسخ : معمای گرینگ برگ

فکر کنم تو کتاب آشنایی با گراف مخصوص مرحله یک فاطمی فصل یکش نوشته که اویلر در سال ... ثابت کرد نمیتوان چنید عملی رو انجام داد
برید اون کتاب رو چک کنید
چون من الان بهش دسترسی ندارم و اینارو از حافظه گفتم که بهش اعتاری نیست

 

[Yousefi]

پاسخ : معمای گرینگ برگ

سلام،

من چند تا چیزرو توی تاپیک نفهمیدم! یکی اینکه چرا اسمش گرینگ برگه!! یکی اینکه چه ربطی به ترکیبیات ممتاز (!) داره.

اسمش کوینگسبرگه (Konigsberg) نه گرینگ برگ !!! (گرینگ برگ تقریبا میشه برگ سبز !!!) راه اویلر اینطوری بوده:

[FONT=Tahoma, Iranian Sans, DejaVu Sans, sans-serif]

[/FONT] [FONT=Tahoma, Iranian Sans, DejaVu Sans, sans-serif]

[/FONT] [FONT=Tahoma, Iranian Sans, DejaVu Sans, sans-serif]

[/FONT]
میاد برای هر منطقه یه راس میگذاره و اگه از یه منطقه به یه منطقه ی دیگه میشد رفت، به هم دو راس متناظرشون رو متصل می کنه (به ازای هر پل یه یال)، بعد می بینه تعدادی راس وجود داره با درجه ی فرد ( یعنی یه راسی که تعداد فردی خط بهش وصله) پس می فهمه که نمیشه از همه ی پل ها گذشت و به همون جا رسید، چرا؟ چون اگه بخوایم از یه راسی بریم و به همون راس بر گردیم، هر بار 2 تا از یال ها رو می پیماییم، که چون یه راسی هست که یه یال فرد داره، پس نمیشه اینکارو کرد.