\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Dynamic Spanning Trees}\id{dynchap}%

\section{Dynamic graph algorithms}

In many applications, we often need to solve a~certain graph problem for a~sequence
of graphs that differ only a~little, so recomputing the solution from scratch for
every graph would be a~waste of time. In such cases, we usually turn our attention
to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure
that remembers a~graph and offers operations that modify the structure of the graph
(let's say by insertion and deletion of edges) and also operations that query the
result of the problem for the current state of the graph.
A~typical example of a~problem solved by such algorithms is dynamic maintenance of
connected components:

\problemn{Dynamic connectivity}
Maintain an~undirected graph under a~sequence of the following operations:
\itemize\ibull
\:$\<Init>(n)$ --- create a~graph with $n$~isolated vertices,\foot{%
The structure could support dynamic additional and removal of vertices, too,
but this is easy to add and infrequently used, so we will rather use a~fixed
set of vertices for clarity.}
\:$\<Insert>(G,u,v)$ --- insert an~edge $uv$ to~$G$ and return its unique
identifier (assuming that the edge did not exist yet),
\:$\<Delete>(G,e)$ --- delete an~edge specified by its identifier from~$G$,
\:$\<Connected>(G,u,v)$ --- test if $u$ and~$v$ are in the same connected component of~$G$.
\endlist

\para
We have already encountered a~special case of dynamic connectivity when implementing the
Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
any edges from the graph (this is sometimes called a~\df{semidynamic graph algorithm}),
which makes the problem substantially easier. We mentioned the Union-Find data structure
of Tarjan and van Leeuwen ....


%--------------------------------------------------------------------------------

\section{Sleator-Tarjan trees}


\endpart
