زمان جاری : یکشنبه 30 اردیبهشت 1403 - 6:18 بعد از ظهر
تعداد بازدید 4194
|
نویسنده |
پیام |
admin
ارسالها : 124
عضویت: 30 /7 /1391
شناسه یاهو: hamidsalavaty
تشکرها : 7
تشکر شده : 97
|
گراف اویلری و هامیلتونی
در نظریه گراف دور اویلری (به انگلیسی: Eulerian circuit) به مسیری گفته میشود که از یک رأس شروع شود و از تمامی یالها یکبار (و فقط یکبار) بگذرد و به همان رأس بازگردد. اگر مسیر از تمام یال ها عبور کند ولی به جای اولش باز نگردد به آن مسیر اویلری(به انگلیسی: Eulerian path) میگویند.
دور اویلری زمانی وجود دارد که گراف همبند باشد و درجه هر رأس زوج باشد، یعنی تعداد یالهای متصل به آن عددی زوج باشد. به یک گراف، گراف اویلری گفته میشود اگر و فقط اگر گراف همبند باشد و درجه تمام رأسهای آن زوج باشد.
امضای کاربر :
|
|
دوشنبه 08 آبان 1391 - 16:09 |
|
تشکر شده: |
|
|
تشکر شده: |
2 کاربر از admin به خاطر این مطلب مفید تشکر کرده اند:
mgh1360 & khashei20 & |
|
admin
ارسالها : 124
عضویت: 30 /7 /1391
شناسه یاهو: hamidsalavaty
تشکرها : 7
تشکر شده : 97
|
پاسخ : 1 RE گراف اویلری و هامیلتونی
در نظریه گراف، مسیر همیلتونی مسیری در یک گراف غیرجهتدار است که هر راس را دقیقا یک بار مشاهده میکند. مدار همیلتونی (یا دور همیلتونی) مداری در یک گراف جهتدار است که دقیقا یک بار هر راس را مشاهده کرده و همچنین به راس آغازین برمی گردد.
مسیر و مدار همیلتونی به نام ویلیام رومن همیلتون*[۱] نام گذاری شدهاند. ویلیام همیلتون بازی ایکوسیان را، که امروزه به نام پازل همیلتون معروف است اختراع کرد. این بازی شامل یافتن یک مدار همیلتونی در گراف یالی یک دوازده سطحی است
مسیر همیلتونی [ویرایش]
یک مسیر همیلتونی یا مسیر قابل تعقیب، مسیری است که هر راس را دقیقا یک بار مشاهده کند. گرافی را که دارای مسیر همیلتنی باشد، گراف قابل تعقیب یا نیمه همیلتنی مینامند. هم چنین گرافی همیلتن-متصل است اگر برای هر زوج از رئوس آن، مسیری همیلتونی بین آن دو راس وجود داشته باشد.
مدار همیلتونی [ویرایش]
مدار همیلتونی، مدار همیلتونی، دور همیلتنی یا دور همیلتون، مداری است که هر راس را دقیقا یک بار مشاهده میکند.(به جز راسی که هم به عنوان آغاز و هم پایان میباشد. در نتیجه این راس دو بار دیده میشود.) به طور قراردادی، گرافی کوچک شامل یک گره، دارای مدار همیلتونی است، ولی گراف متصلی دارای دو گره، شامل مدار همیلتونی نیست.
گراف همیلتونی [ویرایش]
گرافی که دارای مدار همیلتونی باشد، گراف همیلتنی نامیده میشود. هر گراف کامل که بیشتر از دو راس داشته باشد، همیلتونی است.
گرافی با نام گراف همیلتون وجود دارد که یک دوازده وجهی منتظم است و دارای دورهای همیلتونی زیبا میباشد.(شکل(۳))
http://fa.wikipedia.org/wiki/%D9%BE%D8%B1%D9%88%D9%86%D8%AF%D9%87:HamiltonGraph.JPG
امضای کاربر :
|
|
دوشنبه 08 آبان 1391 - 16:11 |
|
ghasemi1460
ارسالها : 8
عضویت: 18 /8 /1391
شناسه یاهو: gh1460ali@yahoo.com
تشکرها : 5
|
پاسخ : 3 RE گراف اویلری و هامیلتونی
http://kelasedars.org[font=Tahoma]
|
|
جمعه 03 آذر 1391 - 10:11 |
|
برای ارسال پاسخ ابتدا باید لوگین یا ثبت نام کنید.