\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[]{polski} 
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[small,bf]{caption}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {\bf Zaawansowane struktury danych } \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{#4}{#1}}
\newcommand{\figref}[1]{\textbf{Rysunek}~\textbf{\ref{fig:#1}}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex

\begin{document}
\newcounter{defcounter}
\lecture{Grafy dynamiczne --- 6 grudnia, 2010}{Zima 2010}{Paweł Rzechonek}{Paweł Kacprzak, Dawid Ryznar}


\section{Wprowadzenie}

W wielu problemach grafowych, grafy poddawane są dynamicznym zmianom, takim jak dodawanie, usuwanie wierzchołków lub krawędzi.

W ostatnich 20 latach rosło zainteresowanie grafami, które zmieniają swoją strukturę w czasie. W wyniki czego powstało wiele efektywnych algorytmów i struktur danych, które rozwiązują dynamiczne problemy grafowe.

\begin{enumerate}[{\bf {Definicja}}]
\item \label{def:1} \textbf{Uaktualnieniem grafu} będziemy nazywać operacje, która wstawia lub usuwa krawędzie czy wierzchołki lub zmienia wartości z nimi związane np. wagi.
	
\item \label{def:2} \textbf{Graf dynamiczny} jest to graf poddany sekwencji uaktualnień.
\setcounter{defcounter}{\value{enumi}}
\end{enumerate}
	
Celem dynamicznych algorytmów grafowych jest efektywne uaktualnianie rozwiązania problemu po zmianie struktury grafu, zamiast każdorazowego budowania rozwiązania od początku używając statycznego algorytmu. Chcemy także minimalizować czas pojedynczej operacji uaktualnienia. 
	
W naszych rozważaniach, $n$ będzie oznaczało liczbę wierzchołków w grafie. 
Grafy będziemy oznaczać literą~$G$, lasy literą~$F$, a drzewa literą~$T$.

Usunięcie wierzchołka będziemy rozumieć jako usunięcie wierzchołek oraz wszystkich krawędzi z nim incydentnych.

\section{Podział problemów}

Dynamiczne problemy grafowe możemy podzielić według rodzaju operacji, które są dozwolone:

\begin{enumerate}[{\bf {Definicja}}]
\setcounter{defcounter}{\value{enumi}}
	\item \label{def:3}Problem nazywamy \textbf{w pełni dynamicznym}, jeśli dozwolone jest zarówno wstawianie i usuwanie wierzchołków oraz krawędzi.
	\item \label{def:4}Problem nazywamy \textbf{wstępującym}, jeśli dozwolone jest tylko wstawianie.
	\item \label{def:5}Problem nazywamy \textbf{zstępującym}, jeśli dozwolone jest tylko usuwanie.
\setcounter{defcounter}{\value{enumi}}
\end{enumerate}

Zaprezentujemy jeden problem w pełni dynamiczny oraz jeden zstępujący. Wstępujący problem spójności grafu można rozwiązać używając struktury danych UNION-FIND w czasie $O(\alpha n)$, gdzie $\alpha$ to liczba uaktualnień i zapytań.

\section{Plan wykładu}

W pierwszej części zaprezentujemy strukturę danych - ET drzewo, na której będą bazować algorytmy przedstawiane w dalszej części wykładu:
\begin{itemize}
	\item W pełni dynamiczny algorytm rozwiązujący problem spójności grafu.
	\item Zstępujący algorytm znajdujący minimalne drzewo spinające grafu.
\end{itemize}

\section{ET drzewa}

\subsection{Wprowadzenie}

Oba zaprezentowane algorytmy będą używały ET drzew jako struktury danych. ET drzewa zostały wynalezione przez M.Henzinger i V.King w ich wspólnej pracy $[1]$.

Drzewo, które będziemy chcieli reprezentować przy pomocy ET drzewa będziemy nazywać drzewem reprezentowanym.

Dla przypomnienia, cyklem Eulera w grafie nazywamy cykl, który przechodzi każdą krawędź dokładnie raz. Jako cykl Eulera po ukorzenionym drzewie~$T$, będziemy rozumieć cykl Eulera po grafie~$G$, powstałym z~$T$ przez zastąpienie każdej krawędzi przez dwie krawędzie skierowane z przeciwnymi zwrotami. Cykl ten zaczyna się i kończy w korzeniu~$T$.

Cykl Eulera po drzewie~$T$, przechodzi każdą krawędź dokładnie dwa razy: raz wchodząc do poddrzewa do którego prowadzi krawędź, a drugi raz wychodząc z tego poddrzewa. Możemy myśleć o cyklu Eulera po drzewie~$T$ jako o~DFS, który zaczyna się i kończy w korzeniu \figref{euler}.

\textbf{Wniosek} ET drzewo będzie miało $O(n)$ wierzchołków.

\begin{figure}[htp]
\centering
\includegraphics[clip, scale=0.6]{tree.pdf}
\caption{Przykładowe drzewo~$T$ oraz jego cykl Eulera. Porządek w jakim wierzchołki są odwiedzane pokazują czerwone strzałki - zaczynamy od korzenia $R$. Sekwencja kolejnych odwiedzeń to: $R\ A\ R\ B\ C\ D\ C\ E\ C\ B\ F\ B\ G\ B\ R$.}
\label{fig:euler}
\end{figure}

ET drzewo reprezentuje sekwencję odwiedzin kolejnych wierzchołków w cyklu Eulera po drzewie~$T$. Sekwencję będziemy przechowywać używając zbalansowanego drzewa binarnego, wzbogaconego o operacje na listach - \texttt{SPLIT(v)} oraz \texttt{JOIN(v, w)}. Kluczem węzła w tym drzewie będzie jego czas odwiedzenia w cyklu Eulera po drzewie reprezentowanym. Łatwą implementacją jest drzewo splay. 

Każdy wierzchołek w drzewie~$T$, które chcemy reprezentować będzie zawierał wskaźnik do pierwszego oraz ostatniego odwiedzenia w sekwencji reprezentowanej przez ET drzewo \figref{ett}.

\begin{figure}[htp]
\centering
\includegraphics[clip, scale=0.6]{eulertourtree.pdf}
\caption{ET drzewo roprezentuje sekwencję odwiedzeń wierzchołków, która zaczyna sie i kończy w korzeniu. Wskaźniki z tej sekwencji prowadzą do wierzchołków reprezentowanego drzewa. Każdy wierzchołek z reprezentowanego drzewa ma wskaźniki do pierwszej i ostatniej wizytacji w sekwencji. (na rysunku zaznaczone są jedynie wskaźniki prowadzące od i do korzenia).}
\label{fig:ett}
\end{figure}

ET drzewa przechowują w łatwy sposób informacje o poddrzewach reprezentowanego drzewa. Rozważmy wierzchołek $v$ z drzewa, które chcemy reprezentować. Wszystkie wierzchołki z poddrzewa ukorzenionego w $v$ znajdują się w ET drzewie pomiędzy pierwszym, a ostatnim odwiedzeniem $v$.

\subsection{Operacje}

Chcemy na ET drzewie wykonywać 3 podstawowe operacje:

\begin{itemize}
	\item \texttt{FINDROOT(v)} - znajduje korzeń drzewa, które zawiera $v$. W cyklu Eulera po drzewie~$T$ korzeń jest odwiedziany pierwszy oraz ostatni. Wystarczy więc wyszukać minimum lub maksimum w ET drzewie.
	\item \texttt{CUT(v)} - Chcemy odciąć poddrzewo ukorzenione w $v$. Cykl Eulera po poddrzewie ukorzenionym w $v$, jest jednym spójnym blokiem sekwencji wizytacji zaczynającym się i kończącym w $v$. Wystarczy więć wykonać operacje listową \texttt{SPLIT} przed pierwszym odwiedzeniem $v$ oraz po ostatnim odwiedzeniu $v$. W wyniku tych operacji dostaniemy ET drzewo poddrzewa ukorzenionego w $v$ oraz 2 ET drzewa, które pokrywają sekwencję odwiedzenia przez wejściem do poddrzewa $v$ oraz po wyjściu z niego. Wykonujemy \texttt{JOIN} na tych 2 ostatnich sekwencjach. W wyniku dostaniemy ET drzewo odciętego poddrzewa ukorzenionego w $v$ oraz ET drzewa~$T$ bez poddrzewa ukorzenionego w $v$.
	\item \texttt{LINK(v,w)} - Chcemy umieścić krawędź pomiędzy dwoma drzewami, które zawierają odpowiednio $v$ oraz $w$. Wierzchołek $v$ ma zostać synem $w$. W ET drzewie taka operacja musi umieszczać sekwencję przejścia poddrzewa ukorzenionego w $v$ bezpośrednio po pierwszym odwiedzeniu $w$ oraz bezpośrednio przed jego drugim odwiedzeniem. Możemy to zrobić wykonując SPLIT na ET drzewie zawierającym $w$ zaraz po pierwszym odwiedzeniu $w$. Wystarczy teraz połaczyć cześć do pierwszego odwiedzenia $w$, ET drzewo w którym znajduję się $v$, drzewo złożone z singletona $w$ oraz cześć po pierwszym odwiedzeniu $w$. 

\end{itemize}
Wszystkie powyższe 3 operacje wymagają stałej ilości standardowych operacji, które działają na zbalansowanym drzewie binarnym w czasie $O(\log n)$, stąd każda z nich wymaga czasu $O(\log n)$

\section{Problem spójności dynamicznego grafu}

Chcemy odpowiadać na pytania postaci:
\begin{itemize}
	\item \texttt{CONNECTED(v,w)} - zwraca \texttt{TRUE} wtedy i tylko wtedy gdy istnieje ścieżka z $v$ do $w$ w grafie.
	\item \texttt{CONNECTED(G)} - zwraca \texttt{TRUE} wtedy i tylko wtedy gdy graf~$G$ jest spójny.
\end{itemize}
Przedstawimy algorytm, który uaktualnia strukture grafu w czasie $O(\log^2 n)$ oraz odpowiada na powyższe pytania w czasie $O(\log n)$.

Gdybyśmy rozważali wariant wstępujący tego problemu, możemy rozwiązać go w następujący sposób:

\begin{itemize}
	\item zbudować las spinający $F$ grafu $G$.
	\item zastosować ET drzewo do zarządzania tym lasem.
\end{itemize}
W pełni dynamicznej wersji problemu, nie jest już tak łatwo.

\textbf{Idea:} Będziemy przechowywać $\log n$ lasów spinających $F_0, F_1, \ldots, F_{\log n}$. Każdy jako ET drzewo.

Każdej krawędzi przypiszemy rangę. Ranga będzie liczbą naturalną z przedziału od $0$ do $\log n$. Będzie ona mogła jedynie zmniejszać się w czasie.

\begin{enumerate}[{\bf {Definicja} }]
\setcounter{defcounter}{\value{enumi}}
	\item $G_i$ będzie grafem składającym się z krawędzi o randze nie większej niż $i$. Wtedy $G = G_{\log n}$.
	\item $F_i$  będzie lasem spinającym grafu $G_i$.
\setcounter{defcounter}{\value{enumi}}
\end{enumerate}

W czasie działania algorytmu będziemy utrzmywać 2 niezmienniki:

\begin{enumerate}[{\bf {Niezmiennik} 1}]
	\item Każda spójna składowa $G_i$ ma co najwyżej $2^i$ wierzchołków.
	\item $F_{\log n}$ jest minimalnym lasem spinającym grafu $G$, używając rangi krawędzi jako wagi. $F_i = G_i \cap F_{\log n}$.
\end{enumerate}

Chcemy, żeby nasza struktura składająca się z $\log n$ lasów spinających implementowała poniższe 4 operacje:

\begin{itemize}

	\item \texttt{INSERT(e=(v,w))}:

	Chcemy umieścić w grafie krawędź $(v,w)$. Ustawiamy rangę tej krawędzi na $\log n$ oraz uaktualniamy listy sąsiedztwa $v$ oraz $w$, dodając odpowiedni wierzchołek do nich.
	Dodatkowo wywołujemy procedury \texttt{FINDROOT(v)} oraz \texttt{FINDROOT(w)}. Jeśli ich wyniki są różne, to w wyniku dodania krawędzi drzewa zawierające $v$ oraz $w$ połączą się. Jeśli tak jest, dodajemy krawędź $e$ do $F_{\log n}$.

	\item \texttt{DELETE(e=(v,w))}:
	Najpierw usuń krawędź $e$ z list sąsiedztwa $w$ oraz $v$, następnie:
	\begin{itemize}
	  \item[-] jeśli $e$ należy do $F_{\log n}$:
	    \begin{itemize}
	      \item[-] usuń $e$ z każdego $F_i$ dla $i \geq ranga(e)$.
	      \item[-] poszukaj krawędzi zastępczej, która połączy $v$ oraz $w$:
	      \begin{itemize}
		\item[-] krawędź zastępcza nie może mieć rangi mniejszej niż $ranga(e)$\newline z niezmiennika 2 - każdy $F_i$ jest MST względem rangi krawędzi.
	      \end{itemize}
		\item[-] for $i = ranga(e)$ to $\log n$
		  \begin{itemize}
		    \item[-] niech $T_v$ będzie drzewem zawierającym $v$, a $T_w$ drzewem zawierającym $w$.
		    \item[-] w razie potrzeby zamieńmy $v$ z $w$ aby zachodziło $|T_v| \leq |T_w|$.
		    \item[-] z niezmiennika 1, wiemy, że $\left|{T_v}\right| + \left|{T_w}\right| \leq 2^i$, stąd $\left|{T_v}\right| \leq 2^{(i+1)}$, a to oznacza, że możemy zdegradować wszystkie krawędzie z $T_v$ do poziomu $i-1$, zachowując dalej niezmiennik.
		    \item[-] dla każdej krawędzi $e'=(x,y)$, gdzie $x$ należy do $T_v$ oraz $ranga(e') = i$:
		    \item[] \ \ \ \ - jeśli $y$ należy do $T_w$: dodaj $e'$ do $F_i, F_{(i+1)},\ldots, F_{\log n}$.
		    \item[] \ \ \ \ - w.p.p. zmniejsz range $e'$ do $i-1$.
		   \end{itemize}
	    \end{itemize}
	\end{itemize}
	\item \texttt{CONNECTED(v, w)}:

	Odpowiada na pytanie, czy istnieje ścieżka z $v$ do $w$:
	\begin{algorithmic}        
	\STATE return FINDROOT(v) == FINDROOT(w) w $F_{\log n}$
	\end{algorithmic}
	
	\item \texttt{CONNECTED(G)}               
	\begin{algorithmic}        
	\STATE $r =$ \texttt{PATH-UP(v)}, gdzie $v$ jest dowolnym wierzchołkiem z~$G$.
	\STATE if size[v] = n then
	\STATE \ \ \ \  return TRUE
	\STATE else
	\STATE \ \ \ \  return FALSE

	\end{algorithmic}
	
\begin{itemize}
 \item \texttt{PATH-UP(v)} zwraca korzeń ET drzewa zwierającego $v$ - nie mylić z korzeniem drzewa reprezentowanego. Wędruje w górę ET drzewa.
 \item \texttt{size[v]} zwraca ilość wierzchołków w poddrzewie ET drzewa zakorzenionego w $v$ wraz z $v$. Zarządzamy tą wartością przez wzbogacenie zbalansowanego BST, w którym przechowujemy ET drzewo. Nie zmienia to asymptotycznego kosztu operacji na tym BST.
\end{itemize}

\end{itemize}

Dodatkowo musimy wzbogacić nasza strukturę danych, aby móc wykonywać \texttt{DELETE} w rządanym czasie:
\begin{itemize}
	\item chcemy sprawdzać czy $|T_v| \leq |T_w|$ w $O(1)$, możemy to zrobić przez standardowe wzbogacenie struktury przez związanie rozmiarów poddrzew z wierzchołkami.
	\item dla każdego wierzchołka w poddrzewie ukorzenionym w $v$ w $F_i$:
	chcemy sprawdzać czy poddrzewo ukorzenione w $v$ zawiera jakieś wierzchołki incydentne do krawędzi o $randze = i$. Szukamy następnej krawędzie o randze $i$ incydentnej do jakiegoś $x$ należącego do $T_v$ w $O(\log n)$ znajdując nastepnika w drzewie i skacząc po pustych poddrzewach.
\end{itemize}
	
\textbf{Analiza kosztu}
\begin{itemize}
	\item \texttt{INSERT}:
	- stała liczba podstawowych operacji na ET drzewie, każda działa w czasie $O(\log n)$ stąd czas działania \texttt{INSERT} wynosi $O(\log n)$.	
	\item \texttt{CONNECTED(v,w)}:
	- dwa wywołania \texttt{FINDROOT}, każde działa w czasie $O(\log n)$ stąd cała procedura działa w czasie $O(\log n)$.
	\item \texttt{CONNECTED(G)}
	- jedno przejście w górę drzewa o wysokości $O(\log n)$ - czas $O(\log n)$.
	
	\item \texttt{DELETE}
	\begin{itemize}
		\item Główny koszt to usuwanie krawędzi z co najwyżej $\log n$ lasów spinających, każde usunięcie zajmuje czas $O(\log n)$, stąd koszt to $O(\log^2 n)$.
		\item Szukanie krawędzi zastępczej. Tutaj analiza jest zamortyzowana i opiera się na fakcie, że ranga każdej krawędzi jest zmniejszana co najwyżej $\log n$ razy, a najbardziej zewnętrzna pętla, w której to robimy wykonuje się też $\log n$ razy, stąd zamortyzowany koszt szukania krawędzie zastępczej wynosi $O(\log^2 n)$.
		\item Całkowity koszt \texttt{DELETE} jest zamortyzowany i wynosi $O(\log^2 n)$.
	\end{itemize}
\end{itemize}	
	
\textbf{Poprawienie czasu}

Czysto teoretycznie, możemy poprawić czas odpowiadania na pytania oraz czas wykonywania uaktualnień grafu. Osiągniemy to używając do przechowywania naszych lasów spinających B-drzew o stopniu $O(\log n)$ zamiast drzew BST. W rezultacie otrzymujemy poniższe czasy:

\begin{itemize}
	\item \texttt{CONNECTED} - $O(\log n / \log \log n)$.
	\item \texttt{INSERT} - $O(\log^2 n / \log \log n)$.
	\item \texttt{DELETE} - $O(\log^2 n / \log \log n)$.
\end{itemize}

\section{Zstępujący algorytm MST}
Zaprezentuję algorytm i strukturę danych do utrzymywania lasu rozpinającego. Będąc precyzyjnym algorytm i struktura danych zużywa $O\left( n^{\frac{1}{3}}\log n \right)$ zamortyzowanego czasu na operację uaktualnienia grafu. Dodatkowo jest w stanie odpowiadać na pytanie w $O\left( 1\right)$ jest to czas najgorszego przypadku. Rozważmy problem utrzymania minimalnego lasu rozpinającego (\textit{msf}) podczas wykonywania operacji usuwania krawędzi. Załóżmy że mamy ważony graf $G=\left\langle V,E \right\rangle $, gdzie $V$ to zbiór wierzchołków $\left(|V|=n\right)$, a $E$ to zbiór krawędzi $\left(|E|=m\right)$. Chcemy utrzymywać minimalny las rozpinający $F$ podczas wykonywania operacji uaktualniania grafu:
\begin{itemize}
\item \textit{delete$\left(u,v\right) $}: Usuwamy krawędź $\left\lbrace u,v\right\rbrace$ z grafu $G$. Jeśli $\left\lbrace u,v\right\rbrace  \in F$, to:
\begin{itemize}
\item usuwamy $\left\lbrace u,v \right\rbrace$ z $F$.
\item zwracamy najlżejszą krawędź $e \in G \setminus F$ która połączy na nowo $F$, jeśli taka krawędź $e$ nie istnieje zwracamy \textit{null}.
\end{itemize}
\end{itemize}
Co więcej struktura będzie pozwalała odpowiadać na następujące pytanie:
\begin{itemize}
\item \textit{connected$\left( u,v \right)$}: zwraca \textit{true} jeśli między wierzchołkami istnieje ścieżka oraz \textit{false} jeśli taka ścieżka nie istnieje.
\end{itemize}
W 1985 Fredrickson wprowadził strukturę danych \textit{topology trees}, która rozwiązywała ten probelm w czasie $O\left( \sqrt{m}\right)$ jest to czas potrzebny na przeprowadzenie aktualizacji. Czas poświęcony na odpowiedź na pytanie czy istnieje ścieżka pomiędzy dwoma wierzchołkami to $O\left( 1\right)$.
W 1992 Eppstein osiągną czas $O\left( \sqrt{n}\right)$ używając \textit{sparsification technique}.
W 1997 Monika Rauch Henzinger i Valerie King zaprezentowały strukturę danych, która porzebuje $O\left( n^{\frac{1}{3}}\log n \right)$ zamortyzowanego czasu na aktualizację i odpowiada na pytania w $O\left( 1\right)$ jest to czas najgorszego przypadku. Ten algorytm zostanie przedstawiony w poniższym dokumencie.

\section{Utrzymywanie minimalnego lasu rozpinajacego}
Przedstawię teraz algorytm służący do utrzymywania minimalnego lasu rozpinającego z dozwoloną operacją usuwania krawędzi. Bez straty ogólności załóżmy, że wagi na krawędziach są rozróżnialne. Na początku wyliczamy minimalny las rozpinający $F$ dla grafu $G$. Możemy użyć do tego algorytm Prima używającego kopców fibonacciego. Czas poświęcony na wyliczenie msf to  $O\left(m+n \log n \right)$. Niech $m^{'}_{in}$ oznacza liczbę krawędzi nie będących w $F$ a będącecyh w $G$ (\textit{niedrzewnych}), mam tutaj na myśli stan $F$ i $G$ na początku (przed wykonaniem aktaulizacji na strukturze). Ponadto niech $k = m^{'^{\frac{1}{3}}}_{in} \log n$. Sortujemy niedrzewne krawędzie względem wagi i rozmieszczamy je w $m^{'}_{in}/k$ poziomach, każdy poziom ma rozmiar $k$. $K$ najlżejszych znajdzie się na poziomie $0$, kolejne $k$ najlżejszych znajdzię się na poziomie 1 i tak dalej. Zbiór krawędzi z poziomu $i$ oznaczmy przez $E_{i}$. Co więcej wszystkie krawędzie należące do $F$ (drzewne) umieszczamy w $E_{0}$.

Podczas wykonywania algorytmu, poziom przypisany do krawędzi pozostaje niezmieniony. $F$ oznacza minimalny las rozpinający dla całego grafu $G$. Dla każdego $i=0,1,..,(m^{'}_{in}/k)-1$ niech $F_{i}$ oznacza minimalny las rozpinający dla grafu ze zbiorem wierzchołków $V$ i zbiorem krawędzi $\bigcup_{j\leqslant i}  E_j$. Na początku dla każdego $i$, $F_i = F$, jednakże podczas wykonywania aktualizacji struktury może się to pozmieniać, ponieważ niedrzewne krawędź z dowlonego poziomu może stać się krawędzią drzewną. Mamy następujący niezmienik $F_0 \subseteq F_1 \subseteq \ldots \subseteq F_{\left(m^{'}_{in}/k\right) -1} = F$, który zostaje zachowany podczas działania algorytmu. Niech $T_{i}\left(x\right)$ oznacza drzewo w $F_i$ zawierające $x$, a $T\left(x\right)$ oznacza drzewo w $F$ zawierające $x$.

\subsection{Główna idea}
Jeśli usuwamy krawędz $e = \left\lbrace u,v \right\rbrace$ taką że $e \not\in F$, to $F$ nie zmienia się, nie jest to zbyt ciekawy przypadek. Załóżmy więc, że usuwamy krawędź $e$, która na $i$ - tym poziomie jest krawędzią drzewną. Dla każdego lasu $F_{j}$, gdzie $j \geqslant i$ drzewo zawierające tą krawędź zostanie podzielone na dwa drzewa $T_{j} \left(u\right)$ i $T_{j}\left(v\right)$. Szukamy najlżejszej krawędzi niedzewnej która połączy na nowo $T\left(u\right)$ i $T\left(v\right)$, zbierając i testując zbiór $S$ kandydujących krawędzi z poziomu $i$. Jeśli takiej krawędzi nie znajdziemy powtarzamy tą procedurę na poziomie $i+1$ aż do wyczerpania wszystkich poziomów. 

\bigskip

Teraz opiszemy operację uaktualniania:

\bigskip

\textit{delete(u,v)}: usuwamy krawędź $\left\lbrace u,v\right\rbrace$ z każdego miejsca w strukturze w którym występuje. Jeśli $\left\lbrace u,v\right\rbrace$ jest krawędzią drzewną na poziomie $i$ wtedy wywołujemy procedurę \textit{Replace(i,u,v)}.

W algorytmie przedstawionym poniżej procedura \textit{Search$ \left( T_{i}\left( u \right) \right)$} zwraca wszystkie niedrzewne  krawędzie z poziomu $i$, które są incydentne z drzewem $T_{i}\left( u \right)$. Procedura \textit{Search} zostanie dokładnie opisana w puźniejszej części tego dokumentu.

\bigskip

\textit{Replace$\left( i,u,v\right) $}
\begin{enumerate}
\item Wykonujemy \textit{Search$\left(T_{i}\left(u\right)\right)$} , \textit{Search$\left(T_{i}\left(v\right)\right)$}. 
\begin{itemize}
\item Jeden z \textit{Search -  ów} się zatrzymał i zwrócił niepusty wynik, niech $S$ oznacza wynik zwrócony przez ten \textit{Search}.
\item \textit{Search - e} zwróciły puste wyniki wtedy $S$ będzie zbiorem wszystkich niedrzewnych krawędzi z poziomu $i$.
\end{itemize}
\item Sprawdzamy każdą krawędź z $S$ czy łączy $T_{i}\left(u\right)$ i $T_{i}\left(v\right)$.
\begin{itemize}
\item znaleźlismy krawędź która łączy $T_{i}\left(u\right)$ i $T_{i}\left(v\right)$, wprowadzamy tą krawędź do $F$ oraz do każdego lasu  $F_{j}$, gdzie  $j\geqslant i$.
\item w $S$ nie znaleźliśmy szukanej krawędzi. Jeśli $i$ nie jest ostatnim poziomem wywołujemy \textit{Replace$\left( i+1,u,v\right)$}. Jeśli $i$ jest ostatnim poziomem procedura \textit{Replac} kończy się, nie znajdujemy zastępczej krawędzi.
\end{itemize}
\end{enumerate}
 
\subsection{Struktura danych}
Każde drzewo w dowolnym $F_{i}$ i w $F$ będzie reprezentowane jako ET-drzewo, zaowocuje to dwiema korzyściami:
\begin{itemize}
\item Stały czas potrzebny na sprawdzenie czy jakaś krawędź łączy dwa drzewa.
\item Szybko możemy odnaleść niedrzewne krawędzie w $E_{i}$, które są incydentne z zadanym drzewem.
\end{itemize}

Aby zmniejszyć koszty będziemy trzymać tylko te $F_{i}$ w pamięci, których $i$ jest wielokrotnoscią $m^{'^{\frac{1}{3}}}_{in}/\log{n}$. Każde ET-drzewa jest przechowywane w B-drzewie o stopniu $d$. Dzięki temu będziemy mogli:
\begin{itemize}
\item Zaimplementować usuwanie i dodawanie krawędzi w $F$ w czasie $O\left(d \log _d  n \right)$ (\textit{split} lub \textit{join} wykonany na ET-drzewie).
\item Sprawdzać czy dwa wierzchołki są w tym samym drzewie w czsie $O\left(\log _d n\right)$
\end{itemize}

Jesli przyjmiemy że $d=n^{\alpha}$, gdzie $\alpha$ - dodatnia stała to:
\begin{itemize}
\item  $O\left(d \log_d n\right) \Rightarrow  O\left(d\right)$.
\item  $O\left(\log_d n\right) \Rightarrow  O\left(1\right)$.
\end{itemize}

Struktura danych będzie składać się z następujących elementów:
\begin{enumerate}
\item Każda krawędź ma przypisany swój poziom $i$, oraz bit który informuje czy jest to krawędź drzewna czy też nie.
\item Niech $k^{'} = max\left\lbrace m^{'^{\frac{1}{3}}}_{in}\log n , n^{\epsilon}\right\rbrace$, gdzie $\epsilon \in ( 0, \frac{1}{3} ]$. Dla każdego drzewa w $F$ reprezentujemy je jako ET-drzewo, które jest zaimplementowane za pomocą B-drzewa o stopniu $k^{'}$.
\item Niech $c = m^{'^{\frac{1}{3}}}_{in}\log n$. Mapujemy każdy poziom $i$ na poziom $j$ taki, że $f(i) = j $, gdzie $f(i) = c  \lfloor \frac{i}{c} \rfloor $ . Dla każdego poziomu $j$ takiego że $c | j $:
\begin{enumerate}
\item Każde drzewo z $F_j$ jest reprezentowane jako ET-drzewo i jest trzymane w B-drzewie o stopniu $2$. 
\item Dla każdego wierzchołka $v$ tworzymy liste $L_{j}\left( v \right)$, która zawiera:
\begin{itemize}
\item Wszystkie niedrzewne krawędzie incydentne do $v$ które są na jakimkolwiek poziomie $i$, gdzie $i \in f^{-1}\left(j\right)$.
\item Wszystkie drzewne krawędzie incydentne do $v$ które są na jakimkolwiek poziomie $i > j$, gdzie $i \in f^{-1}\left(j\right) $.
\end{itemize}
\item Zaznaczamy każde wystąpienie wierzchołka $v$ którego lista $L_{j}\left(v\right)$ nie jest pusta. Każdy wierzchołek w ET-drzewie jest zaznaczony jeżeli drzewo zakorzenione w nim zawiera zaznaczony wierzchołek. 
\end{enumerate}
\end{enumerate}

\subsection{Procedura \textit{Search}}
\textit{Search$\left(T_{i}\left( u \right)\right)$} - zwraca wszystkie niedrzewne krawędzie z poziomu $i$ incydentne z $T_{i}\left( u \right)$. Zaczynamy od przeszukania $T_{f\left(i\right)}\left(u\right)$, które jest poddrzewem $T_{i}\left(u\right)$. Sprawdzamy wszystkie krawędzie  należace do $L_{i}\left(v\right)$ dla każdego wierzchołka $v$ w drzewie $T_{i}\left(u\right)$. Niedrzewne krawędzie z poziomu $i$ są po kolei wybierane, a wszystkie drzewne krawędzie z poziomu $i^{'}$, $f\left(i\right) < i^{'} \leq i$ prowadzą do innych drzew wchodzących w skład $F_{f\left(i\right)}$. Wszystkie takie krawędzie drzewne prowadzą do innych drzew $F_{f\left(i\right)}$, które są poddrzewami $T_{i}\left(u\right)$. Wszystkie poddrzewa $T_{i}\left(u\right)$ zostaną sprawdzone w ten sposób.

\bigskip
Procedura \textit{Search} w pseudokodzie:
\bigskip

\textit{Search$\left(T_{i}\left( u \right)\right)$}

\begin{enumerate}
\item $S^{'} \leftarrow \emptyset $;
\item \textit{listadrzew} $\leftarrow T_{f\left(i\right)}\left(u\right)$;
\item Powtarzamy dopóki \textit{listadrzew} $\neq \emptyset$;
\begin{enumerate}
\item Usuwamy jedno ET-drzewo z \textit{listadrzew};
\item Dla każdego zaznaczonego wierzchołka $x$ w ET-drzewie oraz dla każdej krawędzi $\left\lbrace x,y \right\rbrace \in  L_{f\left(i\right)}\left(x\right)$:
\begin{itemize}
\item if $\left\lbrace x,y \right\rbrace$ jest krawędzią niedrzewną dodaj  ją do $S^{'} $;
\item else if $\left\lbrace x,y \right\rbrace$ jest krawędzią drzewną na poziomie $ l \leqslant i $  to dodaj $T_{f\left(i\right)}\left( y \right)$ do \textit{listadrzew}; 
\end{itemize}
\end{enumerate}
\item Return $S^{'} $;
\end{enumerate}

\subsection{Analiza złożoności}

Niech $t$ oznacza liczbę krawędzi w $F$ przed wykonaniem jakiejkolwiek aktualizacji w grafie. W koszt stworzenia struktury wliczamy kolejno:
\begin{enumerate}
\item Obliczenie minimalnego lasu rozpinającego. Zajmie to czas  $O\left(m+n \log n \right)$. 
\item Posortowanie i podzielenie wszystkich krawędzi niedrzewnych  $O\left( m \log m \right)$.
\item Stowrzenie ET-drzew dla $F$, oraz dla każdego lasu $F_{j}$, gdzie $c | j$. Zajmuje to czas proporcjonalny do wilkości każdego lasu czyli $O\left(m^{'}_{in} + t \right)$.
\item Stworzenie wszystkich list $L$ zajmuje czas propocjonalny do liczby niedrzewnych krawędzi $O\left(m^{'}_{in}\right)$.  
\end{enumerate}

Koszt usunięcia niedrzewnej krawędzi: Usunięcie niedrzewnej krawędzi z któregokolwiek poziomu może spowodować koniecznść zrestartowania znacznika na wierzchołkach w niektórych ET-drzewach. W najgorszym przypadku będzie to restartowanie znacznika na wszystkich wierzchołkach na ścieżce aż do korzenia. Zajmie to maksymalnie czas  $O\left(\log n \right)$.

Usunięcie i wstawienie drzewnej krawędzi do struktury:

W czas poświęcony na usunięcie drzewnej krawędzi wchodzi:

\begin{itemize} 
\item Usunięcie krawędzi z odpowiedniego ET-drzewa wchodzącego w skład $F$. Czas $O\left(k^{'}\right)$ 
\item Usunięcie krawędzi z  pojedynczego ET-drzewa $O\left(\log n \right)$. Trzeba to zrobić dla każdego lasu $F_{j}$, gdzie $c | j$. W sumie daje to czas $O\left(\left(\left( m^{'}_{in}/ k\right)/c\right)\log n \right)$  
\end{itemize}
Czas poświęcony na dodanie drzewnej krawędzi jest propocjonalny do czasu potrzebnego na usunięcie drzewnej krawędzi.


Szukanie zastępczej krawędzi:
Niech $w\left(T\right)$ dla pewnego drzewa $T$ w pewnym lesie $F_{i}$ oznacza wagę drzewa $\left( w\left(T\right) = \sum_{v \in T}  |L_{f\left(i\right)}\left(v\right)| \right)$. Aby przejść od korzenia do liścia w ET-drzewie w celu odnalezienia zaznaczonego wierzchołka, albo przejść od zaznaczonego liścia do korzenia potrzeba poświęcić $O\left( \log n \right)$ czasu. Dlatego koszt \textit{Search$\left( T_{i}\left(x\right)\right)$} to $O\left(w\left(T_{i}\left(x\right)\right) \log n \right)$. 
Koszt wykonywania \textit{Replace} to koszt \textit{Search} plus koszt sprawdzenia każdej krawędzi ze zbioru $S$ czy łączy na nowo dwa drzewa. Sprawdzenie odbywa się w czasie $O\left(1\right)$. Wielkość zbioru $S$ to $O\left(min\left\lbrace k,w\left(T\right) \right\rbrace \right)$. 
Zauważamy że jest co najwyżej $k$ krawędzi na każdym poziomie. Każda lista $L_{j}\left(v\right)$ zawiera co najwyżej krawędzie z $c$ poziomów. Wnioskujemy więc, że $w\left(T\right) \leqslant ck$.
Podsumuwując koszt szukania zastępczej krawędzi to $O\left(m{'^{\frac{1}{3}}} \log n  + n^{\epsilon}\right)$.

Zauważamy również że odpowidź na pytanie \textit{connected(u,v)} zostaje znaleziona w czasie $O\left(1\right)$ użuywając ET-drzew dla przechowywania drzew z lasu $F$.

\begin{thebibliography}{99}
\bibitem{} Monika Rauch Henzinger, Valerie King, Maintaining Minimum Spanning Trees in Dynamic Graphs.
\bibitem{} Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Dynamic Graph Algorithms.
\bibitem{} Robert E. Tarjan, Renato F. Werneck, Dynamic Trees in Practice.
\bibitem{} Camil Demetrescu, Giuseppe F. Italiano, Dynamic Shortest Paths and Transitive Closure: Algorithmic Techniques and Data Structures.
\bibitem{} Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni, Fully Dynamic Algorithms for Maintaining Shortest Paths Trees.
\bibitem{} Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni, Incremental Algorithms for the Single-Source Shortest Path Problem.
\bibitem{} Stephen Alstrup, Jacob Halm, Kristian de Lichtenberg, Mikkel Thorup, Maintaining Information in Fully Dynamic Trees with Top Trees.
\bibitem{} Daniel D. Seator, Robert Endre Tarjan, A Data Structure for Dynamic Trees.
\bibitem{} Stephen Alstrup, Jacob Halm, Kristian de Lichtenberg, Mikkel Thorup, Minimizing Diameters of Dynamic Trees.
\bibitem{} Greg N. Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees.
\bibitem{} Greg N. Frederickson, Ambivalent Data Structures for Dynamic 2-Edge Connectivity and k - Smallest Spanning Trres.
\end{thebibliography}


\end{document}