• Slides of Bipartite Matching Problem, Part I By Mohammad Hossein Bateni
• Slides of Bipartite Matching Problem, Part II By Mohammad Hossein Bateni
• Slides of Maximum Flow Problem By Mohammad Hossein Bateni
• Slides of Min-Cost Flow Problem By Mohammad Hossein Bateni
• کتاب بهینه‌سازی ترکیبیاتی و جبر خطی نوشته محمّد مهینی

• مقدمه
• مساله ی اول
• مساله ی دوم
• مساله ی سوم
• تمرین
• منبع

1) Add(i , x) : این عمل به Ai ، به اندازه x تا اضافه میکند.
2) Sum(i , j) : این عمل از شما می خواهد تا مجموع را در خروجی چاپ کنید.

• اگر i = j ، v هیچ بچه ای نخواهد داشت .
  
• اگر i != j ، v یک بچه ی چپ با زوج مرتب [ i , (i+j)/2 ] و یک بچه راست با زوج مرتب [ (i+j)/2 +1 , j] خواهد داشت.
  
برای مثال اگر n=4 ، درخت شرح داده شده در شکل شماره 1 آمده است

حال برگردیم به مساله ی اول :
اگر چنین Data Stcuture ای داشته باشیم ، جواب دادن سوال Sum(i , j) با O(log n) امکان پذیر است :
یک آرایه به نام s در نظر میگیریم که برای هرراس v در درخت با زوج [i , j]، s[v] برابراست با .
(برای راحتی کار ، از این به بعد ، مولفه ی اولِ زوج مرتبِ راس دلخواهِ v از درخت را با v.left و مولفه ی دوم آن را با v.right نشان میدهیم.)
if ( i <= v.left && v.right <= j) return s[v] return find_sum(v.left , i, j) + find_sum(v.right, i, j);

int find_sum(v, i, j)

    if (v.right < i || j < v.left)

        return 0
    if (i <= v.left && v.right <= j)

        return s[v]
    return find_sum(v.left, i, j) + find_sum(v.right, i, j)

find_sum(v,i,j) = find_sum(v.left,i,j) + find_sum(v.right,i,j)

void add(v, i, j)

    s[v] += x
    if (v.left == v.right )

        return
    if (v.left <= i && i <= (v.left+v.right)/2)

        add(v.left, i, x)
    else

        add(v.right, i, x)

1) Add(i , x) : این عمل Ai را مساوی Ai+x قرار میدهد. ( x مقداری مثبت است )
2) MaxOf(i , j) : این عمل از شما می خواهد تا عدد ماکسیمم بین Ai , Ai+1 , … , Aj را در خروجی چاپ کنید.

int maxof(v, i, j)

    if (v.right < i  ||  j < v.left)

        return 0
    if (i <= v.left && v.right <= j)

        return max[v]
    return maximum ( maxof(v.left, i, j) , maxof(v.right, i, j) )

void add(v, i, j)
    max[v] = maximum(max[v], A_i + x)

    if (v.right == v.left)
        /* here v.left is equal to i */

        A_i += x
        return
    if (v.left <= i && i <= (v.left+v.right)/2)

        add(v.left, i, x)
    else

        add(v.right, i, x)

int find_sum(v, i, j){
    if (v.right < i || j < v.left)  
        return 0

    if ( i <= v.left  &&  v.right <= j)

        return s[v]
    int eshterak = minimum(v.right, j) - maximum(v.left, i) + 1

    /* length of the interval [v.left, v.right] ^ [i, j] */
    return  find_sum(v.left , i, j) 
                 + find_sum(v.right, i, j) + all[v] * eshterak

}

void add(v, i, j, x){

    if (v.right < i || j < v.left)  
        return 
    if ( i <= v.left &&  v.right <= j)

        all[v] += x
    else {
        add(v.left, i, j, x)

        add(v.right, i, j, x)
    }

    s[v] = s[v.left] + s[v.right] + all[v]*(v.right - v.left + 1)
}

1. مساله ی 2 با این تفاوت که در تابع Add ، x میتواند منفی هم باشد.
2. مساله ی 311 از سایت http://acm.sgu.ru
3. مساله ی 325 از سایت http://acm.sgu.ru

• تعاریف
• مسئله بيشينه جريان
• برش ها در شبکه جريان
• الگوریتم
• کاربرد
• پياده سازي الگوريتم
• تمرین
• منبع

• شبکه جریان: شبکه هاي جريان مانند شبکه هاي توزيع آب, حمل و نقل, جريان برق و ... را مي توان مانند خيلي از موارد با گراف مدل سازي کرد. يک شبکه جريان شامل تعدادي گره (رئوس گراف) و ارتباط هاي بين بعضي از آنها (يالهاي گراف) است.
  اين ارتباط ها مانند لوله هاي آب مي توانند جريان را از يک رأس به رأس ديگر منتقل کنند. براي اين يالها محدوديتي وجود دارد که نشان دهنده حداکثر توان آن يال براي عبور جريان است. حداکثر جرياني که از آن يال مي گذرد را با اين محدوديت که آن را ظرفيت (capacity) مي ناميم نشان مي دهيم.
  در يک شبکه جريان به وضوح جريان در رأسي از بين نمي رود. يعني ميزان جريان ورودي يک رأس با جريان خروجي همان رأس برابر است. به اين خاصيت براي يک رأس بقاي جريان در آن رأس مي گويند.
• جريان در يک شبکه: يک شبکه را با يک گراف جهت دار که هر يال آن وزني دارد نشان داديم. منظور از يک جريان در يک شبکه, نسبت دادن اعدادي نامنفي به يالها به عنوان ميزان جريان عبوري از آن يال است که داراي خواصي که گفته شد باشند. يعني عددي که ما نسبت مي دهيم از ظرفيت يال بيشتر نشود و در رئوسي که مولد يا مصرف کننده جريان نيستند بقاي جريان را داشته باشيم.
  براي بيان دقيقتر مي توان اينطور گفت :
  گراف جهتدار G داراي مجموعه رئوس V ومجموعه يالهاي E است و تابع c روي مجموع يالها تعريف شده که c(e) نشان دهنده ظرفيت آن يال است.
  تابع u را در نظر بگيريد که u(e,v) نمايش دهنده وضعيت يال e و رأس v است. u(e,v) مي تواند سه مقدار 0 و 1 و -1 را به ترتيب در حالتهاي زير بگيرد :
  
  1. اگر v هيچ يک از دو سر e نباشد u(e,v) را 0 تعريف مي کنيم.
  2. اگر e از رأس v خارج شده باشد u(e,v) را 1 تعريف مي کنيم.
  3. اگر e به رأس v داخل شده باشد u(e,v) را -1 تعريف مي کنيم.
  
  در اين حالت يک جريان, تابع f روي يالها است که براي هر يال e داشته باشيم و براي هر رأس v که مولد يا مصرف کننده نيست داشته باشيم (حاصل جمع دقيقاً برابر ميزان جريان خروجي منهاي ميزان جريان ورودي است)
  براي مثال شکل زير جرياني در يک شبکه را نشان مي دهد. رئوس مشخص شده مولد يا مصرف کننده هستند و قانون بقاي جريان براي آنها صادق نيست. اعداد کمرنگ روي يالها نمايش دهنده جريان عبوري از آن يال و اعداد پررنگ نمايش دهنده ظرفيت آن يال است.
  
  
  

در يک جوي آب حداکثر جريان عبوري از جوي با کمترين سطح مقطع جوي متناسب است.

• f اي که به اين صورت ساخته مي شود يک جريان است.
• جريان خروجي ازs در f برابر است
• اگر (S,T) يک برش باشد آنوقت

S را تمام رئوسي قرار دهيد که از s به آنها مسيري با يالهاي داراي ظرفيت مثبت وجود دارد. T را هم بقيه رئوس بگيريد.

maxflow(Graph G, Cost c, source s, sink t)

    for each edge(x, y) in E(G) do

        F[x, y] := 0
        F[y, x] := 0

    while there is a positive capacity path P in G from s to t do
        k := { min c(e) | for every edge e in P }

        for each edge(x, y) in P do
            F[x, y] := F[x, y] + k
            F[y, x] := F[y, x] - k
            F[x, y] := F[x, y] - k
            F[y, x] := F[y, x] + k

1. ثابت کنيد در مراحل انجام الگوريتم مقدار F(x,y)+c(x,y) براي دو رأس x و y تغير نمي کند.
2. ثابت کنيد اگر ظرفيت ها اعدادي صحيح باشند الگوريتم در |f*| مرحله که f* جريان بيشينه است پايان مي پذيرد. با استفاده از اين موضوع و يافتن کران خوبي براي |f*| (از روي برشي که در آن S فقط تک رأس s را دارد) نشان دهيد که الگوريتم براي تطابق بيشينه در پايان مي پذيرد.
3. * فرض کنيد ظرفيت يالها بتواند بينهايت شود, نشان دهيد اگر جريان بيشينه بينهايت نشود همچنان الگوريتم پايان پذير است. از اين موضوع استفاده کنيد و الگوريتم را طوري تغيير دهيد که در صورتي که جريان بيشينه بينهايت شود در متناهي مرحله به ما اطلاع دهد که جريان بيشينه بينهايت است و در غير اينصورت به ما جريان بيشينه را برگرداند.
4. * نشان دهيد وقتي شبکه ما چند يال از يک رأس به رأس ديگر دارد با حالتي که دقيقاً يک يال از هر رأس به رأس ديگر وجود دارد معادل است و از آن نتيجه بگيريد که مي توان الگوريتم را در زمان اجراي پياده سازي کرد.
5. * ثابت کنيد که مسأله پيدا کردن جريان بيشينه در حالتي که چند رأس چشمه و چند رأس چاه وجود دارند با حالتي که فقط يک چاه و يک چشمه وجود دارند معادل است (راهنمايي : يک چشمه را به بقيه وصل کنيد و ...)
6. * نشان دهيد که مسأله وقتي که براي جريان عبوري از هر رأس نيز ظرفيت دارد با حالتي عادي معادل است. (راهنمايي : هر رأس را دو تا کنيد, يکي رأس ورودي و ديگري رأس خروجي)
7. ** نشان دهيد که عدد همبندي يالي يک گراف را مي توان با چند بار استفاده از maximum flow حل کرد (راهنمايي : تعداد يالهاي لازم براي حذف کردن براي اينکه از رأس ثابت u به رأسي ديگر مسير پيدا نشود را با استفاده از الگوريتم روي گراف به اضافه يک رأس مجازي t پيدا کنيد)
8. اگر تعداد يالها زياد باشد بايد آنها در ليست مجاورت نگهداري کنيم. در اين حالت بگوييد بايد به چه نکاتي در پياده سازي توجه کرد. (راهنمايي : يالهاي مسير معکوس را چگونه پيدا مي کنيد؟)
9. ثابت کنيد اگر در شبکه اي ظرفيت هر يال 0 يا 1 باشد, جريان بيشينه اي وجود دارد که جمع تعدادي مسير مجزاي يالي است.
10. * نشان دهيد کمينه تعداد يالهاي لازم که اگر آنها را حذف کنيم از رأس x به رأس y در گراف مسيري وجود نداشته باشد با حداکثر تعداد مسيرهاي مجزاي يالي بين x و y برابر است.
    
11. *** يک پوشش مسيري از گراف G تعدادي مسير مجزاي رأسي در G است که تمام رئوس G در آنها ظاهر شده اند. ثابت کنيد که پوشش مسيري با تعداد مسيرهاي کمينه را مي توان در صورتي که گراف يک DAG باشد را با maximum flow پيدا کرد. (راهنمايي : گراف دو بخشي بسازيد که هر بخش آن رئوس G باشند و يالهاي آن از x در بخش بالا به y در بخش پايين است اگر در گراف G از x به y يال وجود داشته باشد.) نشان دهيد که اين الگوريتم براي گراف هاي داراي دور کار نمي کند.
12. **** فرض کنيد روي جريان عبوري از يک يال يک کران پايين نيز قرار دهيم. با ديدن تعريف F از روي f و رابطه نشان دهيد که چطور شبکه اي با اين خاصيت بسازيم (راهنمايي: از ظرفيت هاي منفي استفاده کنيد). مي خواهيم اين مسأله را که جرياني در شبکه با ظرفيت هاي منفي پيدا کنيم را حل کنيم. (در اين مسأله s و t اي وجود ندارند) نشان دهيد که مسأله پيدا کردن جريان بيشينه با استفاده مکرر از مسأله بالا قابل حل است (راهنمايي : از t به s يک يال با ظرفيت بينهايت قرار دهيد و روي ميزان جريان جستجوي دودويي را انجام دهيد) فرض کنيد گراف مسأله جديد G باشد. گراف H را اينطور بسازيد که و ظرفيت يالهاي H را که با d نمايش مي دهيم را اينطور تعريف مي کنيم که براي هر u و v در V(G) و و که در آن منظور از c(X,Y) که X و Y دو زيرمجموعه V(G) هستند برابر تعريف مي شود. نشان دهيد که يک جريان در G وجود دارد اگر و فقط اگر تمامي يالهاي H نامنفي باشند و در جريان بيشينه H تمام يالهاي ورودي t اشباع شده باشند (يعني جريان عبوري از آنها با ظرفيتشان يکي باشد) در ضمن از روي اين جريان براي H جرياني براي G بسازيد. نشان دهيد که اگر G خود داراي چشمه و چاه باشد مي توان با دو بار انجام maximum flow جريان بيشينه را در صورت وجود در G پيدا کرد (با فرض اينکه يالها منفي هم مي توانند باشند)

• ورودی به الگوریتم ها
• انواع مختلف الگوريتمها براي حل مسأله جريان بيشينه
• مراحل مختلف اجرای الگوریتم

• تعاریف
• مقدمه
• قضیه ۱
• الگوریتم
• تحلیل
• کاربرد
• مجموعه مستقل
• تمرین
• منبع

• گراف دوبخشی: گرافی است که راس‌هایش را بتوان به دو مجموعه‌ افراز کرد، به طوری که برای هر یالِ u، uv و v در دو مجموعه‌ی متفاوت باشند.
• تطابق: یک تطابق در گراف بدون جهت G عبارت است از مجموعه‌ای از یال‌های گراف به طوری که هر رأس حداکثر به یکی از یال‌های مجموعه متصل باشد. رأسی که به یکی از یال‌های تطابق متصل باشد را «آلوده» می‌نامیم. اگر یک تطابق تمام رئوس گراف را آلوده کند، آن تطابق را یک «تطابق کامل» می‌نامیم.
• تطابق ماکسیمم: تطابقی است که بیشترین تعداد یال را در گراف داشته باشد. هم‌چنین تطابق ماکسیمال تطابقی است که نتوان یالی از یال‌های گراف را به آن اضافه کرد به طوری که یک تطابق بزرگتر بوجود بیاید. بدیهی است که یک تطابق ماکسیمال ممکن است ماکسیمم نباشد.
• مسیر متناوب: مسیری است که یال‌هایش یکی در میان در تطابق قرار داشته باشند.
• مسیر افزایشی: مسیری متناوب که رئوس اول و آخر آن در تطابق نباشند را یک مسیر افزایشی می گویند.

• ورودی: یک گراف دوبخشی با افراز X و Y از رأس‌ها و یک تطابق M در G و مجموعه‌ی U از همه رأس‌های آلوده نشده توسط M در X.
• ارزش‌دهی آغازی: S = U و T = Ø.
• تکرار: برای هر راس در داخل S تمام مسیرهای افزایشی که از راس مورد نظر شروع میشوند را در نظر می گیریم. اگر راسی در بخش X در یکی از این مسیرهای افزایشی قرار داشت آن راس را به مجموعه S اضافه می کنیم. همچنین اگر راسی در بخش Y در یکی از این مسیرهای افزایشی قرار داشته باشد آن راس را نیز به مجموعه T اضافه می کنیم. برای راس های S آنقدر این کار را انجام می دهیم تا هیچ راسی را نتوان به S یا T اضافه کرد.
  حال اگر در مجموعه T راسی باشد که آلوده نشده است در این صورت یک مسیر افزایشی پیدا کرده ایم. زیرا از یکی از راس های غیر آلوده که در مجموعه U قرار داشت به یک راس غیر آلوده در بخش دیگر مسیری متناوب پیدا شده است. چون ابتدا و انتهای این مسیر راس هایی غیر آلوده هستند پس این مسیر یک مسیر افزایشی است.
  

1. ثابت کنید در گراف G با n راس که دارای هیچ راس تنهایی نمی باشد اندازه تطابق ماکسیمم بعلاوه اندازه پوشش یالی مینیمم برابر n است.
2. ثابت کنید در هر گراف دوبخشی G اندازه بزرگترین تطابق برابر اندازه کوچکترین پوشش راسی می باشد.
3. ثابت کنید در هر گراف دوبخشی G اندازه بزرگترین مجموعه مستقل برابر اندازه کوچکترین پوشش یالی می باشد.
4. ثابت کنید اندازه کوچکترین پوشش راسی بعلاوه اندازه کوچکترین پوشش یالی برابر n می باشد.
5. ثابت کنید اندازه بزرگترین مجموعه مستقل در گراف دوبخشی برابر n ( تعداد رئوس گراف ) منها اندازه تطابق ماکسیمم در گراف می باشد.
6. ثابت کنید روشی که برای پیدا کردن بزرگترین مجموعه مستقل در گراف دوبخشی داده شده است این مجموعه را پیدا می کند.
7. ( مسئله ازدواج پایدار ) فرض کنید n مرد و n زن می خواهند ازدواج کنند به صورتی که هر مرد لیستی اولویت بندی شده از زن هایی دارد که می خواهد با آنها ازدواج کند ( می توانید فرض کنید هر مرد به زن ها اعداد 1 تا n را که نشانه اولویت آنهاست نسبت می دهد ). همچنین زن ها نیز لیسیت از اولویت های خود مانند زن ها دارند. حال می خواهیم ترتیبی از ازدواج را بین این n مرد و n زن برقرار کنیم به طوری که هیچ زن و مردی نباشند که همدیگر را به همسرهای کنونی خود ترجیح دهند. الگوریتمی برای انجام این کار بدست آورید.

• پرسش: نتایج مرحله‌ی اوّل شانزدهمین دوره (سال ۱۳۸۵) چه زمانی و چگونه اعلام می‌شود؟
• پاسخ: نیمه‌ی اسفندماه و از طریق سایت باشگاه و احتمالاً یکی از روزنامه‌های کثیرالانتشار.

• پرسش: حداقل امتیاز لازم برای قبولی در مرحله‌ی اوّل چند نمره است؟
• پاسخ: بسته به عمل‌کرد سایر شرکت‌کنندگان و درجه‌ی سختی سؤالات این حدنصاب متغیر بوده و میزان از پیش تعیین شده‌ای نمی‌باشد. با این حال، پیش‌بینی می‌شود این میزان کمتر از نصف حداکثر امتیاز قابل اکتساب باشد.

• پرسش: در مورد دوره‌ی نوروزی: لطفاً مسائی واکنشی (دسته‌ی دوّم) را بیشتر توضیح دهید و اگر ممکن است یک مثال بزنید.
• پاسخ: به عنوان مثال این سوال را که در المپیاد جهانی ۲۰۰۰ مطرح شده است، در نظر بگیرید: به شما یک فایل از نوع median.o و یک فایل از نوع median.h داده می‌شود که این توابع را دارند:

  int get_n();
  int median(int i, int j, int k);
  
  void report(int m);
  

  مسئله به این صورت است که ما یک آرایه‌ی حداکثر ۱۵۰۰ عضوی داریم که شما باید اندیس عنصر میانه‌ی آن را پیدا کنید. برای این کار اگر تابع اول را صدا کنید اندازه‌ی آرایه را دریافت خواهید کرد؛ با اجرای تابع دوم اندیس عنصر میانه ی سه عنصری که اندیس آن را به تابع داده اید را دریافت خواهید کرد (یکی از سه پارامتر تابع)؛ و با اجرای تابع سوم اندیس جواب را اعلام خواهید کرد و برنامه ی شما متوقف خواهد شد. بدیهی است که اجرای هر یک از سه تابع با پارامترهای بی معنا باعث گرفتن نمره‌ی ۰ از تست مورد نظر خواهد شد، در ضمن تعداد اجراهای تابع دوم نباید از ۷۰۰ بار بیشتر باشد.
  شما باید با فرض این‌که این توابع در median.o (که یک object file است)، پیاده‌سازی شده‌اند (و البته کد آن‌ها در دسترس نیست)، فایل median.h را (که یک header file است) در ابتدای برنامه‌ی خودتان include کرده و به هنگام اجرا نیز با لینک‌کردن median.o در دستور کامپایل، برنامه‌ی خود را تست کنید.