Транспортни мрежи (Network Flow)

Транспортна мрежа е ориентиран граф, без циклуси во кој на секое ребро (i, j) му е придружен реален број аij>=0 што се нарекува пропусна способност на реброто, и за кој важи

• постои едно и само едно теме s, за кое важи дека нема ребра што влегуваат во тоа теме, кое се нарекува влезно теме или влез на мрежата
• постои едно и само едно теме t за кое важи дека нема ребра кои што излегуваат од тоа теме, кое се нарекува излезно теме или излез од мрежата

Протокот низ секое ребро не е поголем од неговата пропусна способност.
За секое теме освен влезното и излезното важи дека вкупниот проток што влегува во темето е еднаков со вкупниот проток што излегува од темето

Алгоритмот за наоѓање максимален проток од влезот (s) до излезот (t) е следен:

Алгоритмот ја започнува работата со произволен проток, што може да биде и нулти поток (се ставаат сите моментални проводности на нула). Потоа, протокот постојано се зголемува со систематска проверка на сите аугментални патеки од s кон t. Барањето на овие аугментални патеки се прави со помош на доделување ознаки на темињата кои кажуваат во правец на кои ребра и за колку потокот може да биде зголемен. Така, потокот се зголемува за максимално можна вредност и потоа повторно се ажурираат ознаките на темињата. Постапката се повторува се додека има аугментални патеки од s кон t.

Овој алгоритам е познат како алгоритам на Форд-Фалкерсон и доколку потокот секогаш го зголемуваме по најкусата аугментална патека, максималниот поток се добива за помалку од |V|*|E|/2 итерации каде што со V го означуваме бројот на темиња, а со E бројот на ребра во графот.

Имплементацијата во Java е следна:

 static int M;        // M is the number of vertices
 static long c[][] = new long[50][50];
 static long f[][] = new long[50][50];  // the flow
 
 static boolean busy[] = new boolean[50];
 static long ver[] = new long[50];
 static int who[] = new int[50];
 
 static void updateNeighbours(int mom) {
  int i;
  long newver;
  
  for (i=1;i<=M;i++) {
   if (busy[i] == false) {
    newver = Math.min(ver[mom], c[mom][i]-f[mom][i]);
    
    if (newver > ver[i]) {
     ver[i] = newver;
     who[i] = mom;
    }
   }
  }
 }
 
 static boolean findPath() {
  // we set all the vertices as unvisited
  int i;
  int bestv;
  long bestscore;
  long dec;
  
  for (i=1;i<=M;i++) {
   busy[i] = false;
   ver[i] = 0;
  }
  
  busy[1] = true;
  ver[1] = Integer.MAX_VALUE;
  who[1] = 0;
  updateNeighbours(1);
  
  while (busy[M] == false) {
   // we find the best vertex found so far
   bestv = 0;
   bestscore = 0;
   
   for (i=1;i<=M;i++) {
    if (busy[i] == false) {
     if (ver[i] > bestscore) {
      bestscore = ver[i];
      bestv = i;
     }
    }
   }
   
   if (bestv == 0) {
    // this means that a path has not been found
    return false;
   }
   
   busy[bestv] = true;
   updateNeighbours(bestv);
   
  }
  
  dec = ver[M];
  i = M;
  while (i!=1) {
   // we work with the segment from i to who[i]
   f[who[i]][i]+=dec;
   f[i][who[i]]=-f[who[i]][i];
   i=who[i];
  }
  
  return true;
 }
 
 static void networkFlow() {
  while (findPath() == true) {
   
  }
 }

M е бројот на темиња.
c[i][j] е пропусната способност на реброто од i до j.
f[i][j] е моменталната проводност по патот од i до j.

Пред да се повика функцијата networkFlow() треба да се иницијализираат пропусните способности на сите ребра. Доколку нема пат од едно теме i до друго теме j тогаш c[i][j]=0. Доколку графот е насочен, т.е. може да се оди само од i до j тогаш само c[i][j] > 0, а c[j][i] = 0. Доколку може да се оди во двете насоки тогаш c[i][j] == c[j][i] > 0. Треба да се напомене дека при повикувањето на networkFlow(), сите елементи f[i][j] треба да бидат иницијализирани на нула.
busy[], ver[] и who[] се низи кои се потребни за работа на алгоритмот на Дијкстра (правилниот изговор е Диџкстра, но јас го викам Дијкстра :) со кој го наоѓаме патот од изворот до излезното теме.

Овој алгоритам може да се примени и за други проблеми, како што е bipartite matching problem. Проблемот може да се дефинира вака.
Дадени ни се група на машки и група на женски и дадено ни е кој со кој си одговара :)
Да се одреди максималниот број на парови што можат да бидат направени така што да си одговараат машкото и женското од секој пар :)




Како може да го решиме проблемот со помош на тоа што веќе го знаеме за транспортните мрежи? Земаме две темиња кои ќе бидат влезно и излезно теме. Сите темиња од групата машки ги поврзуваме со изворот, а сите темиња од групата женски ги поврзуваме со излезното теме. Ги поврзуваме само оние машки и женски кои си одговараат. Сите врски се со тежина 1, т.е. доколку темињата i и j се поврзани, тогаш c[i][j] = 1.

Објаснувањето зошто треба вака да се реши проблемот го оставам на вас :)

Алгоритмот за решавање на овој проблем на транспортни мрежи многу често се применува во задачи. Многу убаво објаснување за овој алгоритам и за многу други, заедно со задачи со нивна примена може да се најдат на сајтот на USACO. Во скоро време ќе напишам и повеќе околу овој сајт и тоа што тој го нуди за едукација.

Користена литература:
USACO
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Algorithms in C - Robert Sedgewick