如何绘制谢尔宾斯基 4 循环图？

Question

几乎可以肯定的是，使用基本的 TikZ 命令来制作您关心的这些内容是最简单的事情。例如，

\begin{tikzpicture}
    \node[circle, draw, fill=black] (1) [label=south west:1] at (0,0) {};
    \node[circle, draw, fill=black] (2) [label=north west:2] at (0,1) {};
    \node[circle, draw, fill=black] (3) [label=north east:3] at (1,1) {};
    \node[circle, draw, fill=black] (4) [label=south east:4] at (1,0) {};
    \draw (1) -- (2) -- (3) -- (4) -- (1);
\end{tikzpicture}

但这有点无聊。所以我们来做点更有趣的事吧。

第一的，广义谢尔宾斯基图非常简洁，但它们并没有真正指定节点之间的距离。（我指的是绘制图形时的距离，而不是两个节点之间的最小路径长度。）查看您提供的图（我假设您是从 Gravier 等人那里复制的），看起来组成 S(n, C_4) 的 S(k-1,C_4) 的四个副本之间的距离为 n-1。所以让我们继续。

递归结构本身就适合递归解决方案。因此，我们在绘制 S(n, C_4) 时想要做的事情如下。

计算出 S(n-1, C_4) 的四个副本分别需要移动多少距离。
确定每个标签的放置位置。
绘制四个 S(n-1, C_4) 中的每一个，并进行适当移动和标记。
连接 S(n-1,C_4) 的四个副本中的适当节点。

第一步本身并不难，但需要解决一个基本的递归关系。我相信有更简单的方法来解决这个问题，但让 w(n) 成为 S(n, C_4) 的宽度。现在根据上面推导的分离规则，我们有递归 w(n) = 2*w(n-1) + n - 1 和 w(1) = 1。

我们可以使用任何标准方法（或者像我一样作弊，使用 Wolfram|Alpha）来解决这个问题，得到 w(n) = 3*2^(n-1) - n - 1。这给了我们宽度，但我们真正想要的是移位量 s(n) = w(n-1) + n - 1。解决这个问题得到 s(n) = 3*2^(n-2) - 1（n > 1）。对于 n = 1，让 s(1) = 1。（值得一提的是，这给出了A083329移位 1)。

第二步，标签放置，没有指定，所以我做了以下选择：每个节点都是 {1,2,3,4}^n 中的一个单词。例如，S(4, C_4) 有节点 1111、1112、1113、1114、1121、...、4444。值得标记的节点是其名称中的 (n-1) 符号一致的节点。因此，对于 n > 1，S(n, C_4) 将有 16 个带标签的节点（每侧四个），而 S(1, C_4) 将有所有四个带标签的节点。我对放置位置做了一些改动，我认为它们看起来不错/与相邻节点标签不重叠。

第三步，绘制，很简单。使用步骤 1 中计算出的移位量，绘制 4 个 S(n-1, C_4) 副本。

最后，我们需要在 4 个副本之间连接一些节点。但是什么节点呢？幸运的是，这在 S(n, G) 的定义中指定（对于任意 G）。对于 G 中的所有边 (x,y)，我们需要添加边 (xy...y, yx...x)。

现在我对 TikZ 不太了解，所以我希望专家能对我的代码提出改进建议。为了构建这个，我使用了库graphs并构建了一个图形宏。

\usepackage{tikz}
\usetikzlibrary{graphs}

\makeatletter
\newcommand*\s@dup[2]{%
    \ifnum\numexpr#1>\@ne
        #2%
        \s@dup{#1-\@ne}{#2}%
    \fi
}
\def\s@compute@label#1#2{%
    \def\s@quad{#1}%
    \ifx#2\relax
        \def\s@temp{#1}
        \edef\s@label{[label=\s@label@pos:\s@prefix]}%
    \else
        \def\s@temp{#2}%
        \expandafter\s@check@label
    \fi
}
\def\s@check@label#1{%
    \ifx#1\relax
        \edef\s@label{[label=\s@label@pos:\s@prefix]}%
    \else\if#1\s@temp
        \expandafter\expandafter\expandafter\s@check@label
    \else
        \expandafter\expandafter\expandafter\s@mismatch
    \fi\fi
}
\def\s@mismatch#1\relax{%
    \def\s@label{}%
}
\def\s@label@pos{%
    \ifcase\numexpr4*(\s@quad-1)+\s@temp-1\relax
        south west% 11
    \or west%       12
    \or north%      13
    \or south%      14
    \or west%       21
    \or north west% 22
    \or north%      23
    \or south%      24
    \or south%      31
    \or north%      32
    \or north east% 33
    \or east%       34
    \or south%      41
    \or north%      42
    \or east%       43
    \or south east% 44
    \fi
}

\tikzgraphsset{
    level/.store in=\s@level,
    prefix/.store in=\s@prefix,
    no placement,
    level=1,
    prefix={},
    declare={sierpinski}{%
        [/utils/exec={%
                \ifnum\s@level=\z@
                    % Step 2: Figure out what to label.
                    \expandafter\s@compute@label\s@prefix\relax
                    \edef\subgraph{\s@prefix \s@label}%
                \else
                    % Step 1: Compute the shift amount.
                    \ifnum\s@level=\@ne
                        \def\s@shift{1}%
                    \else
                        \pgfmathsetmacro\s@shift{3*pow(2,\s@level-2)-1}%
                    \fi
                    \count@=\s@level\relax
                    \advance\count@\m@ne
                    \edef\subgraph{%
                        % Step 3: Draw each of the four S(n-1, C_4) shifted appropriately.
                        sierpinski [level=\the\count@, prefix=\s@prefix1, /tikz/shift={(0,0)}];%
                        sierpinski [level=\the\count@, prefix=\s@prefix2, /tikz/shift={(0,\s@shift)}];%
                        sierpinski [level=\the\count@, prefix=\s@prefix3, /tikz/shift={(\s@shift,\s@shift)}];%
                        sierpinski [level=\the\count@, prefix=\s@prefix4, /tikz/shift={(\s@shift,0)}];%
                        % Step 4:  Connect edges.
                        \s@prefix1\s@dup\s@level2 -- \s@prefix2\s@dup\s@level1;% 12...2 -- 21...1
                        \s@prefix2\s@dup\s@level3 -- \s@prefix3\s@dup\s@level2;% 23...3 -- 32...2
                        \s@prefix3\s@dup\s@level4 -- \s@prefix4\s@dup\s@level3;% 34...4 -- 43...3
                        \s@prefix4\s@dup\s@level1 -- \s@prefix1\s@dup\s@level4;% 41...1 -- 14...4
                    }%
                \fi
            },%
            parse/.expand once=\subgraph
        ]%
    }
}
\makeatother

现在我们只需要使用它！

\begin{tikzpicture}
    \graph [nodes={circle, minimum size=4pt, inner sep=0pt, fill, empty nodes}] {sierpinski [level=1]};
\end{tikzpicture}

您可以通过更改参数来更改节点的绘制方式\graph。将level参数更改为sierpinski将产生 S(level, C_4)。以下是级别 2、3 和 4。

S(4, C_4) 很大，所以我添加了x和y参数来tikzpicture指定大小。

\begin{tikzpicture}[x=2em,y=2em]
    \graph [nodes={circle, minimum size=4pt, inner sep=0pt, fill, empty nodes}] {sierpinski [level=4]};
\end{tikzpicture}

我没有包含“副本 1”文本，因为这对我来说不那么有趣，但做到这一点应该不难。

Answer 1