Рубрики

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

В потоковой сети первый разрез — это разрез, который требует, чтобы источник 's' и приемник 't' находились в разных подмножествах, и он состоит из ребер, идущих от стороны источника к стороне приемника. Пропускная способность st-резания определяется суммой мощностей каждого ребра в наборе. (Источник: Вики )
Обсуждаемая здесь проблема заключается в том, чтобы найти минимальную пропускную способность данной сети. Ожидаемый результат — все края минимального среза.

Например, в следующей потоковой сети примерами срезов st являются {{0, 1}, {0, 2}}, {{0, 2}, {1, 2}, {1, 3}} и т. Д. минимальный срез — {{1, 3}, {4, 3}, {4 5}}, емкость которого равна 12 + 7 + 4 = 23.

Мы настоятельно рекомендуем сначала прочитать приведенный ниже пост.
Алгоритм Форда-Фулкерсона для задачи о максимальном расходе

Минимальный рез и максимальный поток
Как и « Максимальное двустороннее соответствие» , это еще одна проблема, которую можно решить с помощью алгоритма Форда-Фулкерсона . Это основано на теореме о максимальном потоке.

Теорема о минимальном срезе максимального расхода гласит, что в сети потоков величина максимального расхода равна пропускной способности минимального среза. См. Книгу CLRS для доказательства этой теоремы.

От Ford-Fulkerson мы получаем мощность минимальной резки. Как распечатать все края, которые образуют минимальный срез? Идея состоит в том, чтобы использовать остаточный граф .

Ниже приведены шаги для печати всех краев минимального среза.

1) Запустите алгоритм Форда-Фулкерсона и рассмотрите окончательный остаточный граф .

2) Найдите множество вершин, которые достижимы из источника в остаточном графе.

3) Все ребра, которые находятся от достижимой вершины до недостижимой вершины, являются минимальными режущими кромками. Распечатайте все такие края.

Ниже приводится реализация вышеуказанного подхода.

C ++

// C ++ программа для поиска минимального среза с использованием Ford-Fulkerson
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>

using namespace std;

  
// Количество вершин в данном графе
#define V 6

  
/ * Возвращает true, если есть путь от источника 's' к стоку 't' в

  остаточный граф. Также заполняет parent [] для хранения пути * /

int bfs(int rGraph[V][V], int s, int t, int parent[])

{

    // Создаем посещенный массив и отмечаем все вершины как не посещенные

    bool visited[V];

    memset(visited, 0, sizeof(visited));

  

    // Создать очередь, поставить в очередь исходную вершину и отметить исходную вершину

    // как посетил

    queue <int> q;

    q.push(s);

    visited[s] = true;

    parent[s] = -1;

  

    // Стандартный цикл BFS

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

  

        for (int v=0; v<V; v++)

        {

            if (visited[v]==false && rGraph[u][v] > 0)

            {

                q.push(v);

                parent[v] = u;

                visited[v] = true;

            }

        }

    }

  

    // Если мы достигли стока в BFS, начиная с источника, то возвращаем

    // правда, иначе ложь

    return (visited[t] == true);

}

  
// Функция на основе DFS, чтобы найти все достижимые вершины из s. Функция
// отмечает посещение [i] как истинное, если я достижим из s. Начальные значения в
// посещения [] должны быть ложными. Мы также можем использовать BFS для поиска достижимых вершин

void dfs(int rGraph[V][V], int s, bool visited[])

{

    visited[s] = true;

    for (int i = 0; i < V; i++)

       if (rGraph[s][i] && !visited[i])

           dfs(rGraph, i, visited);

}

  
// Печатает минимальный срез

void minCut(int graph[V][V], int s, int t)

{

    int u, v;

  

    // Создание остаточного графа и заполнение остаточного графа

    // заданные мощности в исходном графике как остаточные мощности

    // в остаточном графе

    int rGraph[V][V]; // rGraph [i] [j] указывает остаточную емкость ребра ij

    for (u = 0; u < V; u++)

        for (v = 0; v < V; v++)

             rGraph[u][v] = graph[u][v];

  

    int parent[V];  // Этот массив заполняется BFS и для хранения пути

  

    // Увеличиваем поток, пока есть путь от источника к стоку

    while (bfs(rGraph, s, t, parent))

    {

        // Находим минимальную остаточную емкость кромок вдоль

        // путь заполнен BFS. Или мы можем сказать, найти максимальный поток

        // через найденный путь.

        int path_flow = INT_MAX;

        for (v=t; v!=s; v=parent[v])

        {

            u = parent[v];

            path_flow = min(path_flow, rGraph[u][v]);

        }

  

        // обновляем остаточные емкости ребер и обратных ребер

        // по пути

        for (v=t; v != s; v=parent[v])

        {

            u = parent[v];

            rGraph[u][v] -= path_flow;

            rGraph[v][u] += path_flow;

        }

    }

  

    // Поток максимальный сейчас, найти вершины, достижимые из s

    bool visited[V];

    memset(visited, false, sizeof(visited));

    dfs(rGraph, s, visited);

  

    // Распечатать все ребра от достижимой вершины до

    // недостижимая вершина в исходном графе

    for (int i = 0; i < V; i++)

      for (int j = 0; j < V; j++)

         if (visited[i] && !visited[j] && graph[i][j])

              cout << i << " - " << j << endl;

  

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим график, показанный в приведенном выше примере

    int graph[V][V] = { {0, 16, 13, 0, 0, 0},

                        {0, 0, 10, 12, 0, 0},

                        {0, 4, 0, 0, 14, 0},

                        {0, 0, 9, 0, 0, 20},

                        {0, 0, 0, 7, 0, 4},

                        {0, 0, 0, 0, 0, 0}

                      };

  

    minCut(graph, 0, 5);

  

    return 0;

}

Джава

// Java-программа для нахождения минимального разреза в заданном графике

import java.util.LinkedList;

import java.util.Queue;

  

public class Graph {

          

    // Возвращает true, если есть путь

    // из источника 's' в сток 't' в остатке

    // график. Также заполняет parent [] для хранения пути

    private static boolean bfs(int[][] rGraph, int s,

                                int t, int[] parent) {

          

        // Создать посещенный массив и пометить

        // все вершины как не посещенные

        boolean[] visited = new boolean[rGraph.length];

          

        // Создать очередь, поставить в очередь исходную вершину

        // и отмечаем исходную вершину как посещенную

        Queue<Integer> q = new LinkedList<Integer>();

        q.add(s);

        visited[s] = true;

        parent[s] = -1;

          

        // Стандартный цикл BFS

        while (!q.isEmpty()) {

            int v = q.poll();

            for (int i = 0; i < rGraph.length; i++) {

                if (rGraph[v][i] > 0 && !visited[i]) {

                    q.offer(i);

                    visited[i] = true;

                    parent[i] = v;

                }

            }

        }

          

        // Если мы достигли раковины в старте BFS

        // из источника, затем возвращаем true, иначе false

        return (visited[t] == true);

    }

      

    // Функция на основе DFS, чтобы найти все достижимые

    // вершины из s. Функция отмечает посещенные [я]

    // как истина, если я достижим от s. Начальный

    // значения в посещенном [] должны быть ложными. Мы также можем

    // используем BFS для поиска достижимых вершин

    private static void dfs(int[][] rGraph, int s,

                                boolean[] visited) {

        visited[s] = true;

        for (int i = 0; i < rGraph.length; i++) {

                if (rGraph[s][i] > 0 && !visited[i]) {

                    dfs(rGraph, i, visited);

                }

        }

    }

  

    // Печатает минимальный срез

    private static void minCut(int[][] graph, int s, int t) {

        int u,v;

          

        // Создать остаточный график и заполнить остаточный

        // график с заданными возможностями в оригинале

        // график как остаточные емкости в остаточном графе

        // rGraph [i] [j] указывает остаточную емкость ребра ij

        int[][] rGraph = new int[graph.length][graph.length]; 

        for (int i = 0; i < graph.length; i++) {

            for (int j = 0; j < graph.length; j++) {

                rGraph[i][j] = graph[i][j];

            }

        }

  

        // Этот массив заполняется BFS и для хранения пути

        int[] parent = new int[graph.length]; 

          

        // Увеличиваем поток, пока путь от источника к стоку

        while (bfs(rGraph, s, t, parent)) {

              

            // Находим минимальную остаточную емкость стружки

            // по пути, заполненному BFS. Или мы можем сказать

            // найти максимальный поток по найденному пути.

            int pathFlow = Integer.MAX_VALUE;         

            for (v = t; v != s; v = parent[v]) {

                u = parent[v];

                pathFlow = Math.min(pathFlow, rGraph[u][v]);

            }

              

            // обновляем остаточные емкости ребер и

            // перевернуть ребра вдоль пути

            for (v = t; v != s; v = parent[v]) {

                u = parent[v];

                rGraph[u][v] = rGraph[u][v] - pathFlow;

                rGraph[v][u] = rGraph[v][u] + pathFlow;

            }

        }

          

        // Поток максимальный сейчас, найти вершины, достижимые из s

        boolean[] isVisited = new boolean[graph.length];     

        dfs(rGraph, s, isVisited);

          

        // Распечатать все ребра от достижимой вершины до

        // недостижимая вершина в исходном графе

        for (int i = 0; i < graph.length; i++) {

            for (int j = 0; j < graph.length; j++) {

                if (graph[i][j] > 0 && isVisited[i] && !isVisited[j]) {

                    System.out.println(i + " - " + j);

                }

            }

        }

    }

  

    // Программа для водителя

    public static void main(String args[]) {

          

        // Давайте создадим график, показанный в приведенном выше примере

        int graph[][] = { {0, 16, 13, 0, 0, 0},

                {0, 0, 10, 12, 0, 0},

                {0, 4, 0, 0, 14, 0},

                {0, 0, 9, 0, 0, 20},

                {0, 0, 0, 7, 0, 4},

                {0, 0, 0, 0, 0, 0}

            };

        minCut(graph, 0, 5);

    }

}
// Этот код предоставлен Химаншу Шехар

питон

# Python программа для поиска мин-среза в заданном графике
# Сложность: (E * (V ^ 3))
# Полный путь расширения = VE и BFS с соседней матрицей: V ^ 2 раза

  

from collections import defaultdict

  
# Этот класс представляет ориентированный граф с использованием представления матрицы смежности

class Graph:

  

    def __init__(self,graph):

        self.graph = graph # остаточный график

        self.org_graph = [i[:] for i in graph]

        self. ROW = len(graph)

        self.COL = len(graph[0])

  

  

    '' 'Возвращает true, если есть путь от источника' s 'к стоку' t 'в

    остаточный граф. Также заполняет parent [] для хранения пути '' '

    def BFS(self,s, t, parent):

  

        # Отметить все вершины как не посещенные

        visited =[False]*(self.ROW)

  

        # Создать очередь для BFS

        queue=[]

  

        # Отметить исходный узел как посещенный и поставить его в очередь

        queue.append(s)

        visited[s] = True

  

         # Стандартный цикл BFS

        while queue:

  

            # Освободить вершину из очереди и распечатать ее

            u = queue.pop(0)

  

            # Получить все смежные вершины в удаленной вершине u

            # Если соседний объект не посещался, отметьте его

            # посетил и поставил в очередь

            for ind, val in enumerate(self.graph[u]):

                if visited[ind] == False and val > 0 :

                    queue.append(ind)

                    visited[ind] = True

                    parent[ind] = u

  

        # Если мы достигли приемника в BFS, начиная с исходного кода, вернемся

        # верно, иначе неверно

        return True if visited[t] else False

  

  

    # Возвращает минимальный срез данного графика

    def minCut(self, source, sink):

  

        # Этот массив заполняется BFS и для хранения пути

        parent = [-1]*(self.ROW)

  

        max_flow = 0 # Нет потока изначально

  

        # Увеличивать поток, пока есть путь от источника к раковине

        while self.BFS(source, sink, parent) :

  

            # Найти минимальную остаточную емкость ребер вдоль

            # путь заполнен BFS. Или мы можем сказать, найти максимальный поток

            # через найденный путь.

            path_flow = float("Inf")

            s = sink

            while(s !=  source):

                path_flow = min (path_flow, self.graph[parent[s]][s])

                s = parent[s]

  

            # Добавить поток пути к общему потоку

            max_flow +=  path_flow

  

            # обновить остаточные емкости ребер и обратных ребер

            # вдоль пути

            v = sink

            while(v !=  source):

                u = parent[v]

                self.graph[u][v] -= path_flow

                self.graph[v][u] += path_flow

                v = parent[v]

  

        # печатать ребра, которые изначально имели вес

        # но теперь есть 0 вес

        for i in range(self.ROW):

            for j in range(self.COL):

                if self.graph[i][j] == 0 and self.org_graph[i][j] > 0:

                    print str(i) + " - " + str(j)

  

  
# Создайте график, приведенный на диаграмме выше

graph = [[0, 16, 13, 0, 0, 0],

        [0, 0, 10, 12, 0, 0],

        [0, 4, 0, 0, 14, 0],

        [0, 0, 9, 0, 0, 20],

        [0, 0, 0, 7, 0, 4],

        [0, 0, 0, 0, 0, 0]]

  

g = Graph(graph)

  

source = 0; sink = 5

  
g.minCut(source, sink)

  
# Этот код предоставлен Neelam Yadav

C #

// C # программа для поиска мин-среза в заданном графике

using System;

using System.Collections.Generic;

  

class Graph

{

          

    // Возвращает true, если есть путь

    // из источника 's' в сток 't' в остатке

    // график. Также заполняет parent [] для хранения пути

    private static bool bfs(int[,] rGraph, int s,

                            int t, int[] parent) 

    {

          

        // Создать посещенный массив и пометить

        // все вершины как не посещенные

        bool[] visited = new bool[rGraph.Length];

          

        // Создать очередь, поставить в очередь исходную вершину

        // и отмечаем исходную вершину как посещенную

        Queue<int> q = new Queue<int>();

        q.Enqueue(s);

        visited[s] = true;

        parent[s] = -1;

          

        // Стандартный цикл BFS

        while (q.Count != 0) 

        {

            int v = q.Dequeue();

            for (int i = 0; i < rGraph.GetLength(0); i++) 

            {

                if (rGraph[v,i] > 0 && !visited[i]) 

                {

                    q.Enqueue(i);

                    visited[i] = true;

                    parent[i] = v;

                }

            }

        }

          

        // Если мы достигли раковины в старте BFS

        // из источника, затем возвращаем true, иначе false

        return (visited[t] == true);

    }

      

    // Функция на основе DFS, чтобы найти все достижимые

    // вершины из s. Функция отмечает посещенные [я]

    // как истина, если я достижим от s. Начальный

    // значения в посещенном [] должны быть ложными. Мы также можем

    // используем BFS для поиска достижимых вершин

    private static void dfs(int[,] rGraph, int s,

                            bool[] visited) 

    {

        visited[s] = true;

        for (int i = 0; i < rGraph.GetLength(0); i++) 

        {

            if (rGraph[s,i] > 0 && !visited[i])

            {

                dfs(rGraph, i, visited);

            }

        }

    }

  

    // Печатает минимальный срез

    private static void minCut(int[,] graph, int s, int t) 

    {

        int u, v;

          

        // Создать остаточный график и заполнить остаточный

        // график с заданными возможностями в оригинале

        // график как остаточные емкости в остаточном графе

        // rGraph [i, j] указывает остаточную емкость ребра ij

        int[,] rGraph = new int[graph.Length,graph.Length]; 

        for (int i = 0; i < graph.GetLength(0); i++)

        {

            for (int j = 0; j < graph.GetLength(1); j++)

            {

                rGraph[i, j] = graph[i, j];

            }

        }

  

        // Этот массив заполняется BFS и для хранения пути

        int[] parent = new int[graph.Length]; 

          

        // Увеличиваем поток, пока есть путь

        // от источника к раковине

        while (bfs(rGraph, s, t, parent)) 

        {

              

            // Находим минимальную остаточную емкость стружки

            // по пути, заполненному BFS. Или мы можем сказать

            // найти максимальный поток по найденному пути.

            int pathFlow = int.MaxValue;         

            for (v = t; v != s; v = parent[v]) 

            {

                u = parent[v];

                pathFlow = Math.Min(pathFlow, rGraph[u, v]);

            }

              

            // обновляем остаточные емкости ребер и

            // перевернуть ребра вдоль пути

            for (v = t; v != s; v = parent[v])

            {

                u = parent[v];

                rGraph[u, v] = rGraph[u, v] - pathFlow;

                rGraph[v, u] = rGraph[v, u] + pathFlow;

            

        }

          

        // Поток максимальный сейчас, найти вершины, достижимые из s

        bool[] isVisited = new bool[graph.Length];     

        dfs(rGraph, s, isVisited);

          

        // Распечатать все ребра от достижимой вершины до

        // недостижимая вершина в исходном графе

        for (int i = 0; i < graph.GetLength(0); i++) 

        {

            for (int j = 0; j < graph.GetLength(1); j++)

            {

                if (graph[i, j] > 0 && 

                    isVisited[i] && !isVisited[j])

                {

                    Console.WriteLine(i + " - " + j);

                }

            }

        }

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

          

        // Давайте создадим показанный график

        // в приведенном выше примере

        int [,]graph = {{0, 16, 13, 0, 0, 0},

                        {0, 0, 10, 12, 0, 0},

                        {0, 4, 0, 0, 14, 0},

                        {0, 0, 9, 0, 0, 20},

                        {0, 0, 0, 7, 0, 4},

                        {0, 0, 0, 0, 0, 0}};

        minCut(graph, 0, 5);

    }

}

  
// Этот код предоставлен PrinciRaj1992


Выход:

1 - 3
4 - 3
4 - 5

Ссылки:
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
http://www.cs.princeton.edu/courses/archive/spring06/cos226/lectures/maxflow.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes