معرفی¶

تعاریف¶

تور اویلری گذر بسته ای است که در آن هر یال دقیقا یک بار طی شود. دور همیلتونی دور ای است که در آن هر راس دقیقا یک بار دیده شود همچنین مسیر همیلتونی مسیری است که در آن هر راس دقیقا یک بار دیده شود.

به تفاوت گذر، گشت و مسیر توجه کنید!

تعریف تور اویلری و دور همیلتونی بسیار شبیه به هم است اما همین یک تفاوت ریز (جایگزینی راس به جای یال) باعث شده است که مسئله پیدا کردن دور همیلتونی الگوریتم چند جمله ای نداشته باشد و در مقابل برای پیدا کردن تور اویلری می توان الگوریتم خطی ارائه داد!

پل های کونیگسبرگ¶

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