گراف نیمه اویلری (Semi-Eulerian Graph)، در ریاضیات (Mathematics)
انواع گراف اویلری (Eulerian Graph) را در آموزش زیر شرح دادیم :
گراف نیمه اویلری (Semi-Eulerian Graph) :
یک گراف همبند را نیمه اویلری می نامیم، اگر دارای یک مسیر اویلری (Eulerian Trail) باشد، اما دور اویلری نداشته باشد. مسیر اویلری مسیری (Path) است که از هر یال گراف دقیقا یک بار عبور می کند، ولی لزوما به رأس مبدأ بازنمی گردد. برای اینکه یک گراف همبند، نیمه اویلری باشد، باید دقیقا دو رأس با درجه فرد داشته باشد. این دو رأس، نقاط شروع و پایان مسیر اویلری هستند. تمام رئوس دیگر باید درجه زوج داشته باشند. گراف های نیمه اویلری در مسائلی مانند یافتن کوتاه ترین مسیر برای پیمایش تمام خیابان های یک شهر (مسیریابی مأموران پست) کاربرد دارند. به عبارت ساده تر، این گراف ها تقریبا اویلری هستند، با این تفاوت که نقطه شروع و پایان یکی نیست. اگر به گراف نیمه اویلری یک یال بین دو رأس فرد اضافه کنیم، به یک گراف اویلری تبدیل می شود. این مفهوم تعمیم یافته گراف اویلری است و کاربردهای عملی فراوانی دارد. مسئله نقاشی کردن یک شکل بدون بلند کردن قلم، اما با شروع و پایان در دو نقطه متفاوت، مثالی از این نوع گراف است.
