\documentclass[12pt,a4paper]{article}
\usepackage{graphicx}
\graphicspath{{eps/}{pdf/}}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

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

\noindent
{\bf Data Mining 2: Frequent Pattern Mining} \hfill Summer 2018 \\
Christian Borgelt \hfill from 16.07.2018

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

\vskip3ex
\centerline{\bf Exercise Sheet 11}

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

\subsubsection*{Exercise 40 \quad\rm Searching for Frequent Subgraphs}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Why do we exclude the removal of proper bridges
     when assigning unique parents?
\item[b)\hfill]
     \parbox[t]{90mm}{How many different spanning trees does the
     graph / molecule shown on the right possess?
     Justify your answer!}\hskip16mm
     \lower6.8ex\hbox{\includegraphics{fpmex-4}}
\item[c)\hfill]
     Why is the number of possible code words usually (much) larger
     than the number of spanning trees?
     What additional choices does one have?
\item[d)\hfill]
     Why does a coding scheme based on spanning trees in which
     edges closing cycles are listed after the spanning tree edges
     ensure that we can always the last edge? (In other words:
     why can we spare ourselves the check that this edge
     is not a proper bridge? What must the last edge rather be?)
\item[e)\hfill]
     How many different (extended) adjacency matrices
     does the graph/molecule in part~b) of this exercise possess?
\end{enumerate}

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

\subsubsection*{Exercise 41 \quad\rm Canonical Code Words}

\begin{enumerate}%\itemsep0pt
\item[a)\hfill]
     Check whether the code word \par
     \centerline{\tt
     \begin{tabular}{*{10}{l@{\tt~}}}
     S & 10-N & 21-O & 31-C & 43-C & 54-O
       & 64=O & 73-C & 87-C & 80-C
     \end{tabular}}
     \parbox[t]{90mm}{is the canonical code word,
     based on a depth-first search
     spanning tree, for this graph/molecule: \\[1ex]
     Use the order $\mbox{\tt S} \prec
     \mbox{\tt N} \prec \mbox{\tt O} \prec \mbox{\tt C}$
     for the atoms and the order
     $\mbox{\tt -} \prec \mbox{\tt =}$ for the bonds!}\hskip20mm
     \lower8ex\hbox{\includegraphics{fpmex-5}}
\item[b)\hfill]
     Check whether the code word \par
     \centerline{\tt
     \begin{tabular}{*{10}{l@{\tt~}}}
     S & 0-N1 & 0-C2 & 1-O3 & 1-C4 & 2-C5
       & 4-C5 & 4-C6 & 6-O7 & 6=O8
     \end{tabular}}
     is the canonical code word, based on a breadth-first search
     spanning tree, for the graph/molecule of part~a)!
     Use the same orders as in part~a)!
\end{enumerate}

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

\subsubsection*{Exercise 42 \quad\rm Canonical Code Words}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What are rightmost path extensions?
     What are maximum source extensions?
\item[b)\hfill]
     Do rightmost path/maximum source extensions
     always yield canonical code words?
\item[c)\hfill]
     \parbox[t]{110mm}{Find the canonical code word, based on a
     depth-first search spanning tree, for cyclin, that is, for
     the molecule:}\hskip16mm
     \lower5.3ex\hbox{\includegraphics{fpmex-6}} \\[-1ex]
     Use the order
     $\mbox{\tt N} \prec \mbox{\tt O} \prec \mbox{\tt C}$
     for the atoms and the order
     $\mbox{\tt -} \prec \mbox{\tt =}$ for the bonds!
\item[d)\hfill]
     Find the canonical code word, based on a breadth-first search
     spanning tree, for cyclin (see part~c)!
     Use the same orders as in part~c!
\end{enumerate}

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

\subsubsection*{Exercise 43 \quad\rm Extendable Vertices}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Which vertices/atoms of cyclin are extendable, based on the
     canonical code word from Exercise~42c),
     by rightmost path extensions?
\item[b)\hfill]
     Which vertices/atoms of cyclin are extendable, based on the
     canonical code word from Exercise~42d),
     by maximum source extensions?
\end{enumerate}

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

\subsubsection*{Additional Exercise \quad\rm Perfect Extensions}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Perfect extensions of item sets are defined
     by a very simple criterion. \\
     Why is the same criterion necessary,
     but not sufficient for graphs? \\
     What criterion is needed instead?
\item[b)\hfill]
     Why do rings cause problems to perfect extensions of graphs? \\
     With what additional conditions can these problems be handled? \\
     Are these conditions necessary?
\item[c)\hfill]
     Why is it easy to cut the search tree branches ``to the right''
     of a perfect extension, but difficult to cut those ``to the left''
     of a perfect extension?
\item[d)\hfill]
     Find the perfect extensions of the fragment {\tt C:C} and of the
     fragment {\tt O-C} in the graph database that consists of the
     following three molecules: \par\vskip2mm
     \centerline{\includegraphics{fpmex-1}\hskip20mm
                 \includegraphics{fpmex-2}\hskip20mm
                 \includegraphics{fpmex-3}}
\end{enumerate}

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

\end{document}
