SN-Evolution-Cut: Mehr über die Geschwindigkeit bei Verwendung von BS(n).
authorFlorian Forster <octo@leeloo.octo.it>
Sat, 26 Feb 2011 14:00:38 +0000 (15:00 +0100)
committerFlorian Forster <octo@leeloo.octo.it>
Sat, 26 Feb 2011 14:00:38 +0000 (15:00 +0100)
diplomarbeit.tex
images/10-ec-from-bs19-fast.tex [new file with mode: 0644]
images/11-ec-from-bs18-fast.tex [new file with mode: 0644]
images/12-ec-from-bs22-fast.tex [new file with mode: 0644]
images/19-ec-from-bs37-fast.tex [new file with mode: 0644]

index 03be0ac..6a41d91 100644 (file)
@@ -1825,6 +1825,15 @@ invertieren.
 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:bs}
 
+Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
+Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
+ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
+als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
+= 6$ gestartet, resultiert das gefundene Schnittmuster in einem
+Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
+benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
+wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+
 \begin{figure}
   \begin{center}
     \input{images/16-ec-from-bs22.tex}
@@ -1837,6 +1846,200 @@ invertieren.
   \label{fig:16-ec-from-bs22}
 \end{figure}
 
+Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
+Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
+gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
+mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
+der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
+$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
+Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
+befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
+Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
+resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
+Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
+können.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+    \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+    \hline
+       &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 &  20 &  21 &  22 &  23 \\
+    \hline
+    9  & 21 &    &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    10 & 20 & 27 &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    11 & 20 & 27 & 32 &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    12 & 20 & 26 & 32 & 39 &    &    &    &    &    &    &    &    &     &     &     &     \\
+    13 & 20 & 26 & 32 & 39 & 45 &    &    &    &    &    &    &    &     &     &     &     \\
+    14 & 20 & 26 & 32 & 39 & 45 & 53 &    &    &    &    &    &    &     &     &     &     \\
+    15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 &    &    &    &    &    &     &     &     &     \\
+    16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 &    &    &    &    &     &     &     &     \\
+    17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 &    &    &    &     &     &     &     \\
+    18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 &    &    &     &     &     &     \\
+    19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 &    &     &     &     &     \\
+    20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 &     &     &     &     \\
+    21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 &     &     &     \\
+    22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 &     &     \\
+    23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 &     \\
+    24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+    \hline
+\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+  \label{tbl:ec-bs-efficiency}
+\end{table}
+
+Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
+mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
+gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
+$m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
+
+In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
+effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
+gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
+3~weniger als \bs{19}.
+
+Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
+beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
+Sortiernetzwerk mit 31~Komparatoren gefunden.
+
+\begin{figure}
+  \centering
+  \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
+  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
+  \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
+  \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
+  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
+  12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+  erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
+  \label{fig:ec-bs-fast_networks}
+\end{figure}
+
+Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
+\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
+das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
+Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von
+\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet.
+Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte
+enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen
+enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
+\hline
+  9 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &   6 &   8 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &   6 &   8 &   9 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
+ 16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
+ 17 &   6 &   8 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
+ 18 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
+ 19 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
+ 20 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
+ 21 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
+ 22 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
+ 23 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
+ 24 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\bs{m}& 6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\end{tabular}
+  \end{center}
+  \caption{Anzahl der Schichten der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+  \label{tbl:ec-bs-speed}
+\end{table}
+
+Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
+schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
+die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
+werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+
+Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
+Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
+führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
+werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
+einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
+= 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
+reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
+noch größer gewählt werden.
+
+Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
+\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
+werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
+Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
+Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
+37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
+und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
+Beispiel für ein solches Netzwerk ist in
+Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+    \begin{tabular}{|r|r|r|}
+    \hline
+    $n$ & Komp. & Schichten \\
+    \hline
+          20 & 95 & 14 \\
+          21 & 94 & 14 \\
+          22 & 93 & 14 \\
+          23 & 93 & 14 \\
+          24 & 93 & 14 \\
+          25 & 96 & 13 \\
+          26 & 96 & 13 \\
+          27 & 96 & 13 \\
+          28 & 96 & 13 \\
+          29 & 95 & 13 \\
+          30 & 96 & 13 \\
+          31 & 95 & 13 \\
+          32 & 96 & 13 \\
+          33 & 93 & 13 \\
+          34 & 94 & 13 \\
+          35 & 93 & 13 \\
+          \rowcolor{green!10}
+          36 & 92 & 13 \\
+         \rowcolor{green!10!white!95!black}
+          37 & 92 & 13 \\
+          38 & 93 & 13 \\
+    \hline
+    \bs{19}  & 98 & 14 \\
+    \oes{19} & 91 & 14 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+    von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
+    wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
+    \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
+    13~Schichten die Effizienz der vorherigen
+    Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
+    Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
+    auf diese Art erzeugt wurde, ist in
+    Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
+  \label{tbl:ec-bs-19}
+\end{table}
+
 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
 wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
 durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
@@ -1921,41 +2124,6 @@ Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
 dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
 Geschwindigkeit dieser Sortiernetzwerke gleich ist.
 
-Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
-unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
-gute Schnittmuster anzugeben.
-
-Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
-Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
-Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
-Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
-ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
-ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
-die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
-Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
-mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
-
-\begin{figure}
-  \centering
-  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
-  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
-  \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
-  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
-  \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
-  der Algorithmus schnelle Sortiernetzwerke ausgeben.}
-  \label{fig:11-12-ec-from-bs22-bs24}
-\end{figure}
-
-Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
-\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
-können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
-effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
-folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
-\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
-der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
-und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
-23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
-
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|}
 \hline
@@ -1987,6 +2155,20 @@ Leitungen  & Komparatoren & Schichten & Komparatoren & Schichten \\
   \label{fig:23-ec-from-bs46}
 \end{figure}
 
+Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
+unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
+Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
+Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
+ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
+ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
+
 Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
 haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
 von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
@@ -1994,42 +2176,6 @@ von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
 $k$~Schnitten gestartet, so ist das beste Ergebnis immer das
 $\operatorname{OET}(n-k)$-Netzwerk. 
 
-\begin{table}
-  \begin{center}
-    \rowcolors{2}{black!5}{}
-    \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
-    \hline
-       &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 &  20 &  21 &  22 &  23 \\
-    \hline
-    9  & 21 &    &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
-    10 & 20 & 27 &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
-    11 & 20 & 27 & 32 &    &    &    &    &    &    &    &    &    &     &     &     &     \\
-    12 & 20 & 26 & 32 & 39 &    &    &    &    &    &    &    &    &     &     &     &     \\
-    13 & 20 & 26 & 32 & 39 & 45 &    &    &    &    &    &    &    &     &     &     &     \\
-    14 & 20 & 26 & 32 & 39 & 45 & 53 &    &    &    &    &    &    &     &     &     &     \\
-    15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 &    &    &    &    &    &     &     &     &     \\
-    16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 &    &    &    &    &     &     &     &     \\
-    17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 &    &    &    &     &     &     &     \\
-    18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 &    &    &     &     &     &     \\
-    19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 &    &     &     &     &     \\
-    20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 &     &     &     &     \\
-    21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 &     &     &     \\
-    22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 &     &     \\
-    23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 &     \\
-    24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
-    \hline
-\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
-    \hline
-    \end{tabular}
-  \end{center}
-  \caption{Anzahl der Komparatoren der Ergebnisse des
-    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
-    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
-    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten
-    repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.}
-  \label{tbl:ec-bs-fast}
-\end{table}
-
 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:oes}
 
@@ -2223,7 +2369,7 @@ wie und warum es jede beliebige Eingabe sortiert.
     Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
     Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
     Ausgabenetzwerks.}
-  \label{tbl:ec-bs-fast}
+  \label{tbl:ec-ps-fast}
 \end{table}
 
 Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
diff --git a/images/10-ec-from-bs19-fast.tex b/images/10-ec-from-bs19-fast.tex
new file mode 100644 (file)
index 0000000..2855499
--- /dev/null
@@ -0,0 +1,136 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.58,0.00) {};
+\node[vertex] (v1) at (0.58,1.87) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.76,0.47) {};
+\node[vertex] (v3) at (0.76,3.73) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.93,0.93) {};
+\node[vertex] (v5) at (0.93,1.40) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.58,2.33) {};
+\node[vertex] (v7) at (0.58,3.27) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.93,2.80) {};
+\node[vertex] (v9) at (0.93,4.20) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (1.52,0.00) {};
+\node[vertex] (v11) at (1.52,0.93) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (1.69,0.47) {};
+\node[vertex] (v13) at (1.69,2.80) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.52,1.40) {};
+\node[vertex] (v15) at (1.52,1.87) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.52,3.73) {};
+\node[vertex] (v17) at (1.52,4.20) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (2.27,0.47) {};
+\node[vertex] (v19) at (2.27,2.33) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (2.45,0.93) {};
+\node[vertex] (v21) at (2.45,1.40) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (2.27,2.80) {};
+\node[vertex] (v23) at (2.27,3.73) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.45,3.27) {};
+\node[vertex] (v25) at (2.45,4.20) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (3.03,0.00) {};
+\node[vertex] (v27) at (3.03,0.47) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (3.03,1.87) {};
+\node[vertex] (v29) at (3.03,4.20) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (3.21,2.33) {};
+\node[vertex] (v31) at (3.21,3.73) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (3.38,2.80) {};
+\node[vertex] (v33) at (3.38,3.27) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (3.97,2.33) {};
+\node[vertex] (v35) at (3.97,2.80) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (3.97,3.27) {};
+\node[vertex] (v37) at (3.97,3.73) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (4.55,0.47) {};
+\node[vertex] (v39) at (4.55,3.73) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (4.72,0.93) {};
+\node[vertex] (v41) at (4.72,3.27) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (4.90,1.40) {};
+\node[vertex] (v43) at (4.90,2.80) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (5.07,1.87) {};
+\node[vertex] (v45) at (5.07,2.33) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (5.66,0.47) {};
+\node[vertex] (v47) at (5.66,1.40) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (5.83,0.93) {};
+\node[vertex] (v49) at (5.83,1.87) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (5.66,2.33) {};
+\node[vertex] (v51) at (5.66,3.27) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (5.83,2.80) {};
+\node[vertex] (v53) at (5.83,3.73) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (6.42,0.47) {};
+\node[vertex] (v55) at (6.42,0.93) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (6.42,1.40) {};
+\node[vertex] (v57) at (6.42,1.87) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (6.42,2.33) {};
+\node[vertex] (v59) at (6.42,2.80) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (6.42,3.27) {};
+\node[vertex] (v61) at (6.42,3.73) {};
+\path[comp] (v60) -- (v61);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.47) -- (7.00,0.47);
+\path[edge] (0,0.93) -- (7.00,0.93);
+\path[edge] (0,1.40) -- (7.00,1.40);
+\path[edge] (0,1.87) -- (7.00,1.87);
+\path[edge] (0,2.33) -- (7.00,2.33);
+\path[edge] (0,2.80) -- (7.00,2.80);
+\path[edge] (0,3.27) -- (7.00,3.27);
+\path[edge] (0,3.73) -- (7.00,3.73);
+\path[edge] (0,4.20) -- (7.00,4.20);
+\end{tikzpicture}
diff --git a/images/11-ec-from-bs18-fast.tex b/images/11-ec-from-bs18-fast.tex
new file mode 100644 (file)
index 0000000..4ba1cd5
--- /dev/null
@@ -0,0 +1,161 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.55,0.00) {};
+\node[vertex] (v1) at (0.55,0.44) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.55,0.88) {};
+\node[vertex] (v3) at (0.55,4.41) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.72,1.32) {};
+\node[vertex] (v5) at (0.72,2.20) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.72,2.65) {};
+\node[vertex] (v7) at (0.72,3.09) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.72,3.53) {};
+\node[vertex] (v9) at (0.72,3.97) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (1.27,0.88) {};
+\node[vertex] (v11) at (1.27,3.53) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (1.43,1.32) {};
+\node[vertex] (v13) at (1.43,1.76) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.27,3.97) {};
+\node[vertex] (v15) at (1.27,4.41) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.98,0.44) {};
+\node[vertex] (v17) at (1.98,1.32) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (2.15,0.88) {};
+\node[vertex] (v19) at (2.15,2.65) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (1.98,1.76) {};
+\node[vertex] (v21) at (1.98,2.20) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (1.98,3.09) {};
+\node[vertex] (v23) at (1.98,4.41) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.15,3.53) {};
+\node[vertex] (v25) at (2.15,3.97) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (2.70,0.00) {};
+\node[vertex] (v27) at (2.70,1.76) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (2.87,1.32) {};
+\node[vertex] (v29) at (2.87,2.20) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (2.70,2.65) {};
+\node[vertex] (v31) at (2.70,3.97) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (2.87,3.09) {};
+\node[vertex] (v33) at (2.87,3.53) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (3.42,0.00) {};
+\node[vertex] (v35) at (3.42,0.44) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (3.42,1.32) {};
+\node[vertex] (v37) at (3.42,1.76) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (3.42,2.20) {};
+\node[vertex] (v39) at (3.42,4.41) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (3.58,2.65) {};
+\node[vertex] (v41) at (3.58,3.09) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (3.58,3.53) {};
+\node[vertex] (v43) at (3.58,3.97) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (4.13,0.00) {};
+\node[vertex] (v45) at (4.13,2.65) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (4.30,0.44) {};
+\node[vertex] (v47) at (4.30,0.88) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (4.30,1.32) {};
+\node[vertex] (v49) at (4.30,3.53) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (4.46,1.76) {};
+\node[vertex] (v51) at (4.46,3.09) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (5.02,0.00) {};
+\node[vertex] (v53) at (5.02,0.44) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (5.02,0.88) {};
+\node[vertex] (v55) at (5.02,3.97) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (5.18,2.20) {};
+\node[vertex] (v57) at (5.18,2.65) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (5.73,0.88) {};
+\node[vertex] (v59) at (5.73,1.76) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (5.90,1.32) {};
+\node[vertex] (v61) at (5.90,2.20) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (5.73,2.65) {};
+\node[vertex] (v63) at (5.73,3.53) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (5.90,3.09) {};
+\node[vertex] (v65) at (5.90,3.97) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (6.45,0.88) {};
+\node[vertex] (v67) at (6.45,1.32) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (6.45,1.76) {};
+\node[vertex] (v69) at (6.45,2.20) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (6.45,2.65) {};
+\node[vertex] (v71) at (6.45,3.09) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (6.45,3.53) {};
+\node[vertex] (v73) at (6.45,3.97) {};
+\path[comp] (v72) -- (v73);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.44) -- (7.00,0.44);
+\path[edge] (0,0.88) -- (7.00,0.88);
+\path[edge] (0,1.32) -- (7.00,1.32);
+\path[edge] (0,1.76) -- (7.00,1.76);
+\path[edge] (0,2.20) -- (7.00,2.20);
+\path[edge] (0,2.65) -- (7.00,2.65);
+\path[edge] (0,3.09) -- (7.00,3.09);
+\path[edge] (0,3.53) -- (7.00,3.53);
+\path[edge] (0,3.97) -- (7.00,3.97);
+\path[edge] (0,4.41) -- (7.00,4.41);
+\end{tikzpicture}
diff --git a/images/12-ec-from-bs22-fast.tex b/images/12-ec-from-bs22-fast.tex
new file mode 100644 (file)
index 0000000..6aca4dd
--- /dev/null
@@ -0,0 +1,182 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.48,0.00) {};
+\node[vertex] (v1) at (0.48,2.70) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.63,0.39) {};
+\node[vertex] (v3) at (0.63,3.09) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.77,0.77) {};
+\node[vertex] (v5) at (0.77,2.32) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.92,1.16) {};
+\node[vertex] (v7) at (0.92,4.25) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (1.06,1.54) {};
+\node[vertex] (v9) at (1.06,3.86) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (1.21,1.93) {};
+\node[vertex] (v11) at (1.21,3.48) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (1.69,0.00) {};
+\node[vertex] (v13) at (1.69,0.77) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.69,1.16) {};
+\node[vertex] (v15) at (1.69,1.54) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.69,2.32) {};
+\node[vertex] (v17) at (1.69,2.70) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (1.69,3.86) {};
+\node[vertex] (v19) at (1.69,4.25) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (2.17,0.00) {};
+\node[vertex] (v21) at (2.17,0.39) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (2.17,0.77) {};
+\node[vertex] (v23) at (2.17,2.32) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.32,1.16) {};
+\node[vertex] (v25) at (2.32,1.93) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (2.46,1.54) {};
+\node[vertex] (v27) at (2.46,3.86) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (2.17,2.70) {};
+\node[vertex] (v29) at (2.17,3.09) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (2.17,3.48) {};
+\node[vertex] (v31) at (2.17,4.25) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (2.94,0.39) {};
+\node[vertex] (v33) at (2.94,2.32) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (3.09,0.77) {};
+\node[vertex] (v35) at (3.09,2.70) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (3.23,1.54) {};
+\node[vertex] (v37) at (3.23,3.48) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (3.38,1.93) {};
+\node[vertex] (v39) at (3.38,3.86) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (2.94,3.09) {};
+\node[vertex] (v41) at (2.94,4.25) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (3.86,0.39) {};
+\node[vertex] (v43) at (3.86,0.77) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (3.86,1.54) {};
+\node[vertex] (v45) at (3.86,1.93) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (3.86,2.32) {};
+\node[vertex] (v47) at (3.86,2.70) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (3.86,3.48) {};
+\node[vertex] (v49) at (3.86,3.86) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (4.34,0.00) {};
+\node[vertex] (v51) at (4.34,1.93) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (4.49,0.39) {};
+\node[vertex] (v53) at (4.49,1.54) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (4.63,0.77) {};
+\node[vertex] (v55) at (4.63,1.16) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (4.34,2.32) {};
+\node[vertex] (v57) at (4.34,3.48) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (5.12,0.00) {};
+\node[vertex] (v59) at (5.12,0.77) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (5.12,1.16) {};
+\node[vertex] (v61) at (5.12,3.86) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (5.26,1.54) {};
+\node[vertex] (v63) at (5.26,3.09) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (5.41,1.93) {};
+\node[vertex] (v65) at (5.41,2.70) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (5.89,0.39) {};
+\node[vertex] (v67) at (5.89,0.77) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (5.89,1.16) {};
+\node[vertex] (v69) at (5.89,1.93) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (6.03,1.54) {};
+\node[vertex] (v71) at (6.03,2.32) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (5.89,2.70) {};
+\node[vertex] (v73) at (5.89,3.86) {};
+\path[comp] (v72) -- (v73);
+
+\node[vertex] (v74) at (6.03,3.09) {};
+\node[vertex] (v75) at (6.03,3.48) {};
+\path[comp] (v74) -- (v75);
+
+\node[vertex] (v76) at (6.52,1.16) {};
+\node[vertex] (v77) at (6.52,1.54) {};
+\path[comp] (v76) -- (v77);
+
+\node[vertex] (v78) at (6.52,1.93) {};
+\node[vertex] (v79) at (6.52,2.32) {};
+\path[comp] (v78) -- (v79);
+
+\node[vertex] (v80) at (6.52,2.70) {};
+\node[vertex] (v81) at (6.52,3.09) {};
+\path[comp] (v80) -- (v81);
+
+\node[vertex] (v82) at (6.52,3.48) {};
+\node[vertex] (v83) at (6.52,3.86) {};
+\path[comp] (v82) -- (v83);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.39) -- (7.00,0.39);
+\path[edge] (0,0.77) -- (7.00,0.77);
+\path[edge] (0,1.16) -- (7.00,1.16);
+\path[edge] (0,1.54) -- (7.00,1.54);
+\path[edge] (0,1.93) -- (7.00,1.93);
+\path[edge] (0,2.32) -- (7.00,2.32);
+\path[edge] (0,2.70) -- (7.00,2.70);
+\path[edge] (0,3.09) -- (7.00,3.09);
+\path[edge] (0,3.48) -- (7.00,3.48);
+\path[edge] (0,3.86) -- (7.00,3.86);
+\path[edge] (0,4.25) -- (7.00,4.25);
+\end{tikzpicture}
diff --git a/images/19-ec-from-bs37-fast.tex b/images/19-ec-from-bs37-fast.tex
new file mode 100644 (file)
index 0000000..85896e3
--- /dev/null
@@ -0,0 +1,389 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.30,0.00) {};
+\node[vertex] (v1) at (0.30,3.12) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.39,0.48) {};
+\node[vertex] (v3) at (0.39,2.64) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.48,0.72) {};
+\node[vertex] (v5) at (0.48,0.96) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.48,1.20) {};
+\node[vertex] (v7) at (0.48,3.61) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.57,1.44) {};
+\node[vertex] (v9) at (0.57,4.09) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (0.66,1.68) {};
+\node[vertex] (v11) at (0.66,3.85) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (0.75,1.92) {};
+\node[vertex] (v13) at (0.75,2.16) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (0.75,2.40) {};
+\node[vertex] (v15) at (0.75,2.88) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (0.30,3.36) {};
+\node[vertex] (v17) at (0.30,4.33) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (1.05,0.24) {};
+\node[vertex] (v19) at (1.05,0.96) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (1.14,0.48) {};
+\node[vertex] (v21) at (1.14,2.40) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (1.05,1.20) {};
+\node[vertex] (v23) at (1.05,1.68) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (1.05,1.92) {};
+\node[vertex] (v25) at (1.05,3.36) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (1.23,2.16) {};
+\node[vertex] (v27) at (1.23,4.33) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (1.14,2.64) {};
+\node[vertex] (v29) at (1.14,2.88) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (1.05,3.61) {};
+\node[vertex] (v31) at (1.05,3.85) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (1.53,0.24) {};
+\node[vertex] (v33) at (1.53,0.72) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (1.53,0.96) {};
+\node[vertex] (v35) at (1.53,3.12) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (1.62,1.20) {};
+\node[vertex] (v37) at (1.62,1.44) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (1.62,1.68) {};
+\node[vertex] (v39) at (1.62,3.61) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (1.71,2.16) {};
+\node[vertex] (v41) at (1.71,3.36) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (1.80,2.40) {};
+\node[vertex] (v43) at (1.80,2.64) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (1.53,3.85) {};
+\node[vertex] (v45) at (1.53,4.09) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (2.10,0.00) {};
+\node[vertex] (v47) at (2.10,0.72) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (2.19,0.24) {};
+\node[vertex] (v49) at (2.19,0.96) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (2.10,1.20) {};
+\node[vertex] (v51) at (2.10,1.92) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (2.19,1.44) {};
+\node[vertex] (v53) at (2.19,3.61) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (2.28,1.68) {};
+\node[vertex] (v55) at (2.28,3.85) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (2.10,2.40) {};
+\node[vertex] (v57) at (2.10,3.12) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (2.10,4.09) {};
+\node[vertex] (v59) at (2.10,4.33) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (2.58,0.00) {};
+\node[vertex] (v61) at (2.58,0.24) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (2.58,0.72) {};
+\node[vertex] (v63) at (2.58,0.96) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (2.58,1.44) {};
+\node[vertex] (v65) at (2.58,1.68) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (2.58,3.61) {};
+\node[vertex] (v67) at (2.58,3.85) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (2.88,0.00) {};
+\node[vertex] (v69) at (2.88,2.40) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (2.97,0.24) {};
+\node[vertex] (v71) at (2.97,0.48) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (2.97,0.72) {};
+\node[vertex] (v73) at (2.97,2.88) {};
+\path[comp] (v72) -- (v73);
+
+\node[vertex] (v74) at (3.06,0.96) {};
+\node[vertex] (v75) at (3.06,2.64) {};
+\path[comp] (v74) -- (v75);
+
+\node[vertex] (v76) at (3.15,1.44) {};
+\node[vertex] (v77) at (3.15,4.09) {};
+\path[comp] (v76) -- (v77);
+
+\node[vertex] (v78) at (3.24,1.68) {};
+\node[vertex] (v79) at (3.24,3.36) {};
+\path[comp] (v78) -- (v79);
+
+\node[vertex] (v80) at (3.33,1.92) {};
+\node[vertex] (v81) at (3.33,3.85) {};
+\path[comp] (v80) -- (v81);
+
+\node[vertex] (v82) at (3.42,2.16) {};
+\node[vertex] (v83) at (3.42,3.61) {};
+\path[comp] (v82) -- (v83);
+
+\node[vertex] (v84) at (3.73,0.00) {};
+\node[vertex] (v85) at (3.73,0.24) {};
+\path[comp] (v84) -- (v85);
+
+\node[vertex] (v86) at (3.73,0.48) {};
+\node[vertex] (v87) at (3.73,0.96) {};
+\path[comp] (v86) -- (v87);
+
+\node[vertex] (v88) at (3.82,0.72) {};
+\node[vertex] (v89) at (3.82,2.40) {};
+\path[comp] (v88) -- (v89);
+
+\node[vertex] (v90) at (3.73,1.44) {};
+\node[vertex] (v91) at (3.73,2.16) {};
+\path[comp] (v90) -- (v91);
+
+\node[vertex] (v92) at (3.91,1.68) {};
+\node[vertex] (v93) at (3.91,1.92) {};
+\path[comp] (v92) -- (v93);
+
+\node[vertex] (v94) at (3.73,2.88) {};
+\node[vertex] (v95) at (3.73,3.12) {};
+\path[comp] (v94) -- (v95);
+
+\node[vertex] (v96) at (3.73,3.36) {};
+\node[vertex] (v97) at (3.73,3.85) {};
+\path[comp] (v96) -- (v97);
+
+\node[vertex] (v98) at (3.82,3.61) {};
+\node[vertex] (v99) at (3.82,4.09) {};
+\path[comp] (v98) -- (v99);
+
+\node[vertex] (v100) at (4.21,0.48) {};
+\node[vertex] (v101) at (4.21,0.72) {};
+\path[comp] (v100) -- (v101);
+
+\node[vertex] (v102) at (4.21,0.96) {};
+\node[vertex] (v103) at (4.21,2.40) {};
+\path[comp] (v102) -- (v103);
+
+\node[vertex] (v104) at (4.30,1.44) {};
+\node[vertex] (v105) at (4.30,1.68) {};
+\path[comp] (v104) -- (v105);
+
+\node[vertex] (v106) at (4.30,1.92) {};
+\node[vertex] (v107) at (4.30,2.16) {};
+\path[comp] (v106) -- (v107);
+
+\node[vertex] (v108) at (4.21,2.64) {};
+\node[vertex] (v109) at (4.21,2.88) {};
+\path[comp] (v108) -- (v109);
+
+\node[vertex] (v110) at (4.21,3.36) {};
+\node[vertex] (v111) at (4.21,3.61) {};
+\path[comp] (v110) -- (v111);
+
+\node[vertex] (v112) at (4.21,3.85) {};
+\node[vertex] (v113) at (4.21,4.09) {};
+\path[comp] (v112) -- (v113);
+
+\node[vertex] (v114) at (4.60,0.00) {};
+\node[vertex] (v115) at (4.60,2.16) {};
+\path[comp] (v114) -- (v115);
+
+\node[vertex] (v116) at (4.69,0.24) {};
+\node[vertex] (v117) at (4.69,1.92) {};
+\path[comp] (v116) -- (v117);
+
+\node[vertex] (v118) at (4.78,0.48) {};
+\node[vertex] (v119) at (4.78,1.68) {};
+\path[comp] (v118) -- (v119);
+
+\node[vertex] (v120) at (4.87,0.72) {};
+\node[vertex] (v121) at (4.87,1.44) {};
+\path[comp] (v120) -- (v121);
+
+\node[vertex] (v122) at (4.96,0.96) {};
+\node[vertex] (v123) at (4.96,1.20) {};
+\path[comp] (v122) -- (v123);
+
+\node[vertex] (v124) at (4.60,2.40) {};
+\node[vertex] (v125) at (4.60,3.85) {};
+\path[comp] (v124) -- (v125);
+
+\node[vertex] (v126) at (4.69,2.64) {};
+\node[vertex] (v127) at (4.69,3.61) {};
+\path[comp] (v126) -- (v127);
+
+\node[vertex] (v128) at (4.78,2.88) {};
+\node[vertex] (v129) at (4.78,3.36) {};
+\path[comp] (v128) -- (v129);
+
+\node[vertex] (v130) at (5.26,0.00) {};
+\node[vertex] (v131) at (5.26,0.96) {};
+\path[comp] (v130) -- (v131);
+
+\node[vertex] (v132) at (5.35,0.24) {};
+\node[vertex] (v133) at (5.35,0.72) {};
+\path[comp] (v132) -- (v133);
+
+\node[vertex] (v134) at (5.26,1.20) {};
+\node[vertex] (v135) at (5.26,4.09) {};
+\path[comp] (v134) -- (v135);
+
+\node[vertex] (v136) at (5.35,1.44) {};
+\node[vertex] (v137) at (5.35,4.33) {};
+\path[comp] (v136) -- (v137);
+
+\node[vertex] (v138) at (5.44,1.68) {};
+\node[vertex] (v139) at (5.44,2.64) {};
+\path[comp] (v138) -- (v139);
+
+\node[vertex] (v140) at (5.53,1.92) {};
+\node[vertex] (v141) at (5.53,2.40) {};
+\path[comp] (v140) -- (v141);
+
+\node[vertex] (v142) at (5.62,2.16) {};
+\node[vertex] (v143) at (5.62,3.12) {};
+\path[comp] (v142) -- (v143);
+
+\node[vertex] (v144) at (5.92,0.48) {};
+\node[vertex] (v145) at (5.92,0.96) {};
+\path[comp] (v144) -- (v145);
+
+\node[vertex] (v146) at (5.92,1.20) {};
+\node[vertex] (v147) at (5.92,2.16) {};
+\path[comp] (v146) -- (v147);
+
+\node[vertex] (v148) at (6.01,1.44) {};
+\node[vertex] (v149) at (6.01,2.88) {};
+\path[comp] (v148) -- (v149);
+
+\node[vertex] (v150) at (5.92,3.12) {};
+\node[vertex] (v151) at (5.92,4.09) {};
+\path[comp] (v150) -- (v151);
+
+\node[vertex] (v152) at (6.01,3.36) {};
+\node[vertex] (v153) at (6.01,4.33) {};
+\path[comp] (v152) -- (v153);
+
+\node[vertex] (v154) at (6.31,0.24) {};
+\node[vertex] (v155) at (6.31,0.48) {};
+\path[comp] (v154) -- (v155);
+
+\node[vertex] (v156) at (6.31,0.72) {};
+\node[vertex] (v157) at (6.31,0.96) {};
+\path[comp] (v156) -- (v157);
+
+\node[vertex] (v158) at (6.31,1.20) {};
+\node[vertex] (v159) at (6.31,1.68) {};
+\path[comp] (v158) -- (v159);
+
+\node[vertex] (v160) at (6.40,1.44) {};
+\node[vertex] (v161) at (6.40,1.92) {};
+\path[comp] (v160) -- (v161);
+
+\node[vertex] (v162) at (6.31,2.16) {};
+\node[vertex] (v163) at (6.31,2.64) {};
+\path[comp] (v162) -- (v163);
+
+\node[vertex] (v164) at (6.40,2.40) {};
+\node[vertex] (v165) at (6.40,2.88) {};
+\path[comp] (v164) -- (v165);
+
+\node[vertex] (v166) at (6.31,3.12) {};
+\node[vertex] (v167) at (6.31,3.61) {};
+\path[comp] (v166) -- (v167);
+
+\node[vertex] (v168) at (6.40,3.36) {};
+\node[vertex] (v169) at (6.40,3.85) {};
+\path[comp] (v168) -- (v169);
+
+\node[vertex] (v170) at (6.31,4.09) {};
+\node[vertex] (v171) at (6.31,4.33) {};
+\path[comp] (v170) -- (v171);
+
+\node[vertex] (v172) at (6.70,1.20) {};
+\node[vertex] (v173) at (6.70,1.44) {};
+\path[comp] (v172) -- (v173);
+
+\node[vertex] (v174) at (6.70,1.68) {};
+\node[vertex] (v175) at (6.70,1.92) {};
+\path[comp] (v174) -- (v175);
+
+\node[vertex] (v176) at (6.70,2.16) {};
+\node[vertex] (v177) at (6.70,2.40) {};
+\path[comp] (v176) -- (v177);
+
+\node[vertex] (v178) at (6.70,2.64) {};
+\node[vertex] (v179) at (6.70,2.88) {};
+\path[comp] (v178) -- (v179);
+
+\node[vertex] (v180) at (6.70,3.12) {};
+\node[vertex] (v181) at (6.70,3.36) {};
+\path[comp] (v180) -- (v181);
+
+\node[vertex] (v182) at (6.70,3.61) {};
+\node[vertex] (v183) at (6.70,3.85) {};
+\path[comp] (v182) -- (v183);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.24) -- (7.00,0.24);
+\path[edge] (0,0.48) -- (7.00,0.48);
+\path[edge] (0,0.72) -- (7.00,0.72);
+\path[edge] (0,0.96) -- (7.00,0.96);
+\path[edge] (0,1.20) -- (7.00,1.20);
+\path[edge] (0,1.44) -- (7.00,1.44);
+\path[edge] (0,1.68) -- (7.00,1.68);
+\path[edge] (0,1.92) -- (7.00,1.92);
+\path[edge] (0,2.16) -- (7.00,2.16);
+\path[edge] (0,2.40) -- (7.00,2.40);
+\path[edge] (0,2.64) -- (7.00,2.64);
+\path[edge] (0,2.88) -- (7.00,2.88);
+\path[edge] (0,3.12) -- (7.00,3.12);
+\path[edge] (0,3.36) -- (7.00,3.36);
+\path[edge] (0,3.61) -- (7.00,3.61);
+\path[edge] (0,3.85) -- (7.00,3.85);
+\path[edge] (0,4.09) -- (7.00,4.09);
+\path[edge] (0,4.33) -- (7.00,4.33);
+\end{tikzpicture}