پرش به محتویات

پیدا کردن مسیر اویلری در $O(M)$

مسیر اویلری مسیری در یک گراف است که از تمام یال‌های آن دقیقاً یک بار عبور می‌کند. دور اویلری یک مسیر اویلری است که به شکل یک دور باشد.

مسئله، پیدا کردن مسیر اویلری در یک گراف چندگانه بدون جهت و دارای طوقه است.

الگوریتم

ابتدا می‌توانیم بررسی کنیم که آیا مسیر اویلری وجود دارد یا خیر. می‌توانیم از قضیه زیر استفاده کنیم. یک دور اویلری وجود دارد اگر و تنها اگر درجه همه رأس‌ها زوج باشد. و یک مسیر اویلری وجود دارد اگر و تنها اگر تعداد رأس‌های با درجه فرد دو باشد (یا صفر، در صورت وجود دور اویلری). علاوه بر این، البته، گراف باید به اندازه کافی همبند باشد (یعنی، اگر تمام رأس‌های ایزوله را از آن حذف کنید، باید یک گراف همبند به دست آید).

برای پیدا کردن مسیر اویلری / دور اویلری می‌توانیم از استراتژی زیر استفاده کنیم: تمام دورهای ساده را پیدا کرده و آن‌ها را در یک دور واحد ترکیب می‌کنیم - این دور، همان دور اویلری خواهد بود. اگر گراف به گونه‌ای باشد که مسیر اویلری آن دور نباشد، یال گمشده را اضافه می‌کنیم، دور اویلری را پیدا می‌کنیم، و سپس یال اضافی را حذف می‌کنیم.

جستجوی تمام دورها و ترکیب آنها را می‌توان با یک رویه بازگشتی ساده انجام داد:

رویه FindEulerPath(V)
  ۱. روی تمام یال‌های خروجی از رأس V پیمایش کن؛
       این یال را از گراف حذف کن،
       و FindEulerPath را از سر دیگر این یال فراخوانی کن؛
  ۲. رأس V را به جواب اضافه کن.

پیچیدگی این الگوریتم به وضوح نسبت به تعداد یال‌ها خطی است.

اما می‌توانیم همین الگوریتم را به صورت غیربازگشتی بنویسیم:

پشته St؛
رأس شروع را در St قرار بده؛
تا زمانی که St خالی نشده
  فرض کن V مقدار بالای St باشد؛
  اگر درجه(V) = ۰ باشد، آنگاه
    V را به جواب اضافه کن؛
    V را از بالای St حذف کن؛
  در غیر این صورت
    یک یال دلخواه خروجی از V را پیدا کن؛
    آن را از گراف حذف کن؛
    سر دیگر این یال را در St قرار بده؛

بررسی معادل بودن این دو شکل الگوریتم آسان است. با این حال، شکل دوم به وضوح سریع‌تر است و کد بسیار کارآمدتر خواهد بود.

مسئله دومینو

در اینجا یک مسئله کلاسیک دور اویلری را ارائه می‌دهیم - مسئله دومینو.

N دومینو وجود دارد، همانطور که می‌دانید، روی هر دو سر دومینو یک عدد نوشته شده است (معمولاً از ۱ تا ۶، اما در مورد ما این مهم نیست). شما می‌خواهید تمام دومینوها را در یک ردیف قرار دهید به طوری که اعداد روی هر دو دومینوی مجاور، که در سمت مشترک آنها نوشته شده‌اند، یکسان باشند. چرخاندن دومینوها مجاز است.

مسئله را بازنویسی می‌کنیم. فرض کنید اعداد نوشته شده روی دومینوها، رأس‌های گراف باشند و خود دومینوها یال‌های این گراف باشند (هر دومینو با اعداد (a,b) یال‌های (a,b) و (b,a) را تشکیل می‌دهد). در این صورت مسئله ما به مسئله پیدا کردن مسیر اویلری در این گراف کاهش می‌یابد.

پیاده‌سازی

برنامه زیر یک دور یا مسیر اویلری را در یک گراف جستجو و چاپ می‌کند، یا اگر وجود نداشته باشد، -1 را خروجی می‌دهد.

ابتدا، برنامه درجه رأس‌ها را بررسی می‌کند: اگر هیچ رأسی با درجه فرد وجود نداشته باشد، گراف یک دور اویلری دارد، اگر ۲ رأس با درجه فرد وجود داشته باشد، در گراف فقط یک مسیر اویلری وجود دارد (اما دور اویلری ندارد)، اگر بیش از ۲ چنین رأسی وجود داشته باشد، در گراف نه دور اویلری و نه مسیر اویلری وجود دارد. برای پیدا کردن مسیر اویلری (نه دور)، به این صورت عمل می‌کنیم: اگر V1 و V2 دو رأس با درجه فرد هستند، کافی است یک یال (V1, V2) اضافه کنیم، در گراف حاصل دور اویلری را پیدا می‌کنیم (که به وضوح وجود خواهد داشت)، و سپس یال «ساختگی» (V1, V2) را از جواب حذف می‌کنیم. ما دقیقاً همانطور که در بالا توضیح داده شد (نسخه غیربازگشتی) به دنبال دور اویلری خواهیم گشت و همزمان در پایان این الگوریتم بررسی خواهیم کرد که آیا گراف همبند بوده است یا خیر (اگر گراف همبند نباشد، در پایان الگوریتم برخی یال‌ها در گراف باقی می‌مانند و در این حالت باید -1 چاپ کنیم). در نهایت، برنامه در نظر می‌گیرد که ممکن است رأس‌های ایزوله در گراف وجود داشته باشند.

توجه داشته باشید که در این مسئله از ماتریس مجاورت استفاده می‌کنیم. همچنین این پیاده‌سازی با استفاده از روش brute-force یال بعدی را پیدا می‌کند، که نیازمند پیمایش مکرر کل سطر در ماتریس است. یک راه بهتر این است که گراف را به صورت لیست مجاورت ذخیره کنیم و یال‌ها را در زمان $O(1)$ حذف کرده و یال‌های معکوس را در لیستی جداگانه علامت‌گذاری کنیم. به این ترتیب می‌توانیم به یک الگوریتم با پیچیدگی $O(N)$ دست یابیم.

int main() {
    int n;
    vector<vector<int>> g(n, vector<int>(n));
    // خواندن گراف در قالب ماتریس مجاورت

    vector<int> deg(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            deg[i] += g[i][j];
    }

    int first = 0;
    while (first < n && !deg[first])
        ++first;
    if (first == n) {
        cout << -1;
        return 0;
    }

    int v1 = -1, v2 = -1;
    bool bad = false;
    for (int i = 0; i < n; ++i) {
        if (deg[i] & 1) {
            if (v1 == -1)
                v1 = i;
            else if (v2 == -1)
                v2 = i;
            else
                bad = true;
        }
    }

    if (v1 != -1)
        ++g[v1][v2], ++g[v2][v1];

    stack<int> st;
    st.push(first);
    vector<int> res;
    while (!st.empty()) {
        int v = st.top();
        int i;
        for (i = 0; i < n; ++i)
            if (g[v][i])
                break;
        if (i == n) {
            res.push_back(v);
            st.pop();
        } else {
            --g[v][i];
            --g[i][v];
            st.push(i);
        }
    }

    if (v1 != -1) {
        for (size_t i = 0; i + 1 < res.size(); ++i) {
            if ((res[i] == v1 && res[i + 1] == v2) ||
                (res[i] == v2 && res[i + 1] == v1)) {
                vector<int> res2;
                for (size_t j = i + 1; j < res.size(); ++j)
                    res2.push_back(res[j]);
                for (size_t j = 1; j <= i; ++j)
                    res2.push_back(res[j]);
                res = res2;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j])
                bad = true;
        }
    }

    if (bad) {
        cout << -1;
    } else {
        for (int x : res)
            cout << x << " ";
    }
}

مسائل تمرینی: