گراف جهت‌دار بدون دور¶

قضیه 3.3.2¶

صورت قضیه : اگر \(G\) یک گراف جهت دار بدون دور باشد, آنگاه میتوان راس های \(G\) را طوری به ترتیب \(v_{1}, v_{2}, ..., v_{n}\) نوشت به طوری که اگر یال \((v_{i}, v_{j})\) در گراف باشد, انگار \(i < j\) باشد. (شکل۱ و شکل۲ را ببینید. شکل۲ یک ترتیب مرتب کردن راس ها برای گراف شکل۱ می‌باشد.)

اثبات قضیه : برای اثبات این قضیه از استقرا کمک می‌گیریم. پایه استقرا \(n = 1\) می‌باشد. که گرافی یک راسی می‌باشد. که حکم برای این گراف واضح است.

طبق قضیه \(3.1.2\) که در تعاریف گراف ثابت کردیم, در \(G\) یک راس وجود دارد که درجه ورودی آن \(0\) می‌باشد(زیرا اگر درجه ورودی همه راس ها حداقل یک باشد, آنگاه این گراف دور دارد که با فرض سوال در تناقض است).

حال فرض کنید \(d^{-}(x) = 0\) . راس \(x\) را در جایگاه \(v_{1}\) قرار میدهیم و از گراف حذف میکنیم(به همراه تمام یال های متصل به آن).

چون گراف اولیه دور نداشت, با حذف راس \(x\) دوری ایجاد نمی‌شود و شرایط استقرا برقرار است. پس طبق استقرا گراف باقی‌مانده را می‌توان طوری در یک ردیف چید که شرط سوال برقرار باشد. این ترتیب چیدن راس ها را به ترتیب در \(v_{2}, v_{3}, ..., v_{n}\) قرار می‌دهیم. از طرفی \(v_{1} = x\) است.

اکنون کافی است ثابت کنیم این ترتیب راس ها, از شرط سوال پیروی می‌کند. راس های \(v_{2}, v_{3}, ..., v_{n}\) که تکلیفشان مشخص است چون طبق استقرا چیده شده اند. حال کافی است راس \(v_{1}\) شرط را رعایت کند. که این هم واضح است. چون این راس یال ورودی ندارد. پس حکم ثابت شد!

پی نوشت : صورت شهودی تر این قضیه به این‌صورت است که می‌توان راس های گراف بدون دور را در یک ردیف چید به طوری که همه یال ها از چپ به راست(یا از راست به چپ) باشند! هم‌چنین به این ترتیب از راس ها یک topological sort یا ترتیب توپولوژیک گوییم!

الگوریتم مرتب سازی توپولوژیک¶

این الگوریتم همان الگوریتم \(DFS\) است. صرفا هنگام تمام شدن پیمایش از یک راس, آن را در یک پشته(در اینجا برای افزایش سرعت برنامه از پشته استفاده نکردیم. توصیه می‌شود استفاده از پشته به حداقل برسد), می‌اندازیم.

اثبات درستی الگوریتم¶

فرض کنید ترتیبی که الگوریتم به ما می‌دهد اینگونه باشد \(v_{1}, v_{2}, ..., v_{n}\) به لم زیر توجه کنید :

لم ۱ : وقتی راسی مانند \(x\) را در آرایه می‌اندازیم که همه راس هایی که از x می‌توان به آنها رسید(یعنی همه راس هایی مثل \(v\) که از \(x\) به \(v\) مسیر هست) , پیمایش آنها تمام شده باشد و در آرایه انداخته شده باشند!(چرا؟)

برای اثبات الگوریتم بالا از برهان خلف و لم ۱ استفاده می‌کنیم. فرض کنید ترتیبی که به دست آوردیم مطلوب نباشد. یعنی وجود دارند \(i < j\) به طوری که یال \((v_{i}, v_{j})\) متعلق به گراف باشد(یعنی یک یال از چپ به راست).

اما این ممکن نیست! زیرا وقتی \(v_{i}\) در آرایه انداخته شده, طبق لم ۱, تمام راس هایی که از \(v_{i}\) به آنها مسیر هست, باید در آرایه انداخته شده باشند. اما از \(v_{i}\) به \(v_{j}\) یک یال است(و بدیهتا مسیر هم هست), و \(v_{j}\) هنوز در آرایه انداخته نشده! که این خلاف لم ۱ می‌باشد. پس حکم باطل است و چنین \(i, j\) وجود ندارند!

پیچیدگی الگوریتم¶

پیچیدگی الگوریتم بالا, همان پیچیدگی الگوریتم \(DFS\) است یعنی \(O(n + m)\) که \(m, n\) به ترتیب تعداد راس ها و یال ها می‌باشند.

پیاده‌سازی الگوریتم¶

#include<bits/stdc++.h>

using namespace std;

const int MX = 5e5 + 5;

int n, m; /// Tedad ra's ha va yal ha
vector<int> gr[MX]; /// vector mojaverat
vector<int> topologic; /// topological sort
bool mark[MX];

void dfs(int v){
    mark[v] = 1;
    for(int u: gr[v]){
        if(!mark[u])
            dfs(u);
    }
    topologic.push_back(v); // in array yek topological sort baraie DAG ast!
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
                int v, u;
                cin >> v >> u; // Ra's ha 0-based hastand!
                gr[v].push_back(u);
    }
    // Graph vorodi bayad DAG bashad!
    for(int i = 0; i < n; i++)
                if(!mark[i])
                   dfs(i);
    // topological sort ro khoroji midahim!
    for(int i = 0; i < topologic.size(); i++)
          cout << topologic[i] << ' ';
    cout << endl;
    return 0;
}

پی نوشت۱ : دقت کنید که الگوریتم بالا در صورتی جواب درست را می‌دهد که گرافی بدون دور به عنوان ورودی بگیرد. بعد‌ها الگوریتم پیدا کردن دور در گراف جهت دار را شرح خواهیم داد.

پی نوشت۲ : در آخر ترتیب توپولوژیکی که به دست می‌اوریم, یال ها از راست به چپ هستند(به عبارتی یال ها از ایندکس بزرگ تر به ایندکس کوچک تر هستند. برعکس ترتیبی که در قضیه 3.3.2 آوردیم).