Как найти дуги минимального разреза

96

8.1. Процедура “пометок вершин “

Начальное состояние: ¾ все вершины не имеют пометок.

Вершине s приписывается пометка.

Всем вершинам xi Î {Gs}, для которых дуга (s, xi) не насыщена:

¾

с si > j si присваиваются пометки.

 Всем вершинам xk Î {G xi}, для которых дуга (xi , xk,) не насыщена:

¾

сij > j ij присваиваются пометки.

Входе присвоения пометок вершинам сети возможны две

ситуации:¾

1. Удалось присвоить пометку вершине t, из чего следует, что в сети есть путь от вершины s к вершине t, все дуги которого не насыщены. Следовательно, поток на сети может быть увеличен за счёт его увеличения на пути s,…, t (с помощью рассмотренного выше алгоритма).

2. Не удалось присвоить пометку вершине t. Следовательно, на сети получен максимальный поток и, для его вычисления, возможно, построить минимальный разрез.

На рисунке 10.17 приведён результат пометок вершин для рассматриваемой сети:

Слайд 1

Потоки в сетях
Теорема о максимальном потоке
и минимальном разрезе
Лекция 6

Слайд 2

Сеть
•
Ориентированный граф G с пропускными
способностями дуг u

Слайд 3

Поток
•
Определение 6 .1. Дан орграф G с

Слайд 4

s-t- Поток
•
Да на сеть ( G , u ,

Слайд 5

Задача « Максимальный Поток »
•
Дано : Сеть (

Слайд 6

s – t- Разрез
•
s-t – разрез в графе

Слайд 7

s – t – Поток и s –

Слайд 8

Доказательство (а)   
 
 
 
 
 
 
 
 
 
 
 
.

Слайд 9

s – t – Поток и s –

Слайд 10

Обратные дуги и остаточные
пропускные способности
•
Определение 6

Слайд 11

Остаточный граф
S t5
5 5
514
3 25
1
S t1
2 5
314
3
2G
G
f

Слайд 12

Увеличивающий Путь
Даны поток f и

Слайд 13

Увеличивающий Путь
S t5
5 5
514
3 25
1
S t1
2 5
314
3
2G
G
f
S
t5
5 5
515
3 35

Слайд 14

Алгоритм Форда-Фалкерсона
Input: Сеть ( G, u, s, t ).
Output:

Слайд 15

Замечание
•
Найти увеличивающий путь легко (любой

Слайд 16

Пример c бесконечным числом итераций
( все линии представляют ребра,

Слайд 17

Упражнение 6.1
•
Показать, что для сети из предыдущего
примера алгоритм Форда-Фалкерсона

Слайд 18

Целочисленный пример c
экспоненциальным числом итераций
S tR
R R
R1
2 R итераций

Слайд 19

Характеризация максимального
потока
Теорема 6 . 4
s-t-

Слайд 20

Доказательство
•
Пусть в G
f не существует f –

Слайд 21

Замечание
•
В частности, из доказательства следует, что
каждому максимальному потоку соответствует

Слайд 22

Максимальный поток и
минимальный разрез

Теорема

Слайд 23

Теорема о целочисленном потоке
Следствие 6 .

Слайд 24

Упражнение 6. 2
•
По c троить пример сети, в которой
вместимости

Слайд 25

Теорема о Декомпозиции Потока
Теорема 6 . 7 ( Фалкерсон

Слайд 26

Доказательство
•
Построим P , C и w индукцией по

Слайд 27

Иллюстрация доказательства
ts
v
0 w
0 w
1 w
2
w
3
ts
v
0 w
0 w
1 w
2
w
3v
1
v
2

Слайд 28

Доказательство
•
Пусть P будет цикл или путь, найденный в

Слайд 29

Теорема о Декомпозиции Потока
Теорема 6 . 7 ( Фалкерсон

Слайд 30

Упражнение 6.2
•
Доказать следующую теорему
Теорема (Хоффман 1960)
Задан орграф G

Чтобы скачать презентацию – поделитесь ей с друзьями с помощью
социальных кнопок.

#ifndef DEF_H
#define DEF_H
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
#include <iterator>
#include <functional>

using namespace std;

extern int reverseID[];
extern vector<int> id;
extern vector< vector<int> > weight, edge;
extern map<int, string> name;
extern int V, E;

void read_data();
#endif

#include "definitions.h"

int reverseID[3000];
vector<int> id; // origin ID of characters
vector< vector<int> > weight; // weights of edges
vector< vector<int> > edge; // the graph's edges
map<int, string> name; // names of characters
int V, E; // amount of vertices and edges

void read_data() {
    freopen("input.in", "r", stdin); // read from the input file

    cin >> V >> E;
  
    id.resize(V);
    weight.resize(V);
    edge.resize(V);

    int u;
    char s[100];
    for (int i = 0; i < V; i++) { // read the names
        scanf("%d %[^n]", &u, s);
        name[i] = string(s);
        id[i] = u; // origin ID by assigned ID
        reverseID[u] = i; // assigned ID by origin ID
    }

    int a, b, w;
    for (int i = 0; i < E; i++) { // read the edges and weights
        cin >> a >> b >> w;
        edge[reverseID[a]].push_back(reverseID[b]);
        edge[reverseID[b]].push_back(reverseID[a]);
        weight[reverseID[a]].push_back(w);
        weight[reverseID[b]].push_back(w);
    }
}

#include "definitions.h"
#include "degree.h"
#include "dfsbfs.h"
#include "bridges_articulations.h"
#include "cliques.h"
#include "spanning.h"
#include "cut.h"

int main() {
    read_data();

    degree();
    count_components();
    calculate_diameter();
    find_cliques();
    get_spanning_tree();
    find_bridges_and_articulations();
    find_cut();
}

#include "definitions.h"

void degree() {
    freopen("degree.txt", "w", stdout); // output file

    vector< pair<int,int> > degree(V);
    for (int i = 0; i < V; i++) {
        degree[i] = make_pair(edge[i].size(), i);
    }

    stable_sort(degree.begin(), degree.end());

    for (int i = V-1; i >= 0; i--) {
        cout << name[degree[i].second] << ": " << degree[i].first << endl;
    }
}

#include "definitions.h"

vector<bool> useddfs;
vector<int> comp;

void dfs(int u) {
    useddfs[u] = true;
    comp.push_back(u);
    for (vector<int>::iterator i = edge[u].begin(); i != edge[u].end(); i++)
        if (!useddfs[*i])
            dfs(*i);
}

void count_components() {
    freopen("components.txt", "w", stdout); // output file

    int comp_num = 0;
    useddfs.resize(V, false);
    for (int i = 0; i < V; i++) {
        if (!useddfs[i]) {
            comp.clear();
            dfs(i);
            comp_num++;
        }
    }
    cout << comp_num;
}

#include "definitions.h"

vector<bool> usedbfs;

void bfs(int u, vector<int> &distance, vector<int> &path) {
    queue<int> q;
    q.push(u);
    usedbfs[u] = true;
    path[u] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (vector<int>::iterator i = edge[u].begin(); i != edge[u].end(); i++) {
            int to = *i;
            if (!usedbfs[to]) {
                usedbfs[to] = true;
                q.push(to);
                distance[to] = distance[u] + 1;
                path[to] = u;
            }
        }
    }
}

void calculate_diameter() {
    freopen("diameter.txt", "w", stdout); // output file

    int diameter = 0;
    int current_max = 0;
    double average_max = 0;
    double average_average = 0;
    vector< vector<int> > distribution(V, vector<int> (0));
    vector< vector<int> > max_path;
    vector<int> farthest_node;
    for (int i = 0; i < V; i++) {
        vector<int> distance_to(V, 0);
        vector<int> path(V,-1);
        usedbfs.clear();
        usedbfs.resize(V, false);
        bfs(i, distance_to, path);
        current_max = 0;
        for (int j = 0; j < V; j++) {
            average_average += distance_to[j];

            if (distance_to[j] > current_max)
                current_max = distance_to[j];

            if (distance_to[j] > diameter) {
                diameter = distance_to[j];
                farthest_node.clear();
                max_path.clear();
                max_path.push_back(path);
                farthest_node.push_back(j);
            } else if (distance_to[j] == diameter){
                max_path.push_back(path);
                farthest_node.push_back(j);
            }
        }
        average_max += current_max;
        distribution[current_max].push_back(i);
    }
    average_max /= V;
    average_average /= V*V;

    cout << "Diameter: " << diameter << endl;
    cout << "Average path: " << average_average << endl;
    cout << "Average farthest path: " << average_max << endl;

    vector < vector<int> > farthest_path;    

    for (int i = 0; i < farthest_node.size(); i++) {
        farthest_path.push_back(vector<int>());
        for (int u = farthest_node[i]; u != -1; u = max_path[i][u])
            farthest_path[i].push_back(u);
    }

    cout << "Farthest paths:" << endl;
    for (int i = 0; i < farthest_path.size(); i++) {
        cout << i+1 << ": ";
        for (vector<int>::iterator j = farthest_path[i].begin(); j != farthest_path[i].end(); j++)
            cout << name[*j] << ". ";
        cout << endl;
    }

    int minimum = V;
    cout << "Farthest paths distribution:" << endl;
    for (int i = 0; i <= diameter; i++) {
        if (distribution[i].size() != 0 && i < minimum)
            minimum = i;

        cout << i << ": " << distribution[i].size() << endl;
    }

    cout << "Characters with minimum farthest path:" << endl;
    for (vector<int>::iterator i = distribution[minimum].begin(); i != distribution[minimum].end(); i++) {
        cout << name[*i] << endl;
    }
}

#include "definitions.h"

vector < vector<int> > cliques;

bool compare_vectors_by_size(const vector<int> &i, const vector<int> &j)
{
    return (i.size() > j.size());
}

void bron_kerbosch(set <int> R, set <int> P, set <int> X) { // where R is probable clique, P - possible vertices in clique, X - exluded vertices
    if (P.size() == 0 && X.size() == 0) { // R is maximal clique
        cliques.push_back(vector<int>(0));
        for (set<int>::iterator i = R.begin(); i != R.end(); i++) {
            cliques.back().push_back(*i);
        }
    }
    else {
        set <int> foriterate = P;
        for (set<int>::iterator i = foriterate.begin(); i != foriterate.end(); i++) {
            set <int> newR;
            set <int> newP;
            set <int> newX;

            newR = R;
            newR.insert(*i);

            set_intersection(P.begin(), P.end(), edge[*i].begin(), edge[*i].end(), inserter(newP, newP.begin()));

            set_intersection(X.begin(), X.end(), edge[*i].begin(), edge[*i].end(), inserter(newX, newX.begin()));

            bron_kerbosch(newR, newP, newX);

            P.erase(*i);
            X.insert(*i);
        }
    }
}

void find_cliques() {
    freopen("cliques.txt", "w", stdout); // output file

    set <int> P;
    for (int i = 0; i < V; i++) {
        P.insert(i);
        stable_sort(edge[i].begin(), edge[i].end());
    }
    
    bron_kerbosch(set<int>(), P, set<int>());

    stable_sort(cliques.begin(), cliques.end(), compare_vectors_by_size);

    cout << "Distribution:" << endl;
    int max_size = 0;
    int max_counter = 0;
    for (int i = cliques.size()-1; i >= 0 ; i--) {
        if (cliques[i].size() > max_size) {
            if (max_counter > 0) {
                cout << max_size << ": " << max_counter << endl;
            }
            max_size = cliques[i].size();
            max_counter = 0;
        }

        max_counter++;
    }
    if (max_counter > 0) {
        cout << max_size << ": " << max_counter << endl;
    }

    cout << "Cliques:" << endl;
    for (int i = 0; i < cliques.size(); i++) {
        cout << i + 1 << "(" << cliques[i].size() << "): ";
        for (int j = 0; j < cliques[i].size(); j++) {
            cout << name[cliques[i][j]] << ". ";
        }
        cout << endl;
    }
}

#include "definitions.h"

vector<int> p;

int dsu_get(int v) {
    return (v == p[v]) ? v : (p[v] = dsu_get(p[v]));
}

void dsu_unite(int u, int v) {
    u = dsu_get(u);
    v = dsu_get(v);

    if (rand() & 1)
        swap(u, v);

    if (u != v)
        p[u] = v;
}


void get_spanning_tree() {
    freopen("spanning.txt", "w", stdout); // output file

    vector < pair < int, pair<int, int> > > edges_weights, result;

    vector < vector<bool> > used;
    for (int i = 0; i < V; i++) {
        used.push_back(vector<bool>(V, false));
    }

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
            int cur_v = edge[i][j];
            if (!used[i][cur_v]) {
                edges_weights.push_back(make_pair(weight[i][j], make_pair(i, cur_v)));
                used[i][cur_v] = true;
                used[cur_v][i] = true;
            }
        }
    }

    sort(edges_weights.begin(), edges_weights.end(), greater< pair < int, pair<int, int> > >());

    for (int i = 0; i < V; i++) {
        p.push_back(i);
    }

    for (int i = 0; i < E; i++) {
        int u = edges_weights[i].second.first;
        int v = edges_weights[i].second.second;
        int w = edges_weights[i].first;

        if (dsu_get(u) != dsu_get(v)) {
            result.push_back(edges_weights[i]);
            dsu_unite(u, v);
        }
    }

    for (vector < pair < int, pair<int, int> > >::iterator i = result.begin(); i != result.end(); i++) {
        cout << id[(i->second).first] << " " << id[(i->second).second] << " " << i->first << endl;
    }
}

#include "definitions.h"

vector<bool> used, usedcnt;
int timer = 0;
vector<int> tin, fout, articulations;
vector < pair<int,int> > bridges;

int count_rec(int v, int skip) {
    int cnt = 1;
    usedcnt[v] = true;

    for (int i = 0; i < edge[v].size(); i++) {
        int to = edge[v][i];

        if(to == skip || usedcnt[to]) 
            continue;

        cnt += count_rec(to, skip);
    }
    
    return cnt;
}

int count_from(int v, int skip, bool clean = true){
    usedcnt.resize(V, false);

    if (clean) {
        for (int i = 0; i < usedcnt.size(); i++)
            usedcnt[i] = false;
    }
         
    return count_rec(v, skip);
}

void dfs(int v, int prev = -1) {
    used[v] = true;
    tin[v] = fout[v] = timer++;

    int root_calls = 0;
    bool in_ar_list = false;
    for (int i = 0; i < edge[v].size(); i++) {
        int to = edge[v][i];

        if (to == prev)  continue;

        if (used[to])
            fout[v] = min(fout[v], tin[to]);
        else {
            dfs(to, v);
            fout[v] = min(fout[v], fout[to]);

            if (fout[to] > tin[v]) {
                bridges.push_back(make_pair(v, to));
            }
            
            if (fout[to] >= tin[v] && prev != -1 && !in_ar_list) {
                articulations.push_back(v);
                in_ar_list = true;
            }
            
            root_calls++;
        }
    }
    
	if (prev == -1 && root_calls > 1)
		articulations.push_back(v);
}

void find_bridges_and_articulations() {
    freopen("bridges_and_articulations.txt", "w", stdout); // output file

    used.resize(V, false);
    tin.resize(V);
    fout.resize(V);

    for (int i = 0; i < V; i++)
        if (!used[i])
            dfs(i);
    
    cout << "Bridges:" << endl;
    for (int i = 0; i < bridges.size(); i++) {
        cout << name[bridges[i].first] << " (" << count_from(bridges[i].first, bridges[i].second) << ") - " << name[bridges[i].second] << " (" << count_from(bridges[i].second, bridges[i].first) <<")" << endl;
    }
    
    
    cout << endl << "Articulation points:" << endl;  
    for (int i = 0; i < articulations.size(); i++) {
        int cur = articulations[i];
        cout << name[cur];
        
        for (int i = 0; i < usedcnt.size(); i++)
            usedcnt[i] = false;
            
        for (int j = 0; j < edge[cur].size(); j++) {
            if (!usedcnt[edge[cur][j]]) {
                int comp_size = count_from(edge[cur][j], cur, false); 
                cout << " (" << comp_size << ")";
            }
        }
        cout << endl;
    }
}

#include "definitions.h"

const int INF = 1000000000;

struct edge_s{
    int a, b, c, flow; // a->b, c-capacity, flow=0
    edge_s(int a, int b, int c, int flow) : a(a), b(b), c(c), flow(flow) {}
};

vector< pair<int, int> > top_degree;
vector< pair<int, int> > top_flow;
vector<int> dis;
vector<int> ptr;
vector<edge_s> edgelist;
vector< vector<int> > edges_dup;

bool compare_pairs_by_second(const pair<int, int> &i, const pair<int, int> &j)
{
    return (i.second > j.second);
}

bool bfs_dinic(int s, int t) {
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    
    while (!q.empty() && dis[t] == -1) {
        int v = q.front();
        q.pop();
        
        for (int i = 0; i < edges_dup[v].size(); i++) {
            int ind = edges_dup[v][i],
            next = edgelist[ind].b;
            
            if (dis[next] == -1 && edgelist[ind].flow < edgelist[ind].c) {
                q.push(next);
                dis[next] = dis[v] + 1;
            }
        }
    }
    
    return dis[t] != -1;
}

int dfs_dinic(int v, int t, int flow) {
    if (!flow) {
        return 0;
    }
    
    if (v == t) {
        return flow;
    }
    
    for (; ptr[v] < (int) edges_dup[v].size(); ptr[v]++) {
        int ind = edges_dup[v][ptr[v]];
        int next = edgelist[ind].b;
        
        if (dis[next] != dis[v] + 1) {
            continue;
        }
        
        int pushed = dfs_dinic(next, t, min(flow, edgelist[ind].c - edgelist[ind].flow));
        
        if (pushed) {
            edgelist[ind].flow += pushed;
            edgelist[ind ^ 1].flow -= pushed;
            return pushed;
        }
    }
    
    return 0;
}

long long dinic_flow(int s, int t) {
    long long flow = 0;
     
    while (true) {
        fill(dis.begin(), dis.end(), -1);
        
        if (!bfs_dinic(s, t)) {
            break;
        }
        
        fill(ptr.begin(), ptr.end(), 0);
        
        while (int pushed = dfs_dinic(s, t, INF)) {
            flow += pushed;
        }
    }
    return flow;
}

void dinic_addedge(int a, int b, int c) {
    edges_dup[a].push_back((int) edgelist.size());
    edgelist.push_back(edge_s(a, b, c, 0));
    edges_dup[b].push_back((int) edgelist.size());
    edgelist.push_back(edge_s(b, a, 0, 0));
}

void find_cut() {
    freopen("cut_min.txt", "w", stdout); // output file
    
    dis.resize(2 * V, 0);
    ptr.resize(2 * V, 0);
    edges_dup.resize(2 * V, vector<int>(0));
    const int top = min(10, V);

    for (int i = 0; i < V; i++)
        top_flow.push_back(make_pair(0, i));

    for (int i = 0; i < V; i++) {
        top_degree.push_back(make_pair(edge[i].size(), i));
        for (int j = 0; j < edge[i].size(); j++) {
            int to = edge[i][j];
            dinic_addedge(i, to + V, V);
        }
        dinic_addedge(i + V, i, 1);
    }
    
    stable_sort(top_degree.rbegin(), top_degree.rend());
    
    cout << "Minimum cut between characters:" << endl;
    for (int i = 0; i < top; i++) {
        for (int j = i + 1; j < top; j++) {
            vector<int>::iterator p = find(edge[top_degree[i].second].begin(), edge[top_degree[i].second].end(), top_degree[j].second);
            
            if (p != edge[top_degree[i].second].end())
                continue;
            
            int flow = dinic_flow(top_degree[i].second, top_degree[j].second + V);
            cout << name[top_degree[i].second] << " -> " << name[top_degree[j].second] << " = " << flow << endl;     

            for (int k = 0; k < edgelist.size(); k++) {
                if ((edgelist[k].a == (edgelist[k].b + V)) && (edgelist[k].flow == 1)) {
                    top_flow[edgelist[k].b].first++;
                }
                edgelist[k].flow = 0;
            }
        }
    }
    
    stable_sort(top_flow.rbegin(), top_flow.rend());

    cout << endl << "Top involved characters in the flows:" << endl;
    for (int i = 0; i < top; i++) {
        cout << name[top_flow[i].second] << " (" << top_flow[i].first << ")" << endl;
    }
}