ریاضیات

انواع نمودارها-

قبل از اینکه این مقاله را مرور کنید ، مطمئن شوید که مقاله قبلی درباره انواع نمودارها را در تئوری نمودار مرور کرده اید .

ما در این زمینه صحبت کرده ایم-

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

در این مقاله ، ما در مورد نمودارهای همیلتونین بحث خواهیم کرد.

نمودار هامیلتونی-

نمودار همیلتونین ممکن است به صورت زیر تعریف شود:

همچنین بخوانید- نمودار اولر

مثال نمودار همیلتونی-

نمودار زیر مثالی از نمودار همیلتونی است-

اینجا،

• این نمودار شامل یک پیاده روی بسته ABCDEFA است.
• از هر راس نمودار دقیقاً یک بار بازدید می کند به جز راس شروع.
• در طول راه رفتن لبه ها تکرار نمی شوند.
• بنابراین ، این نمودار همیلتونی است.

متناوباً ، یک مدار همیلتونین ABCDEFA در نمودار بالا وجود دارد ، بنابراین یک نمودار همیلتونین است.

مسیر هامیلتونی-

• اگر در نمودار متصل پیاده روی وجود داشته باشد که دقیقاً یک بار بدون تکرار لبه ها از هر رأس نمودار بازدید کند ، پس چنین پیاده روی به عنوان مسیر همیلتون خوانده می شود.

یا

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

مثالهای مسیر هامیلتونی-

نمونه هایی از مسیر همیلتون به شرح زیر است -

مدار همیلتونین-

مدار همیلتونین به چرخه همیلتونین نیز معروف است .

• اگر در نمودار متصل پیاده روی وجود داشته باشد که دقیقاً یک بار از هر راس نمودار بازدید کند (به جز راس شروع) بدون تکرار لبه ها و به راس شروع بازگردد ، بنابراین چنین پیاده روی به عنوان مدار همیلتون خوانده می شود.

یا

• اگر چرخه ای در نمودار متصل وجود داشته باشد که شامل تمام رئوس نمودار باشد ، آن چرخه به عنوان مدار همیلتون خوانده می شود.

یا

• یک مسیر همیلتونی که در همان راس شروع و ختم می شود ، مدار همیلتونین نامیده می شود.

یا

• مسیر بسته همیلتون به عنوان مدار همیلتون خوانده می شود.

مثالهای مدار همیلتونین -

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

یادداشت های مهم-

• هر مدار همیلتونین را می توان با برداشتن یکی از لبه های آن به یک مسیر همیلتونی تبدیل کرد.
• هر گرافی که حاوی مدار همیلتون باشد حاوی مسیر همیلتونی نیز هست اما برعکس درست نیست.
• ممکن است بیش از یک مسیر همیلتونین و مدارهای همیلتونی در یک نمودار وجود داشته باشد.

همچنین نمودار - Planar را بخوانید

مشکلات عملی مبتنی بر گرافهای هامیلتون در نظریه گراف-

چالش ها و مسائل-

نمودارهای هامیلتونی کدامیک از موارد زیر است / هستند؟

راه حل ها-

آ)

این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

ب)

این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

ج)

نمودار هم شامل مسیر همیلتون (ABCDHGFE) و هم مدار همیلتون (ABCDHGFEA) است.

از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

د)

نمودار شامل هر دو مسیر همیلتون (ABCDEFG) و مدار همیلتون (ABCDEFGA) است.

از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

ه)

این نمودار نه حاوی مسیر همیلتون است و نه حاوی مدار همیلتونین است.

از آنجا که نمودار حاوی مدار همیلتون نیست ، بنابراین نمودار همیلتونین نیست .

و)

نمودار شامل هر دو مسیر همیلتون (ABCDEFGHI) و یک مدار همیلتونین (ABCDEFGHIA)

از آنجا که نمودار شامل یک مدار همیلتونین است ، بنابراین یک نمودار همیلتونین است .

برای درک بهتر در مورد نمودارهای همیلتونین در تئوری نمودار ،

این سخنرانی ویدئویی را مشاهده کنید

مقاله بعدی - نمودار دو طرفه

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

با مراجعه به کانال YouTube ما LearnVidFun ، سخنرانی های ویدیویی را تماشا کنید .

خلاصه

نام مقاله

نمودار همیلتونین | مسیر همیلتونین | مدار همیلتونین

شرح

نمودار Hamiltonian in Graph Theory- نمودار Hamiltonian یک نمودار متصل است که شامل یک مدار Hamiltonian است. مثالهای نمودار همیلتونی. مسیر Hamiltonian و Hamiltonian Circuit- مسیر Hamiltonian مسیری در یک نمودار متصل است که شامل همه رئوس نمودار است. یک مسیر همیلتونین بسته ، مدار همیلتونین نامیده می شود.

نویسنده

آکشی سینگال

نام ناشر

دروازه ویدیالی

https://www.gatevidyalay.com/hamiltonian-graphs-hamiltonian-path-hamiltonian-circuit/