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

نظریه نمودار

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

 

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

 

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

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

 

 

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

 

نمودار اولر-

 

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

 

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

 

یا

نمودار اولر یک نمودار متصل است که شامل یک مدار اویلر است.

 

نمودار اولر نمودار-

 

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

 

 

اینجا،

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

 

روش دیگر ، نمودار فوق شامل یک مدار اویلر BACEDCB است ، بنابراین یک نمودار اویلر است.

 

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

 

مسیر اولر-

 

مسیر اولر با نام Euler Trail یا Euler Walk نیز شناخته می شود .

 

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

یا

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

 

توجه داشته باشید

یک نمودار شامل یک مسیر اویلر خواهد بود اگر و فقط اگر شامل حداکثر دو راس درجه فرد باشد.

 

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

 

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

 

 

مدار اویلر-

 

مدار اولر با نام Euler Cycle یا Euler Tour نیز شناخته می شود .

 

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

یا

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

یا

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

یا

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

 

توجه داشته باشید

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

 

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

 

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

 

 

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

 

اگر یک نمودار متصل شامل یک مسیر اویلر باشد اما یک مدار اویلر نداشته باشد ، بنابراین چنین گرافی به عنوان یک نمودار نیمه اولر نامیده می شود.

 

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

  • نمودار باید متصل باشد.
  • نمودار باید حاوی دنباله اویلر باشد.

 

مثال-

 

 

اینجا،

  • این نمودار شامل دنباله اولر BCDBAD است.
  • اما حاوی مدار اویلر نیست.
  • بنابراین ، این یک نمودار نیمه اولری است.

 

همچنین نمودار دو طرفه را بخوانید

 

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

 

توجه -01:

 

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

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

 

توجه -02:

 

برای بررسی اینکه آیا هر گرافی حاوی مدار اویلر است یا خیر ،

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

 

Note-03:

 

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

  • فقط مطمئن شوید که متصل است و حاوی دنباله اویلر است.
  • اگر نمودار متصل باشد و حاوی دنباله اویلر باشد ، در غیر این صورت نمودار یک نمودار نیمه اولر است.

 

Note-04:

 

برای بررسی اینکه آیا هر گرافی حاوی دنباله اولر است یا خیر ،

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

 

Note-05:

 

  • اگر یک نمودار حاوی مدار اویلر باشد ، قطعاً شامل یک مسیر Euler خواهد بود.
  • اگر نمودار دارای یک مسیر اویلر باشد ، ممکن است حاوی مدار اویلر باشد یا نباشد.

 

Note-06:

 

  • نمودار اولر قطعاً یک نمودار نیمه اولر است.
  • اما نمودار نیمه اولر ممکن است نمودار اولر باشد یا نباشد.

 

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

 

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

 

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

 

 

راه حل ها-

 

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

 

با استفاده از قانون فوق ،

الف) این یک نمودار اولر است.

ب) نمودار اولر نیست.

ج) نمودار اولر نیست.

د) نمودار اولر نیست.

ه) نمودار اولر است.

و) نمودار اولر نیست.

 

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

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

 

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

 

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

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

خلاصه

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

نام مقاله

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

شرح

نمودار اویلر در تئوری نمودار - نمودار اویلر یک نمودار متصل است که تمام رئوس آن از یک درجه هستند. مثالهای نمودار اولر. Euler Path and Euler Circuit- Euler Path یک دنباله در نمودار متصل است که شامل تمام لبه های نمودار است. مسیر دنباله دار اولر به عنوان مدار اویلر خوانده می شود.

نویسنده

آکشی سینگال

نام ناشر

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

آرم ناشر

منبع

https://www.gatevidyalay.com/euler-graph-euler-trail-euler-circuit/