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

\begin{document}

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

\noindent
{\bf Data Mining 2: Finden h"aufiger Muster} \hfill Sommer 2018 \\
Christian Borgelt \hfill ab 16.07.2018

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

\vskip3ex
\centerline{\bf 11.~"Ubungsblatt}

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

\subsubsection*{Aufgabe 31 \quad\rm Suche nach h"aufigen Teilgraphen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Warum schlie\3en wir bei der Zuweisung eindeutiger Elterngraphen
     das Entfernen echter Br"ucken aus?
\item[b)\hfill]
     \parbox[t]{90mm}{Wie viele verschiedene spannende B"aume besitzt
     der rechts gezeigte Graph / das rechts gezeigte Molek"ul?
     Begr"unden Sie Ihre Antwort!}\hskip16mm
     \lower6.8ex\hbox{\includegraphics{fpmex-4}}
\item[c)\hfill]
     Warum ist die Zahl der m"oglichen Kodew"orter i.a.\ (wesentlich)
     gr"o\3er als die Zahl der spannenden B"aume?
     Welche zus"atzlichen Wahlm"oglichkeiten bestehen?
\item[d)\hfill]
     Warum stellt ein Kodierungsschema, das spannende B"aume benutzt
     und in dem alle ringschlie\3enden Kanten nach den Baumkanten
     aufgelistet werden, sicher, da\3 man immer die letzte Kante
     entfernen kann? (Mit anderen Worten: Warum kann man die Pr"ufung
     einsparen, ob diese Kante eine echte Br"ucke ist? Was mu\3 die
     letzte Kante vielmehr sein?)
\item[e)\hfill]
     Wie viele verschiedene (erweiterte) Adjazenzmatrizen besitzt
     der Graph / das Molek"ul aus Teil~b) dieser Aufgabe?
\end{enumerate}

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

\subsubsection*{Aufgabe 32 \quad\rm Kanonische Kodew"orter}

\begin{enumerate}%\itemsep0pt
\item[a)\hfill]
     Pr"ufen Sie, ob das Kodewort \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}{das kanonische Kodewort bzgl.\ eines durch
     Tiefensuche konstruierten spannenden Baumes f"ur diesen
     Graphen / dieses Molek"ul ist: \\[1ex]
     Verwenden Sie die Ordnung $\mbox{\tt S} \prec
     \mbox{\tt N} \prec \mbox{\tt O} \prec \mbox{\tt C}$
     f"ur die Atome und die Ordnung
     $\mbox{\tt -} \prec \mbox{\tt =}$ f"ur die Bindungen!}\hskip20mm
     \lower8ex\hbox{\includegraphics{fpmex-5}}
\item[b)\hfill]
     Pr"ufen Sie, ob das Kodewort \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}}
     das kanonische Kodewort bzgl.\ eines durch Breitensuche
     konstruierten spannenden Baumes f"ur den Graphen / das Molek"ul
     aus Teil~a) ist! Benutzen Sie die gleichen Ordnungen
     wie in Teil~a)!
\end{enumerate}

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

\subsubsection*{Aufgabe 33 \quad\rm Kanonische Kodew"orter}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was sind {\em rightmost path extensions\/}?
     Was sind {\em maximum source extensions\/}?
\item[b)\hfill]
     Liefern {\em rightmost path/maximum source extensions\/}
     stets kanonische Kodew"orter?
\item[c)\hfill]
     \parbox[t]{110mm}{Finden Sie das kanonische Kodewort bzgl.\
     eines durch Tiefensuche erzeugten spannenden Baumes f"ur
     Cyclin, d.h.\ f"ur:}\hskip16mm
     \lower5.3ex\hbox{\includegraphics{fpmex-6}} \\[-1ex]
     Attributordnungen:
     $\mbox{\tt N} \prec \mbox{\tt O} \prec \mbox{\tt C}$
     f"ur die Atome und
     $\mbox{\tt -} \prec \mbox{\tt =}$ f"ur die Bindungen.
\item[d)\hfill]
     Finden Sie das kanonische Kodewort bzgl.\
     eines durch Breitensuche erzeugten spannenden Baumes
     f"ur Cyclin (siehe Teil~c)! (Ordnungen wie in Teil~c.)
\end{enumerate}

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

\subsubsection*{Aufgabe 34 \quad\rm Erweiterbare Knoten}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Welche Knoten/Atome von Cyclin sind, auf der Grundlage
     des Kodewortes aus Aufgabe~33c), durch
     {\em rightmost path extensions\/} erweiterbar?
\item[b)\hfill]
     Welche Knoten/Atome von Cyclin sind, auf der Grundlage
     des Kodewortes aus Aufgabe~33d), durch
     {\em maximum source extensions\/} erweiterbar?
\end{enumerate}

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

\subsubsection*{Zusatzaufgabe \quad\rm Perfekte Erweiterungen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Perfekte Erweiterungen von Itemmengen werden "uber ein einfaches
     Kriterium definiert.
     Warum ist das gleiche Kriterium notwendig, aber nicht hinreichend
     f"ur Graphen?
     Welches Kriterium wird stattdessen gebraucht?
\item[b)\hfill]
     Warum verursachen Ringe Probleme f"ur perfekte Erweiterungen
     von Graphen? \\
     Durch welche zus"atzlichen Bedingungen werden diese Probleme
     behandelt? \\
     Sind diese Bedingungen notwendig?
\item[c)\hfill]
     Warum ist es leicht, Suchbaumzweige ``rechts von'' einer perfekten
     Erweiterung, aber schwierig, Zweige ``links von'' einer perfekten
     Erweiterung zu stutzen?
\item[d)\hfill]
     Finden Sie die perfekten Erweiterungen des Fragmentes {\tt C:C}
     und des Fragmentes {\tt O-C} in der Graphdatenbank, die aus den
     folgenden drei Molek"ulen besteht: \par\vskip2mm
     \centerline{\includegraphics{fpmex-1}\hskip20mm
                 \includegraphics{fpmex-2}\hskip20mm
                 \includegraphics{fpmex-3}}
\end{enumerate}

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

\end{document}
