سلام.
سوال اینه چه جوری بفهمیم یه گراف اویلری یا هامیلتونی؟ میشه با استفاده از این شکل توضیح بدید.
[
attachment=5444]
چه جوری میتونم مدار دور بکشم حالا اویلری یا هامیلتونی
گراف اویلری که سادست: باید درجه همه راس ها زوج باشه.
گراف همیلتونی هم راهی الگوریتمیک نداره. برای هر مساله فرق میکنه.
این گراف همیلتونی نیست چون باید تو مسیر همیلتونی مربوطه b,d,f باشند که در نتیجه باید راس a حداقل 3 بار ملاقات بشه.
ممنون... میشه بیشتر توضیح بدید متوجه نشدم! و مدار اولیری بکشید
من دقیق یادم نیست.
abcadeafga
با تشکر از پاسخ های دوستمون جناب blackhalo1989. وجود مدار اویلری فقط شرط همبندی و زوج بودن درجه رئوس رو احتیاج داره. این دوشرط، لازم و کافی هستن.
مدار همیلتونی فقط یه شرط کافی داره که مجموع درجات هردوراس بزرگتر یا مساوی تعداد رئوس باشه. وجود این شرط نشون میده گراف دور همیلتونی داره و عدم وجودش هیچ چیز رو ثابت نمیکنه. این شرط توی این گراف نیست.
این گراف مشخصه که دور همیلتونی نداره. اگه از یک راس غیر از a شروع کنیم فقط یکبار از a عبور میکنیم و دور کامل تشکیل نمیشه (حداکثر دور بطول 3 ایجاد میشه). اگرم از a شروع کنیم فقط یک دور بطول 3 درست میشه.
واقعا ممنون . خیلی اینجا کمکم کرد واقعا فروم خوبی دارید امیدوارم از سوالای زیاد خسته نشید