شناسایی کمر گراف

کمر گراف، طول کوتاه‌ترین دور در گراف است. برای مثال کمر گرافی که تنها شامل مثلث است، سه است؛ کمر گرافی که یک مربع با قطر‌هایش است نیز ۳ است. توجه کنید اگر گراف هیچ دوری نداشته باشد، کمر گراف را ۰ فرض می‌کنیم.

برای راحتی، مسئله را می‌توانیم به چند حالت تقسیم کنیم:

• گراف‌های جهت‌دار: در این‌جا پیدا کردن دور کمی متفاوت است و هر دوری حتما در یک مؤلفه قویا همبند است. پس ابتدا باید مؤلفه‌های قویا همبند را پیدا کرد و سپس برای هر مؤلفه کمر را پیدا کرد.
• گراف‌های وزن‌دار: در این حالت تعریف طول دور تعداد یال‌ها نیست بلکه وزن یال‌های آن دور است؛ اگر گراف یال با وزن منفی داشته باشد، چه بسا ممکن است دوری با طول منفی پیدا کنیم و هرچه روی آن حرکت کنیم طول آن کمتر شود! در این حالت روشی برای پیدا کردن دور منفی وجود دارد. اگر دور منفی نداشته باشیم نیز باید از الگوریتم هایی که روی گراف‌های وزن‌دار اجرا می‌شوند استفاده کرد مانند فلوید که همه کوتاه‌ترین مسیر‌ها (از جمله کوتاه‌ترین مسیر هر رأس به خودش) را پیدا می‌کند.
• گراف‌های بدون‌جهت و بی‌وزن: در اینجا به بررسی این حالت می‌پردازیم و با استفاده از جست‌و‌جوی سطح‌اول مسئله را حل می‌کنیم.

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

فرض کنید کمر گراف شامل رأس $v$ باشد. پیمایشی که ریشه آن $v$ بوده را در نظر بگیرید. اولین دوری که پیدا می‌کنیم، طولش برابر کمر است؛ زیرا قطعا به رأس روبرویی (رأسی که فاصله اش از دو طرف برابر باشد) $v$ از دو مسیر مختلف می‌رسیم و چون $bfs$ همه مسیر‌ها را بطور موازی جلو می‌برد، پس این دور را در ارتفاع نصف کمر (اگر فرد بود، سقف می‌گیریم) پیدا می‌کنیم یا دوری دیگر را که طول برابری دارد. پس به ازای هر رأسی که عضو کمر باشد، طول دور پیدا شده با پیمایش از آن رأس، برابر کمر است.

توجه کنید که اگر در مرحله‌ای طول دور کمینه پیدا شده برابر $d$ باشد، آنگاه اگر در پیمایشمان به ارتفاع بیش از $d/2$ برسیم پس حتما دوری که پیدا می‌شود بیشتر از $d$ می‌شود بنابراین کمر از این رأس نمی‌گذرد و پیمایش را متوقف کرده و از رأس بعدی آغاز می‌کنیم.

فرض کنید $V$ تعداد رأس‌ها و $E$ تعداد یال‌ها است. چون از هر رأسی یک‌بار جست‌و‌جوی سطح‌اول می‌زنیم و هزینه هر جست‌وجو برابر $O(V + E)$ است، پس هزینه کل از $O(V * (V + E))$ است. توجه کنید که پیدا کردن کمینه از $O(V)$ است و تأثیری در پیچیدگی کل ندارد.

minimum_cylce.cpp

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
 
using namespace std;
const int MAXN = 100 * 1000 + 10;
const int INF = 1<<30;     //   بینهایت
 
bool mark[MAXN];
vector<int> adj[MAXN];      //  لیست مجاورت رأس‌ها
int depth[MAXN];            //  ارتفاع هر رأس
int parent[MAXN];           //  پدر هر رأس
 
int n;       //     تعداد رأس ها توجه کنید شماره رأس‌ها از ۰ شروع می‌شود
int m;       //     تعداد یال‌ها
 
int bfs(int v, int max_depth) {
    queue<int> q;                // صفی که رأس‌ها در آن قرار می‌گیریند
    memset(depth, -1, sizeof(depth));
    memset(mark, 0, sizeof(mark));
    mark[v] = 1;
    depth[v] = 0;
    q.push(v);
 
    while(q.size()) {
        v = q.front();
        q.pop();
 
	if (depth[v] == max_depth)     // دوری که در آینده پیدا می‌شود نمی‌تواند کمینه باشد
	    return INF;
 
        for(unsigned int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
 
            if (mark[u] == 1 && u != parent[v])      // پس دور پیدا شده است
                return (depth[v]+1) + depth[u];      // ارتفاع قبلی پیدا شده برای این رأس + ارتفاع الان پیدا شده
 
            mark[u] = 1;
            q.push(u);
            parent[u] = v;
            depth[u] = depth[v] + 1;      // ارتفاع همسایه یک واحد بیشتر از ارتفاع این رأس است
        }
 
    }
 
    return INF;
}
 
int find_min_cycle()
{
    int dist = INF;              // تقریبا بینهایت برای اینکه در کمینه تاثیری نگذارد و دور را نگه می‌دارد
 
    for (int i = 0; i < n; i++)
        dist = min(dist, bfs(i, dist/2));
 
    return dist;
}
 
 
void input()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        adj[--v].push_back(--u);
        adj[u].push_back(v);
    }
}
 
int main()
{
    input();   
    cout << find_min_cycle() << endl;
}