Tranzitivno zatvorenje i tranzitivna redukcija

Za zadati usmereni graf \(G=(V,E)\) njegovo tranzitivno zatvorenje (engl. transitive closure) je usmereni graf \(G^*=(V,E^*)\) u kome postoji grana od čvora \(u\) do čvora \(v\) ako i samo ako u grafu \(G\) postoji usmereni put od čvora \(u\) do čvora \(v\). Dakle, skupu grana \(E\) treba dodati što manji broj grana, tako da dobijeni novi skup grana \(E^*\) određuje relaciju koja je tranzitivna. Na slici 1 prikazan je jedan usmeren graf i njegovo tranzitivno zatvorenje.

Postoji veliki broj različitih primena tranzitivnog zatvorenja, pa je važno imati efikasan algoritam za njegovo nalaženje. Na primer, tabelu u programu za tabelarna izračunavanja (npr. Microsoft Excel) možemo predstaviti u vidu usmerenog grafa: polja tabele odgovaraju čvorovima, a grana od čvora koji odgovara polju \(a\) do čvora koji odgovara polju \(b\) postoji ako vrednost koja se računa u polju \(b\) zavisi od vrednosti polja \(a\). Kada se izmeni neka od vrednosti u tabeli, potrebno je ažurirati vrednosti svih polja koje od nje zavise, odnosno svih čvorova koji su dostižni iz datog polja. Ta polja se mogu odrediti na osnovu tranzitivnog zatvorenja datog grafa. Dodatno, ta polja je potrebno ažurirati u topološkom redosledu čvorova.

Slično, ako neki skup aerodroma razmotrimo kao skup čvorova, a postojanje direktnog leta od jednog do drugog aerodroma predstavimo usmerenom granom između odgovarajućih čvorova, onda nam tranzitivno zatvorenje grafa daje informaciju o tome sa kog aerodroma do kog aerodroma je moguće stići direktnim letom ili putem više povezanih letova.

Postoji više načina za računanje tranzitivnog zatvorenja datog grafa. Jedan način je da se iz svakog čvora pokrene pretraga u dubinu ili širinu i sačuva informacija o svim čvorovima dostižnim iz datog. Ovaj algoritam je vremenske složenosti \(O(|V|\cdot(|V|+|E|))\) i ima dobre performanse ako je graf redak, dok za guste grafove postaje složenosti \(O(|V|^3)\).

Ako je tranzitivno zatvorenje grafa \(G\) gust graf, efikasnije je najpre izračunati komponente jake povezanosti grafa \(G\). Za svaka dva čvora iz iste komponente jake povezanosti važi da su međusobno dostižni, pa u tranzitivnom zatvorenju treba da budu povezani granama. Ako postoji grana \((u,v)\) koja povezuje čvorove iz različitih jakih komponenti povezanosti, svaki čvor iz komponente kojoj pripada čvor \(v\) je dostižan iz svakog čvora komponente kojoj pripada čvor \(u\) i odgovarajuću granu treba dodati tranzitivnom zatvorenju grafa \(G\). Dakle, problem se svodi na pronalaženje tranzitivnog zatvorenja komprimovanog grafa, sačinjenog od jakih komponenti povezanosti, koji obično ima dosta manje čvorova i grana (slika 2). Ako postoji \(K\) komponenti jake povezanosti, složenost određivanja tranzitivnog zatvorenja komprimovanog grafa je \(O(K^3)\), što može biti znatno manje od \(O(|V|^3)\) kada je \(K\) dovoljno manje od \(|V|\).

Treći način da rešimo ovaj problem jeste redukcijom (svođenjem) na drugi problem. Ako granama grafa dodelimo proizvoljne težine (na primer, svakoj grani dodelimo težinu \(1\)) i izračunamo najkraće puteve između svih parova čvorova tako dobijenog težinskog grafa, dužina najkraćeg puta između čvorova između kojih postoji put će biti konačna, dok će dužina najkraćeg puta između čvorova između kojih ne postoji put ostati \(+\infty\). Dakle, problem određivanja tranzitivnog zatvorenja, što je u suštini problem ispitivanja dostižnosti između čvorova, prirodno se može svesti na određivanje dužine najkraćih puteva između svaka dva čvora.

Umesto da direktno primenimo algoritam za određivanje svih najkraćih puteva u grafu, možemo ga vremenski i prostorno optimizovati tako da direktno rešava problem tranzitivnog zatvorenja grafa. Primetimo da nas jedino interesuje da li je dužina najkraćeg puta u grafu \(G'\) konačna ili beskonačna (a u slučaju kada je konačna, ne interesuje nas njena konkretna vrednost, tj. da li je ona jednaka \(10\), \(7\) ili \(2\)). Dakle, umesto da koristimo celobrojnu matricu u kojoj se pamte dužine najkraćih puteva između svaka dva čvora, možemo koristiti logičku matricu koja na poziciji \((i,j)\) sadrži vrednost true ako je čvor \(j\) dostižan iz čvora \(i\), a inače false. Takođe, umesto da koristimo aritmetičke operacije, možemo preći na logičke operacije: umesto operacije sabiranja dužina koristimo logičku konjunkciju (dužina puta koji se sastoji iz dva dela će biti konačna ako i samo ako su oba dela puta konačna).

// funkcija koja za svaka dva cvora utvrdjuje
// da li izmedju njih postoji put
void tranzitivnoZatvorenje(const vector<vector<bool>>& matricaPovezanosti) {
  // inicijalizujemo matricu tranzitivnog zatvorenja
  // na matricu povezanosti grafa
  vector<vector<bool>> zatvorenje = matricaPovezanosti;
  int brojCvorova = matricaPovezanosti.size();

  // proveravamo da li postoji put kroz cvor sa oznakom k
  for (int k = 0; k < brojCvorova; k++)
    for (int i = 0; i < brojCvorova; i++)
      for (int j = 0; j < brojCvorova; j++)
        if (zatvorenje[i][k] && zatvorenje[k][j])
          zatvorenje[i][j] = true;

  cout << "Matrica susedstva grafa koji"
       << " predstavlja tranzitivno zatvorenje je" << endl;
  for (int i = 0; i < brojCvorova; i++) {
    for (int j = 0; j < brojCvorova; j++)
      cout << zatvorenje[i][j] << " ";
    cout << endl;
  }
}

int main() {
  // broj cvorova u grafu
  int n;
  cin >> n;
  // matrica susedstva grafa koji sadrzi n cvorova
  vector<vector<bool>> M(n);
  // ucitavamo matricu susedstva 
  for (int i = 0; i < n; i++) {
    M[i].resize(n);
    for (int j = 0; j < n; j++) {
      // realizujemo ucitavanje logickih vrednosti
      // citamo celobrojne vrednosti i konvertujemo ih u logicke
      int x;
      cin >> x;
      M[i][j] = x == 1;
    }
  }
  
  tranzitivnoZatvorenje(M);
  return 0;
}

Matrica zatvorenje na kraju izvršavanja algoritma kodira informacije o dostižnosti u polaznom grafu \(G\), odnosno predstavlja skup grana u tranzitivnom zatvorenju grafa \(G\).

Razmotrimo osnovni korak algoritma, naredbu if. Ona se sastoji od dve provere: da li važi zatvorenje[i,k] i da li važi zatvorenje[k,j]. Akcija se preduzima samo ako su oba uslova ispunjena. Ova if naredba izvršava se \(|V|\) puta za svaki par čvorova. Svaka popravka ove naredbe vodila bi bitnoj popravci algoritma. Moraju li se svaki put proveravati oba uslova? Prva provera zavisi samo od vrednosti \(i\) i \(k\), a druga zavisi samo od vrednosti \(k\) i \(j\). Zbog toga se prva provera može za fiksirane vrednosti \(i\) i \(k\) izvršiti samo jednom (umesto \(|V|\) puta). Naime,

Ova promena je ugrađena u poboljšani algoritam čiji je ključni fragment dat u nastavku. Asimptotska složenost algoritma ostaje nepromenjena, ali se algoritam u proseku izvršava dva puta brže.

// proveravamo da li postoji put kroz cvor sa oznakom k
for (int k = 0; k < brojCvorova; k++)
  for (int i = 0; i < brojCvorova; i++)
    if (zatvorenje[i][k])
      for (int j = 0; j < brojCvorova; j++)
        if (zatvorenje[k][j])
          zatvorenje[i][j] = true;

Zapaža se da se posle ove zamene u unutrašnjoj petlji algoritma operacija or primenjuje na vrstu \(i\) i vrstu \(k\) matrice zatvorenje, a rezultat je nova vrsta \(i\). Zbog toga, ako je \(n=|V|\le 64\), vrste matrice zatvorenje predstavljaju niz nula i jedinica i mogu se tumačiti kao \(n\) bitova u binarnoj reprezentacija celog broja, pa se primena operacije or na vrste može zameniti bitskom or operacijom dva cela broja, što je \(n\) puta brže. Ako je \(n>64\), onda se vrsta može predstaviti nizom 64-bitnih celih brojeva, pa se algoritam izvršava približno \(64\) puta brže. Asimptotska složenost je i dalje \(O(|V|^3)\), ali ubrzanje za faktor \(64\) nije zanemarljivo.

Primer 2.12.1. Razmotrimo primer izračunavanja tranzitivnog zatvorenja grafa sa slike 3.

Slika 3: Primer grafa za koji je potrebno odrediti tranzitivno zatvorenje.

On se sastoji iz narednih koraka:

\(k=0\): \( \begin{matrix} & \begin{matrix}1&2&3&4\end{matrix} \\ \begin{matrix}1\\2\\3\\4\end{matrix} \hspace{-1em} & \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\end{pmatrix} \end{matrix}\) \(k=1\): \( \begin{matrix} & \begin{matrix}1&2&3&4\end{matrix} \\ \begin{matrix}1\\2\\3\\4\end{matrix} \hspace{-1em} & \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\end{pmatrix} \end{matrix}\) \(k=2\): \( \begin{matrix} & \begin{matrix}1&2&3&4\end{matrix} \\ \begin{matrix}1\\2\\3\\4\end{matrix} \hspace{-1em} & \begin{pmatrix} 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\end{pmatrix} \end{matrix}\)

\(k=3\): \( \begin{matrix} & \begin{matrix}1&2&3&4\end{matrix} \\ \begin{matrix}1\\2\\3\\4\end{matrix} \hspace{-1em} & \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\end{pmatrix} \end{matrix}\) \(k=4\): \( \begin{matrix} & \begin{matrix}1&2&3&4\end{matrix} \\ \begin{matrix}1\\2\\3\\4\end{matrix} \hspace{-1em} & \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0\end{pmatrix} \end{matrix}\)

Primetimo da u grafu sa slike 3 ne postoji direktna grana od čvora \(3\) do čvora \(2\), ali postoji put dužine dva preko čvora \(1\). Slično, od čvora \(3\) do čvora \(4\) ne postoji direktna grana, ali postoji put dužine \(3\), preko čvorova \(1\) i \(2\).

Čitaocima se ostavlja za razmišljanje pitanje kako bi izgledalo tranzitivno zatvorenje neusmerenog grafa.

Interesantan problem u vezi sa nalaženjem tranzitivnog zatvorenja je i problem određivanja tranzitivne redukcije grafa (engl. transitive reduction). Ova operacija predstavlja operaciju inverznu operaciji pronalaženja tranzitivnog zatvorenja grafa: cilj je da se za dati usmereni graf konstruiše usmereni graf sa istim skupom čvorova i što manjim skupom grana, a da se pritom ne promeni relacija dostižnosti. Tranzitivno zatvorenje grafa \(G\) jednako je tranzitivnom zatvorenju tranzitivne redukcije grafa \(G\). Iako je tranzitivno zatvorenje grafa \(G\) jedinstveno određeno, u opštem slučaju graf može imati više različitih tranzitivnih redukcija.

2.12 Tranzitivno zatvorenje i tranzitivna redukcija