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

تعاریف :

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

گراف G را نیمه اویلری می گوئیم اگر و فقط اگر همبند باشد و حداکثر 2 رأس درجه فرد داشته باشد .

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

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

برای پیدا کردن دور(مسیر) اویلری در یک راف ، کافیست شرط اویلری بودن رو چک کنیم .

اگر اویلری بود ، کافیه از راسی دلخواه شروع کنیم . اگر نیمه اویلری بود ، از یک رأس درجه فرد شروع می کنیم .

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

برای بدست آوردن دور(مسیر) الگوریتم خطی نسبت به تعداد یالها( (O(E ) وجود داره .

الگوریتم :

با کمک DFS گراف را پیمایش می کنیم . هر بار که از روی یک یال گذشتیم ، یال مورد نظر رو از گراف حذف می کنیم . زمان بازگشت از DFS رأس فعلی رو به مسیر اضافه می کنیم .

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

نکته : تو گراف های نیمه اویلری ، تو هر راس حداکثر 2 بار DFS فراخوانی میشه .

تو بار اول یک مسیر از این رأس به راس درجه فرد دیگه پیدا میشه اما ممکنه تعدادی از یال ها هنوز استفاده نشده باشند . چون یال های استفاده شده رو حذف کردیم ، گراف باقیمونده اویلری است ، لذا با شروع از همین نقطه دور اویلری ای پیدا می کنیم .

به اضافه کردن این دور به ابتدای مسیری که قبلا پیدا کرده بودیم ، یک مسیر اویلری برای گراف پیدا کردیم .

به عنوان مثال اگر در گراف زیر از نقطه 1 شروع کنیم و به رأس 2 بریم ، مسیر اولیه پیدا شده ولی هنوز یال استفاده نشده وجود داره . لذا دوباره از 1 شروع می کنیم و دور اویلری گراف باقیمونده رو پیدا می کنیم و به اول مسیر قبلی اضافه می کنیم .

1 --- 2

| \

|   \

3 --- 4

مسیر اویلری این گراف میشه :

1 3 4 1 2

کد :

int path[N], len = 0;
void DFS( int x )
{
    for( int i = 0 ; i < N ; i ++ )
        if( mat[x][i] > 0 )
        {
            mat[x][i] --;
            mat[i][x] --;
            DFS( i );
        }
    path[ len ++ ] = x;
}

برای بدست آوردن دور(مسیر) کافیه از main تابع رو برای یه نقطه شروع خوب ( رأس دلخواه در گراف اویلری و رأس فرد در گراف نیمه اویلری ) فراخوانی کنید .

بعد از اجرای DFS ، اگر مسیر شامل E|  + 1| رأس بود ، path شامل دور(مسیر) مورد نظر است .

در غیر این صورت گراف ناهمبند است لذا دور(مسیر) اویلری نداریم .