SN-Evolution-Cut: Mehr zu den Versuchen mit OES(n).
authorFlorian Forster <octo@leeloo.octo.it>
Sat, 26 Feb 2011 17:57:38 +0000 (18:57 +0100)
committerFlorian Forster <octo@leeloo.octo.it>
Sat, 26 Feb 2011 17:57:38 +0000 (18:57 +0100)
diplomarbeit.tex
images/11-ec-from-oes17-fast.tex [new file with mode: 0644]
images/12-ec-from-oes18-fast.tex [new file with mode: 0644]

index 3caa170..0358d88 100644 (file)
@@ -2165,6 +2165,110 @@ $\operatorname{OET}(n-k)$-Netzwerk.
 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:oes}
 
+Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
+genauso effizient und schnell wie das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
+Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
+\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
+tabellarisch.
+
+\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 &  19 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &  19 &  26 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &  19 &  26 &  31 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &  19 &  26 &  31 &  37 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &  19 &  26 &  31 &  37 &  41 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &  19 &  26 &  31 &  37 &  41 &  48 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &     &     &     &     &     &     &     &     &     \\
+ 16 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &  59 &     &     &     &     &     &     &     &     \\
+ 17 &  19 &  26 &  31 &  38 &  41 &  48 &  53 &  59 &  63 &     &     &     &     &     &     &     \\
+ 18 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &     &     &     &     &     &     \\
+ 19 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &     &     &     &     &     \\
+ 20 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &     &     &     &     \\
+ 21 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 &     &     &     \\
+ 22 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 &     &     \\
+ 23 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 &     \\
+ 24 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 & 122 \\
+\hline
+\end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+    \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+    Ausgabenetzwerks.}
+  \label{tbl:ec-oes-efficiency}
+\end{table}
+
+\begin{figure}
+  \centering
+  \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
+  \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
+  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
+  11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+  erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
+  sind.}
+  \label{fig:ec-oes-fast_networks}
+\end{figure}
+
+Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
+schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
+$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
+Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
+war allerdings in allen beobachteten Fällen nur dann möglich, wenn
+zusätzliche Komparatoren in Kauf genommen wurden. In den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
+Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
+beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
+Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+
+\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 &   9 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
+ 18 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
+ 19 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
+ 20 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
+ 21 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
+ 22 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
+ 23 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
+ 24 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\oes{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{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+    Ausgabenetzwerks.}
+  \label{tbl:ec-oes-speed}
+\end{table}
+
 In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
 viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
 $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
@@ -2353,7 +2457,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-ps-fast}
+  \label{tbl:ec-ps-speed}
 \end{table}
 
 Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
diff --git a/images/11-ec-from-oes17-fast.tex b/images/11-ec-from-oes17-fast.tex
new file mode 100644 (file)
index 0000000..c46afe8
--- /dev/null
@@ -0,0 +1,165 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.56,0.45) {};
+\node[vertex] (v1) at (0.56,1.81) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.73,0.90) {};
+\node[vertex] (v3) at (0.73,1.35) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.56,2.26) {};
+\node[vertex] (v5) at (0.56,3.61) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.73,2.71) {};
+\node[vertex] (v7) at (0.73,3.16) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.56,4.06) {};
+\node[vertex] (v9) at (0.56,4.52) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (1.30,0.00) {};
+\node[vertex] (v11) at (1.30,1.35) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (1.30,2.26) {};
+\node[vertex] (v13) at (1.30,2.71) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.30,3.16) {};
+\node[vertex] (v15) at (1.30,3.61) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.86,0.00) {};
+\node[vertex] (v17) at (1.86,0.90) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (1.86,1.35) {};
+\node[vertex] (v19) at (1.86,1.81) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (1.86,2.26) {};
+\node[vertex] (v21) at (1.86,4.52) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (2.03,2.71) {};
+\node[vertex] (v23) at (2.03,3.16) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.03,3.61) {};
+\node[vertex] (v25) at (2.03,4.06) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (2.60,0.00) {};
+\node[vertex] (v27) at (2.60,1.35) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (2.77,0.45) {};
+\node[vertex] (v29) at (2.77,0.90) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (2.60,2.71) {};
+\node[vertex] (v31) at (2.60,3.61) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (2.77,3.16) {};
+\node[vertex] (v33) at (2.77,4.52) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (3.33,0.00) {};
+\node[vertex] (v35) at (3.33,0.45) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (3.33,0.90) {};
+\node[vertex] (v37) at (3.33,1.35) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (3.33,2.26) {};
+\node[vertex] (v39) at (3.33,2.71) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (3.33,3.16) {};
+\node[vertex] (v41) at (3.33,3.61) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (3.33,4.06) {};
+\node[vertex] (v43) at (3.33,4.52) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (3.90,0.00) {};
+\node[vertex] (v45) at (3.90,2.26) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (4.06,0.45) {};
+\node[vertex] (v47) at (4.06,2.71) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (4.23,0.90) {};
+\node[vertex] (v49) at (4.23,3.16) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (4.40,1.35) {};
+\node[vertex] (v51) at (4.40,3.61) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (4.57,1.81) {};
+\node[vertex] (v53) at (4.57,4.06) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (5.14,1.81) {};
+\node[vertex] (v55) at (5.14,2.26) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (5.14,2.71) {};
+\node[vertex] (v57) at (5.14,4.52) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (5.70,0.90) {};
+\node[vertex] (v59) at (5.70,1.81) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (5.87,1.35) {};
+\node[vertex] (v61) at (5.87,2.71) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (5.70,2.26) {};
+\node[vertex] (v63) at (5.70,3.16) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (5.70,3.61) {};
+\node[vertex] (v65) at (5.70,4.52) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (6.44,0.45) {};
+\node[vertex] (v67) at (6.44,0.90) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (6.44,1.35) {};
+\node[vertex] (v69) at (6.44,1.81) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (6.44,2.26) {};
+\node[vertex] (v71) at (6.44,2.71) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (6.44,3.16) {};
+\node[vertex] (v73) at (6.44,3.61) {};
+\path[comp] (v72) -- (v73);
+
+\node[vertex] (v74) at (6.44,4.06) {};
+\node[vertex] (v75) at (6.44,4.52) {};
+\path[comp] (v74) -- (v75);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.45) -- (7.00,0.45);
+\path[edge] (0,0.90) -- (7.00,0.90);
+\path[edge] (0,1.35) -- (7.00,1.35);
+\path[edge] (0,1.81) -- (7.00,1.81);
+\path[edge] (0,2.26) -- (7.00,2.26);
+\path[edge] (0,2.71) -- (7.00,2.71);
+\path[edge] (0,3.16) -- (7.00,3.16);
+\path[edge] (0,3.61) -- (7.00,3.61);
+\path[edge] (0,4.06) -- (7.00,4.06);
+\path[edge] (0,4.52) -- (7.00,4.52);
+\end{tikzpicture}
diff --git a/images/12-ec-from-oes18-fast.tex b/images/12-ec-from-oes18-fast.tex
new file mode 100644 (file)
index 0000000..36f279b
--- /dev/null
@@ -0,0 +1,186 @@
+\begin{tikzpicture}[auto]
+\node[vertex] (v0) at (0.51,0.00) {};
+\node[vertex] (v1) at (0.51,2.06) {};
+\path[comp] (v0) -- (v1);
+
+\node[vertex] (v2) at (0.67,0.41) {};
+\node[vertex] (v3) at (0.67,1.24) {};
+\path[comp] (v2) -- (v3);
+
+\node[vertex] (v4) at (0.82,0.82) {};
+\node[vertex] (v5) at (0.82,1.65) {};
+\path[comp] (v4) -- (v5);
+
+\node[vertex] (v6) at (0.51,2.47) {};
+\node[vertex] (v7) at (0.51,3.71) {};
+\path[comp] (v6) -- (v7);
+
+\node[vertex] (v8) at (0.67,2.88) {};
+\node[vertex] (v9) at (0.67,3.29) {};
+\path[comp] (v8) -- (v9);
+
+\node[vertex] (v10) at (0.51,4.12) {};
+\node[vertex] (v11) at (0.51,4.53) {};
+\path[comp] (v10) -- (v11);
+
+\node[vertex] (v12) at (1.34,0.00) {};
+\node[vertex] (v13) at (1.34,0.82) {};
+\path[comp] (v12) -- (v13);
+
+\node[vertex] (v14) at (1.34,1.65) {};
+\node[vertex] (v15) at (1.34,2.06) {};
+\path[comp] (v14) -- (v15);
+
+\node[vertex] (v16) at (1.34,2.47) {};
+\node[vertex] (v17) at (1.34,2.88) {};
+\path[comp] (v16) -- (v17);
+
+\node[vertex] (v18) at (1.34,3.29) {};
+\node[vertex] (v19) at (1.34,3.71) {};
+\path[comp] (v18) -- (v19);
+
+\node[vertex] (v20) at (1.85,0.00) {};
+\node[vertex] (v21) at (1.85,1.24) {};
+\path[comp] (v20) -- (v21);
+
+\node[vertex] (v22) at (2.01,0.41) {};
+\node[vertex] (v23) at (2.01,2.06) {};
+\path[comp] (v22) -- (v23);
+
+\node[vertex] (v24) at (2.16,0.82) {};
+\node[vertex] (v25) at (2.16,1.65) {};
+\path[comp] (v24) -- (v25);
+
+\node[vertex] (v26) at (1.85,2.47) {};
+\node[vertex] (v27) at (1.85,4.53) {};
+\path[comp] (v26) -- (v27);
+
+\node[vertex] (v28) at (2.01,2.88) {};
+\node[vertex] (v29) at (2.01,3.29) {};
+\path[comp] (v28) -- (v29);
+
+\node[vertex] (v30) at (2.01,3.71) {};
+\node[vertex] (v31) at (2.01,4.12) {};
+\path[comp] (v30) -- (v31);
+
+\node[vertex] (v32) at (2.68,0.41) {};
+\node[vertex] (v33) at (2.68,0.82) {};
+\path[comp] (v32) -- (v33);
+
+\node[vertex] (v34) at (2.68,1.24) {};
+\node[vertex] (v35) at (2.68,1.65) {};
+\path[comp] (v34) -- (v35);
+
+\node[vertex] (v36) at (2.68,2.88) {};
+\node[vertex] (v37) at (2.68,3.71) {};
+\path[comp] (v36) -- (v37);
+
+\node[vertex] (v38) at (2.83,3.29) {};
+\node[vertex] (v39) at (2.83,4.53) {};
+\path[comp] (v38) -- (v39);
+
+\node[vertex] (v40) at (3.35,0.00) {};
+\node[vertex] (v41) at (3.35,0.41) {};
+\path[comp] (v40) -- (v41);
+
+\node[vertex] (v42) at (3.35,0.82) {};
+\node[vertex] (v43) at (3.35,1.24) {};
+\path[comp] (v42) -- (v43);
+
+\node[vertex] (v44) at (3.35,1.65) {};
+\node[vertex] (v45) at (3.35,2.06) {};
+\path[comp] (v44) -- (v45);
+
+\node[vertex] (v46) at (3.35,2.47) {};
+\node[vertex] (v47) at (3.35,2.88) {};
+\path[comp] (v46) -- (v47);
+
+\node[vertex] (v48) at (3.35,3.29) {};
+\node[vertex] (v49) at (3.35,3.71) {};
+\path[comp] (v48) -- (v49);
+
+\node[vertex] (v50) at (3.35,4.12) {};
+\node[vertex] (v51) at (3.35,4.53) {};
+\path[comp] (v50) -- (v51);
+
+\node[vertex] (v52) at (3.86,0.00) {};
+\node[vertex] (v53) at (3.86,2.47) {};
+\path[comp] (v52) -- (v53);
+
+\node[vertex] (v54) at (4.01,0.41) {};
+\node[vertex] (v55) at (4.01,2.88) {};
+\path[comp] (v54) -- (v55);
+
+\node[vertex] (v56) at (4.17,0.82) {};
+\node[vertex] (v57) at (4.17,3.29) {};
+\path[comp] (v56) -- (v57);
+
+\node[vertex] (v58) at (4.32,1.24) {};
+\node[vertex] (v59) at (4.32,3.71) {};
+\path[comp] (v58) -- (v59);
+
+\node[vertex] (v60) at (4.48,1.65) {};
+\node[vertex] (v61) at (4.48,4.12) {};
+\path[comp] (v60) -- (v61);
+
+\node[vertex] (v62) at (4.63,2.06) {};
+\node[vertex] (v63) at (4.63,4.53) {};
+\path[comp] (v62) -- (v63);
+
+\node[vertex] (v64) at (5.15,1.65) {};
+\node[vertex] (v65) at (5.15,2.47) {};
+\path[comp] (v64) -- (v65);
+
+\node[vertex] (v66) at (5.30,2.06) {};
+\node[vertex] (v67) at (5.30,2.88) {};
+\path[comp] (v66) -- (v67);
+
+\node[vertex] (v68) at (5.82,0.82) {};
+\node[vertex] (v69) at (5.82,1.65) {};
+\path[comp] (v68) -- (v69);
+
+\node[vertex] (v70) at (5.97,1.24) {};
+\node[vertex] (v71) at (5.97,2.06) {};
+\path[comp] (v70) -- (v71);
+
+\node[vertex] (v72) at (5.82,2.47) {};
+\node[vertex] (v73) at (5.82,3.29) {};
+\path[comp] (v72) -- (v73);
+
+\node[vertex] (v74) at (5.97,2.88) {};
+\node[vertex] (v75) at (5.97,3.71) {};
+\path[comp] (v74) -- (v75);
+
+\node[vertex] (v76) at (6.49,0.41) {};
+\node[vertex] (v77) at (6.49,0.82) {};
+\path[comp] (v76) -- (v77);
+
+\node[vertex] (v78) at (6.49,1.24) {};
+\node[vertex] (v79) at (6.49,1.65) {};
+\path[comp] (v78) -- (v79);
+
+\node[vertex] (v80) at (6.49,2.06) {};
+\node[vertex] (v81) at (6.49,2.47) {};
+\path[comp] (v80) -- (v81);
+
+\node[vertex] (v82) at (6.49,2.88) {};
+\node[vertex] (v83) at (6.49,3.29) {};
+\path[comp] (v82) -- (v83);
+
+\node[vertex] (v84) at (6.49,3.71) {};
+\node[vertex] (v85) at (6.49,4.12) {};
+\path[comp] (v84) -- (v85);
+
+\path[edge] (0,0.00) -- (7.00,0.00);
+\path[edge] (0,0.41) -- (7.00,0.41);
+\path[edge] (0,0.82) -- (7.00,0.82);
+\path[edge] (0,1.24) -- (7.00,1.24);
+\path[edge] (0,1.65) -- (7.00,1.65);
+\path[edge] (0,2.06) -- (7.00,2.06);
+\path[edge] (0,2.47) -- (7.00,2.47);
+\path[edge] (0,2.88) -- (7.00,2.88);
+\path[edge] (0,3.29) -- (7.00,3.29);
+\path[edge] (0,3.71) -- (7.00,3.71);
+\path[edge] (0,4.12) -- (7.00,4.12);
+\path[edge] (0,4.53) -- (7.00,4.53);
+\end{tikzpicture}