Tranzitivno zaprtje usmerjenega grafa

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Kratek opis problema

Na podanem usmerjenem grafu iščemo vse direktne povezave iz izbranega vozlišča do ostalih vozlišč do katerih lahko dostopamo iz danega vozlišča preko povezav v grafu. Dobljen graf imenujemo tranzitivno zaprt graf.

Pojmi

Če za poljuben usmerjen graf in neko izbrano vozlišče iščemo tranzitivno zaprtje grafa, moramo najprej vedeti kaj je usmerjen graf in kaj je tranzitivnost.

  • Usmerjen graf:

Graf z vozlišči in povezavami je usmerjen, če so povezave usmerjene, torej se začnejo v začetnem vozlišču (iz katerega povezava izhaja) in končajo v končnem vozlišču (v katerega je povezava usmerjena).

  • Tranzitivnost:

Če obstaja povezava (v primeru usmerjenega grafa - usmerjena povezava) iz vozlišča x v vozlišče y in povezava (v primeru usmerjenega grafa - usmerjena povezava) iz vozlišča y in v vozlišče z, potem obstaja tudi povezava (v primeru usmerjenega grafa - usmerjena povezava) iz x v z</br>

Uvod

Za poljuben usmerjen graf in neko izbrano vozlišče bi radi poiskali tranzitivno zaprtje usmerjenega grafa. Tranzitivno zaprtje usmerjenega gafa dobim tako, da poiščemo vsa vozlišča do katerih lahko dostopamo preko usmerjenih povezav iz izbranega vozlišča. Izbano vozišče in ta vozlišča ter usmerjene povezave iz izbranega vozlišča do teh vozlišč imenujemo tranzitivno zaprtje usmerenega grafa. Primer podanega usmerjnega grafa in njegovega tranzitivno zaprtega usmerjenega grafa:

Usmerjen graf in matrika sosednosti

Slika:Usmerjen graf.jpg


Tranzitivno zaprtje grafa in matrika sosednosti

Slika:Zaprtje graf.jpg

Warshallov algoritem

En izmed algoritmov za iskanje tranzitivnega zaprja usmerjenega grafa je Warshallov algotitem.

Primer Warshallovega algoritma, ki za podano matriko sosednosti poišče tranzitivno zaprtje grafa (matriko sosednosti).

  1.  
  2. public static void Warshall (int[][] A)
  3. {
  4. for (int k = 0; k < A.length; k++)
  5. for (int i = 0; i < A.length; i++)
  6. for (int j = 0; j < A.length; j++)
  7. A[i][j] = A[i][j] | (A[i][k] & A[k][j]);
  8. }

Implementacija tranzitivnega zaprtja usmerjenega grafa

  1.  
  2. GraphTC(Graph G)
  3. {
  4. DenseGraph T = GraphUtilities.densecopy(G); //ustvarimo kopijo grafa G
  5. //dodamo ciklicne povezave na vsakem vozliscu (xRx in xRx -> xRx)
  6. for (int s = 0; s < T.V(); s++)
  7. T.insert(new Edge(s, s));
  8.  
  9. for (int i = 0; i < T.V(); i++) //se premikamo po vseh vozlscih
  10. for (int s = 0; s < T.V(); s++) //izvajamo tranzitivno zaprtje na vseh vozlscih
  11. if (T.edge(s, i)) //a) ce obstaja povezava do vozlisca i iz izbranega vozlisca (trenutnega V(s))
  12. for (int t = 0; t < T.V(); t++)
  13. if (T.edge(i, t)) //b) ce obstaja povezava do vozlisca t iz vozlisca i
  14. //ce je izpolnjena tranzitivnost iz tock a) in b) potem obstaja povezava
  15. //iz vozlisca s do vozlisca t, ki jo dodamo grafu
  16. T.insert(new Edge(s, t));
  17. }

Primeri

  • Warshall.java

  1.  
  2. public class Warshall {
  3. public static void Warshall (int[][] A)
  4. {
  5. for (int k = 0; k < A.length; k++)
  6. for (int i = 0; i < A.length; i++)
  7. for (int j = 0; j < A.length; j++)
  8. A[i][j] = A[i][j] | (A[i][k] & A[k][j]);
  9. }
  10.  
  11. public static void izpisi(int[][] A)
  12. {
  13. for (int i = 0; i < A.length; i++) {
  14. for (int j = 0; j < A.length; j++)
  15. System.out.print(A[i][j] + " ");
  16. System.out.println();
  17. }
  18. }
  19.  
  20. public static void main(String[] args)
  21. {
  22. int[][] A = new int[][] {{1, 0, 1, 0, 0, 1},
  23. {1, 1, 0, 0, 0, 0},
  24. {0, 1, 1, 0, 0, 0},
  25. {0, 0, 1, 1, 1, 0},
  26. {0, 0, 0, 0, 1, 1},
  27. {0, 0, 0, 0, 1, 1}};
  28. System.out.println("Matrika sosednosti:");
  29. izpisi(A);
  30. Warshall(A);
  31. System.out.println("Tranzitivno zaprtje:");
  32. izpisi(A);
  33. }
  34. }

Povzetek

Tranzitivno zaprtje usmerjenega grafa je usmerjen graf, ki ima povezave iz dane točke v vse tiste točke, ki jih iz te točke lahko dosežemo s sprehodom po usmerjenih povezavah v originalnem grafu.
Z algoritmom za iskanje tranzitivnega zaprtja usmerjenega grafa lahko ugotovimo, če iz določenega vozlišča lahko direktno pridemo v katerokoli drugo vozlišče.

Literatura

Kot vir sem uporabljala knjigo Algorithms in Java, Third Edition, Part 5: Graph Algorithms.

Osebna orodja