سلام. همیلتونی و اویلری بودن به هم ارتباطی ندارن. گرافی که دور اویلری داره درجه تمام رئوسش زوجه. شرط کافی برای همیلتونی بودن گراف هم اینه که درجه تمام رئوس از نصف تعداد رئوس کمتر نباشه.

(۰۸ دى ۱۳۹۳ ۰۶:۵۷ ب.ظ)sarashahi نوشته شده توسط:  سلام
سوالی که من دارم اینه که میشه گرافی هم ها میلتونی باشه و هم اویلری؟
و گرافی که اویلری باشه اما هامیلتونی نباشه ( و برعکس)
برای هر سه مورد گراف ساده.

سلام.
سه تا مثال از گراف های همیلتونی و اویلری

(۰۹ دى ۱۳۹۳ ۱۱:۲۱ ق.ظ)shamdooni نوشته شده توسط:  

(08 دى ۱۳۹۳ ۰۶:۵۷ ب.ظ)sarashahi نوشته شده توسط:  سلام
سوالی که من دارم اینه که میشه گرافی هم ها میلتونی باشه و هم اویلری؟
و گرافی که اویلری باشه اما هامیلتونی نباشه ( و برعکس)
برای هر سه مورد گراف ساده.

سلام.
سه تا مثال از گراف های همیلتونی و اویلری

گراف اول همیلتونی نیست. اویلری هست.
گراف دوم : توی گراف همیلتونی یال موازی نمیتونیم داشته باشیم.
توی تعریف گراف اویلری داریم: به یک گراف، گراف اویلری گفته می‌شود اگر و فقط اگر گراف همبند باشد و درجه تمام رأس‌های آن زوج باشد.
گراف آخری همبند نیست.

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

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

حالا با این تعریف دوباره شکل ها را بررسی کنید

اینو میدونم
اما تعریفی که ما از اویلری داریم اینه که ۱-همبند باشه ۲-درجه همه راس هاش زوج باشه
و برای همیلتونی باید نصف تعداد راسهاش کمتر مساوی کمترین درجه در اون گراف باشه.
اونی که شما داری میگی تعریف دور همیلتونی یا اویلری هست.

(۱۰ دى ۱۳۹۳ ۱۲:۰۱ ق.ظ)sarashahi نوشته شده توسط:  اینو میدونم
اما تعریفی که ما از اویلری داریم اینه که ۱-همبند باشه ۲-درجه همه راس هاش زوج باشه
و برای همیلتونی باید نصف تعداد راسهاش کمتر مساوی کمترین درجه در اون گراف باشه.
اونی که شما داری میگی تعریف دور همیلتونی یا اویلری هست.

منظور ازگراف اویلری دور اویلری است.
و منظور ازگراف هملتونی دور هملتونی است.

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

(۱۰ دى ۱۳۹۳ ۱۲:۱۸ ق.ظ)masoomeh_s نوشته شده توسط:  

(10 دى ۱۳۹۳ ۱۲:۰۱ ق.ظ)sarashahi نوشته شده توسط:  اینو میدونم
اما تعریفی که ما از اویلری داریم اینه که ۱-همبند باشه ۲-درجه همه راس هاش زوج باشه
و برای همیلتونی باید نصف تعداد راسهاش کمتر مساوی کمترین درجه در اون گراف باشه.
اونی که شما داری میگی تعریف دور همیلتونی یا اویلری هست.

منظور ازگراف اویلری دور اویلری است.
و منظور ازگراف هملتونی دور هملتونی است.

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

همیلتونی نیست چون نصف تعداد راس هاش میشه ۳/۵ و کمترین درجه در این گراف ۲ هست.

(۱۰ دى ۱۳۹۳ ۱۲:۰۱ ب.ظ)sarashahi نوشته شده توسط:  همیلتونی نیست چون نصف تعداد راس هاش میشه ۳/۵ و کمترین درجه در این گراف ۲ هست.

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