SHARE
TWEET

Untitled

LazySenpai Jun 25th, 2019 38 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass[12pt,a4paper,leqno]{article}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage{polski}
  4. \usepackage{pgf}
  5. \usepackage{tikz}
  6. \usetikzlibrary{arrows,automata}
  7. \usepackage{subfigure}
  8. \usepackage{xcolor}
  9. \usepackage{float}
  10. \usepackage{geometry}
  11.  \geometry{
  12.  a4paper,
  13.  total={170mm,257mm},
  14.  left=20mm,
  15.  top=20mm,
  16.  }
  17. \tikzset{
  18.     ultra thick/.style={line width=10pt}
  19. }
  20. \usetikzlibrary{patterns}
  21.  
  22. \begin{document}
  23. \section*{Algorytm Borůvki}
  24.  
  25. Jest to algorytm wyznaczający minimalne drzewo rozpinające dla grafu ważonego pod warunkiem, że jest on spójny. Jest on algorytmem zachłannym.
  26.  
  27. Algorytm na początku rozważa każdy z wierzchołków jako oddzielne drzewo, natomiast potem w pętli szuka dla każdego drzewa najlżejszą krawędź łączącą ją do kolejnego drzewa, dodaje ją do MST i łączy wierzchołki jako jedno drzewo do momentu, aż nie zostanie tylko jedno.
  28.  
  29. \subsection*{Lista kroków}
  30.  
  31. \begin{enumerate}
  32. \item Rozważ wszystkie wierzchołki jako oddzielne drzewa.
  33. \item Zadeklaruj MST jako puste.
  34. \item Dopóki jest więcej niż jedno drzewo rób po kolei dla każdego drzewa .
  35.    \begin{itemize}
  36.      \item  Znajdź krawędź o najmniejszym koszcie który łączy drzewo do kolejnego drzewa.
  37.      \item  Dodaj je do MST jeśli nie jest jeszcze dodane.  
  38.     \end{itemize}
  39. \item Zwróć MST.
  40. \end{enumerate}
  41.  
  42. \begin{figure}[ht]
  43. \centering
  44. \subfigure[Drzewo na początku, każdy wierzchołek tworzy oddzielne drzewo]{%
  45. \begin{tikzpicture}[node distance=2.3cm,thick]
  46.  
  47.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  48.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  49.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  50.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  51.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  52.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  53.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  54.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  55.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.6cm] {i};
  56.  
  57.    
  58.   \path[every node/.style={font=\sffamily\large}]
  59.     (a) edge node [above left] {1} (b)
  60.     (b) edge node [above] {2} (c)
  61.     (c) edge node [above] {4} (d)
  62.     (d) edge node [above right] {5} (e)
  63.     (f) edge node [above] {2} (g)
  64.     (e) edge node [below right] {7} (f)
  65.     (g) edge node [above] {3} (h)
  66.     (a) edge node [below left] {4} (h)
  67.     (b) edge node [above right] {5} (i)
  68.     (i) edge node [right] {1} (g)
  69.     (i) edge node [above left] {2} (h)
  70.     (c) edge node [above right] {2} (f);
  71.  
  72.  
  73. \end{tikzpicture}}
  74.  
  75. \subfigure[Drzewo po przejściu przez każdy wierzchołek]{%
  76. \begin{tikzpicture}[node distance=2cm,thick]
  77.  
  78.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  79.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  80.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  81.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  82.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  83.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  84.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  85.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  86.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.4cm] {i};
  87.  
  88.     \draw[-, ultra thick, gray!70] (a) -- (b);
  89.     \draw[-, ultra thick, gray!70] (c) -- (f);
  90.     \draw[-, ultra thick, gray!70] (d) -- (c);
  91.     \draw[-, ultra thick, gray!70] (d) -- (e);
  92.     \draw[-, ultra thick, gray!70] (i) -- (g);
  93.     \draw[-, ultra thick, gray!70] (i) -- (h);
  94.    
  95.   \path[every node/.style={font=\sffamily\large}]
  96.     (a) edge node [above left] {1} (b)
  97.     (b) edge node [above] {2} (c)
  98.     (c) edge node [above] {4} (d)
  99.     (d) edge node [above right] {5} (e)
  100.     (f) edge node [above] {2} (g)
  101.     (e) edge node [below right] {7} (f)
  102.     (g) edge node [above] {3} (h)
  103.     (a) edge node [below left] {4} (h)
  104.     (b) edge node [above right] {5} (i)
  105.     (i) edge node [right] {1} (g)
  106.     (i) edge node [above left] {2} (h)
  107.     (c) edge node [above right] {2} (f);
  108.  
  109.  
  110. \end{tikzpicture}}
  111. \centering
  112. \subfigure[Drzewo po zakończeniu]{%
  113. \begin{tikzpicture}[node distance=2cm,thick]
  114.  
  115.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!20] (b) {b};
  116.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (a) [below left of=b] {a};
  117.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (c) [right of=b] {c};
  118.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (d) [right of=c] {d};
  119.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (e) [below right of=d] {e};
  120.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (f) [below left of=e] {f};
  121.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (g) [left of=f] {g};
  122.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (h) [left of=g] {h};
  123.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!20] (i) [below of=c, node distance=1.4cm] {i};
  124.  
  125.     \draw[-, ultra thick, gray!70] (a) -- (b);
  126.     \draw[-, ultra thick, gray!70] (c) -- (f);
  127.     \draw[-, ultra thick, gray!70] (d) -- (c);
  128.     \draw[-, ultra thick, gray!70] (d) -- (e);
  129.     \draw[-, ultra thick, gray!70] (i) -- (g);
  130.     \draw[-, ultra thick, gray!70] (i) -- (h);
  131.     \draw[-, ultra thick, gray!70] (c) -- (b);
  132.     \draw[-, ultra thick, gray!70] (g) -- (f);
  133.  
  134.   \path[every node/.style={font=\sffamily\large}]
  135.     (a) edge node [above left] {1} (b)
  136.     (b) edge node [above] {2} (c)
  137.     (c) edge node [above] {4} (d)
  138.     (d) edge node [above right] {5} (e)
  139.     (f) edge node [above] {2} (g)
  140.     (e) edge node [below right] {7} (f)
  141.     (g) edge node [above] {3} (h)
  142.     (a) edge node [below left] {4} (h)
  143.     (b) edge node [above right] {5} (i)
  144.     (i) edge node [right] {1} (g)
  145.     (i) edge node [above left] {2} (h)
  146.     (c) edge node [above right] {2} (f);
  147. \end{tikzpicture}}
  148. \caption{Wizualizacja działania algorytmu. }
  149. \end{figure}
  150. \newpage
  151. W powyższej wizualizacji algorytm w pierwszym kroku znajduje najtańsze krawędzie :
  152.  
  153. \begin{figure}[H]
  154. \centering
  155. \begin{tabular}{|c|c|}
  156.     \hline
  157.     Drzewo& Krawędź \\
  158.     \hline
  159.     \{a\}& (a,b) \\
  160.     \hline
  161.     \{b\}& (a,b) \\
  162.     \hline
  163.     \{c\}& (c,d) \\
  164.     \hline
  165.     \{d\}& (c,d) \\
  166.     \hline
  167.     \{e\}& (d,e) \\
  168.     \hline
  169.     \{f\}& (c,f) \\
  170.     \hline
  171.     \{g\}& (g,i) \\
  172.     \hline
  173.     \{h\}& (h,i) \\
  174.     \hline
  175.     \{i\}& (g,i) \\
  176.     \hline
  177. \end{tabular}
  178. \end{figure}
  179.  
  180. potem w drugim :
  181.  
  182. \begin{figure}[H]
  183. \centering
  184. \begin{tabular}{|c|c|}
  185.     \hline
  186.     Drzewo& Krawędź \\
  187.     \hline
  188.     \{a,b\}& (b,c) \\
  189.     \hline
  190.     \{c,d,e,f\}& (f,g) \\
  191.     \hline
  192.     \{g,h,i\}& (f,g) \\
  193.     \hline
  194. \end{tabular}
  195. \end{figure}
  196.  
  197.  
  198. \subsection*{Złożoność}
  199. Mimo tego, że przez powyższą wizualizację można odnieść wrażenie, iż algorytm ten ma logaritmiczną złożność obliczeniową to jednak w implementacji jest ona równa $O(E\log{V})$, gdzie E to liczba  krawędzi a V liczba wierzchołków.
  200.  
  201. \subsection*{Źródła}
  202.  
  203. \begin{enumerate}
  204.  \item https://www.geeksforgeeks.org/boruvkas-algorithm-greedy-algo-9/
  205.  
  206.  \item https://en.wikipedia.org/wiki/Borůvka\%27s\_algorithm
  207. \end{enumerate}
  208.  
  209. \end{document}
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231. \begin{tikzpicture}[node distance=2cm,thick]
  232.  
  233.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm, fill=gray!50] (b) {b};
  234.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (a) [below left of=b] {a};
  235.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (c) [right of=b] {c};
  236.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (d) [right of=c] {d};
  237.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (e) [below right of=d] {e};
  238.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (f) [below left of=e] {f};
  239.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (g) [left of=f] {g};
  240.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (h) [left of=g] {h};
  241.   \node[circle,draw,font=\sffamily\large\bfseries, minimum width = 0.8cm,fill=gray!50] (i) [below of=c, node distance=1.4cm] {i};
  242.  
  243.  
  244.   \path[every node/.style={font=\sffamily\large}]
  245.     (a) edge node [above left] {3} (b)
  246.     (b) edge node [above] {2} (c)
  247.     (c) edge node [above] {4} (d)
  248.     (d) edge node [above right] {5} (e)
  249.     (f) edge node [above] {2} (g)
  250.     (e) edge node [below right] {7} (f)
  251.     (g) edge node [above] {3} (h)
  252.     (a) edge node [below left] {4} (h)
  253.     (b) edge node [above right] {5} (i)
  254.     (i) edge node [right] {1} (g)
  255.     (i) edge node [above left] {2} (h)
  256.     (c) edge node [above right] {2} (f);
  257.  
  258.  
  259. \end{tikzpicture}
  260.  
  261. \draw[-, ultra thick, gray!70] (a) -- (b);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top