گراف نیمه اویلری جهت دار (Directed Semi-Eulerian Graph)، در ریاضیات (Mathematics)
انواع گراف اویلری (Eulerian Graph) را در آموزش زیر شرح دادیم :
گراف نیمه اویلری جهت دار (Directed Semi-Eulerian Graph) :
این نوع گراف، معادل جهت دار گراف نیمه اویلری است. یک گراف جهت دار همبند ضعیف را نیمه اویلری می نامند، اگر دارای یک مسیر اویلری جهت دار باشد که از هر یال دقیقا یک بار عبور کند، اما لزوما به رأس شروع بازنگردد. شرط وجود چنین مسیری به این صورت است: گراف باید حداکثر دو رأس داشته باشد که در آنها درجه ورودی و خروجی متفاوت باشد. اگر چنین دو رأسی وجود داشته باشند، یکی از آنها (رأس شروع) باید دارای
\[ \deg^+(v) = \deg^-(v) + 1 \]و دیگری (رأس پایان) باید دارای
\[ \deg^-(v) = \deg^+(v) + 1 \]باشد. برای تمام رئوس دیگر، درجه ورودی و خروجی باید برابر باشند. این گراف ها در مسائل برنامه ریزی و زمان بندی که مسیرها جهت دار هستند، کاربرد دارند. به عنوان مثال، در مسیریابی ترافیک یک طرفه، یافتن مسیری که از همه خیابان ها عبور کند.
نویسنده علیرضا گلمکانی
شماره کلید 5525
گزینه ها 
نظرات 0 0 0