Рубрики

Найти максимальное количество ребер непересекающихся путей между двумя вершинами

Учитывая ориентированный граф и две вершины в нем, источник 's' и пункт назначения 't', найдите максимальное количество непересекающихся путей ребер от s до t. Два пути называются ребрами непересекающимися, если они не имеют общего ребра.

На приведенном выше графике может быть не более двух ребер непересекающихся путей от источника 0 до места назначения 7. Две крайние непересекающиеся дорожки выделены ниже красным и синим цветами: 0-2-6-7 и 0-3-6-5-7.

Обратите внимание, что пути могут быть разными, но максимальное количество одинаково. Например, на приведенной выше схеме другой возможный набор путей — это 0-1-2-6-7 и 0-3-6-5-7 соответственно.

Эту проблему можно решить, уменьшив ее до максимальной скорости потока . Ниже приведены шаги.
1) Рассмотрите данный источник и назначение как источник и приемник в сети потока. Назначьте емкость устройства для каждого края.
2) Запустите алгоритм Форда-Фулкерсона, чтобы найти максимальный поток от источника до приемника.
3) Максимальный поток равен максимальному количеству непересекающихся путей.

Когда мы запускаем Ford-Fulkerson, мы уменьшаем емкость на единицу. Таким образом, край не может быть использован снова. Таким образом, максимальный поток равен максимальному числу непересекающихся ребер.

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

C / C ++

// C ++ программа для поиска максимального количества непересекающихся путей ребер
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>

using namespace std;

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

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

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

bool 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);

}

  
// Возвращает максимальное количество непересекающихся с ребром путей от s до t.
// Эта функция является копией forFulkerson (), обсуждаемой на http://goo.gl/wtQ4Ks

int findDisjointPaths(int graph[V][V], int s, int t)

{

    int u, v;

  

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

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

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

    int rGraph[V][V]; // Остаточный граф, где rGraph [i] [j] указывает

                     // остаточная емкость ребра от i до j (если есть

                     // это ребро Если rGraph [i] [j] равен 0, то нет)

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

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

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

  

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

  

    int max_flow = 0;  // изначально нет потока

  

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

    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;

        }

  

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

        max_flow += path_flow;

    }

  

    // Возвращаем общий поток (max_flow равен максимальному

    // количество непересекающихся путей

    return max_flow;

}

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

int main()

{

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

    int graph[V][V] = { {0, 1, 1, 1, 0, 0, 0, 0},

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

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

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

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

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

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

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

                      };

  

    int s = 0;

    int t = 7;

    cout << "There can be maximum " << findDisjointPaths(graph, s, t)

         << " edge-disjoint paths from " << s <<" to "<< t ;

  

    return 0;

}

Джава

// Java программа для поиска максимального числа
// краевых непересекающихся путей

import java.util.*;

  

class GFG

{

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

static int V = 8;

  
/ * Возвращает true, если есть путь от
источник 's', чтобы поглотить 't' в остаточном графе.
Также заполняет parent [] для хранения пути * /

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

                   int t, int parent[])

{

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

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

    boolean []visited = new boolean[V];

  

  

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

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

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

    q.add(s);

    visited[s] = true;

    parent[s] = -1;

  

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

    while (!q.isEmpty())

    {

        int u = q.peek();

        q.remove();

  

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

        {

            if (visited[v] == false && 

                rGraph[u][v] > 0)

            {

                q.add(v);

                parent[v] = u;

                visited[v] = true;

            }

        }

    }

  

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

    // начиная с источника, затем

    // вернуть true, иначе false

    return (visited[t] == true);

}

  
// Возвращает максимальное количество ребер-непересекающихся
// пути от s до t. Эта функция является копией
// forFulkerson () обсуждается на http://goo.gl/wtQ4Ks

static int findDisjointPaths(int graph[][], int s, int t)

{

    int u, v;

  

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

    // остаточный граф с заданными емкостями

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

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

      

    // Остаточный граф, где rGraph [i] [j] указывает

    // остаточная емкость ребра от i до j (если есть

    // это ребро Если rGraph [i] [j] равен 0, то нет)

    int [][]rGraph = new int[V][V];

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

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

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

      

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

    int []parent = new int[V]; 

  

    int max_flow = 0; // изначально нет потока

  

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

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

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

    {

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

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

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

        int path_flow = Integer.MAX_VALUE;

  

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

        {

            u = parent[v];

            path_flow = Math.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;

        }

  

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

        max_flow += path_flow;

    }

  

    // Возвращаем общий поток (max_flow равен

    // максимальное количество непересекающихся путей

    return max_flow;

}

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

public static void main(String[] args)

{

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

    int graph[][] = {{0, 1, 1, 1, 0, 0, 0, 0},

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

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

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

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

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

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

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

  

    int s = 0;

    int t = 7;

    System.out.println("There can be maximum "

                findDisjointPaths(graph, s, t) + 

                  " edge-disjoint paths from "

                                 s + " to "+ t);

}

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

питон

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

   

from collections import defaultdict

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

class Graph:

   

    def __init__(self,graph):

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

        self. ROW = len(graph)

          

   

    '' 'Возвращает 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 findDisjointPaths(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]

  

        return max_flow

  

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

  

graph = [[0, 1, 1, 1, 0, 0, 0, 0],

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

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

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

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

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

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

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

   

  

g = Graph(graph)

  

source = 0; sink = 7

   

print ("There can be maximum %d edge-disjoint paths from %d to %d" % 

            (g.findDisjointPaths(source, sink), source, sink))

  

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

C #

// C # программа для поиска максимального числа
// краевых непересекающихся путей

using System;

using System.Collections.Generic; 

  

class GFG

{

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

static int V = 8;

  
/ * Возвращает true, если есть путь от
источник 's', чтобы поглотить 't' в остаточном графе.
Также заполняет parent [] для хранения пути * /

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

                int t, int []parent)

{

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

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

    bool []visited = new bool[V];

  

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

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

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

    q.Enqueue(s);

    visited[s] = true;

    parent[s] = -1;

  

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

    while (q.Count != 0)

    {

        int u = q.Peek();

        q.Dequeue();

  

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

        {

            if (visited[v] == false && 

                rGraph[u, v] > 0)

            {

                q.Enqueue(v);

                parent[v] = u;

                visited[v] = true;

            }

        }

    }

  

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

    // начиная с источника, затем

    // вернуть true, иначе false

    return (visited[t] == true);

}

  
// Возвращает максимальное количество ребер-непересекающихся
// пути от s до t. Эта функция является копией
// forFulkerson () обсуждается на http://goo.gl/wtQ4Ks

static int findDisjointPaths(int [,]graph, 

                             int s, int t)

{

    int u, v;

  

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

    // остаточный граф с заданными емкостями

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

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

      

    // Остаточный граф, где rGraph [i, j] указывает

    // остаточная емкость ребра от i до j (если есть

    // это ребро Если rGraph [i, j] равен 0, то нет)

    int [,]rGraph = new int[V, V];

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

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

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

      

    // Этот массив заполнен BFS и

    // сохранить путь

    int []parent = new int[V]; 

  

    int max_flow = 0; // изначально нет потока

  

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

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

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

    {

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

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

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

        int path_flow = int.MaxValue;

  

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

        {

            u = parent[v];

            path_flow = Math.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;

        }

  

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

        max_flow += path_flow;

    }

  

    // Возвращаем общий поток (max_flow равен

    // максимальное количество непересекающихся путей

    return max_flow;

}

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

public static void Main(String[] args)

{

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

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

    int [,]graph = {{0, 1, 1, 1, 0, 0, 0, 0},

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

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

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

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

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

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

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

  

    int s = 0;

    int t = 7;

    Console.WriteLine("There can be maximum "

               findDisjointPaths(graph, s, t) + 

                 " edge-disjoint paths from "

                                s + " to "+ t);

}

  
// Этот код предоставлен Rajput-Ji


Выход:

There can be maximum 2 edge-disjoint paths from 0 to 7 

Сложность времени: такая же, как сложность времени реализации Эдмондса-Карпа для Форд-Фулкерсона (см. Сложность времени, обсуждаемую здесь )

Ссылки:
http://www.win.tue.nl/~nikhil/courses/2012/2WO08/max-flow-applications-4up.pdf

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

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

Найти максимальное количество ребер непересекающихся путей между двумя вершинами

0.00 (0%) 0 votes