0

I saw a nice question & answer over here, about creating an animation to demonstrate graph isomorphism. I'd like to do the same for these two examples:

These two are isomorphic: enter image description here These two aren't isomorphic: enter image description here


I realize most of the code is provided at the link I provided earlier, but I'm not very experienced with LaTeX, and I'm just having a little trouble adapting the code to suit the new graphs.

So, I have this shape (a pentagon):

\documentclass{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}
\tikzset{Bullet/.style={circle,draw,fill=black,scale=0.75}}
\node[Bullet,label=left :{$e_1$}] (E1) at (0,2) {} ;
\node[Bullet,label=above:{$e_2$}] (E2) at (1,3) {} ;
\node[Bullet,label=right:{$e_3$}] (E3) at (2,2) {} ;
\node[Bullet,label=right:{$e_4$}] (E4) at (2,0) {} ;
\node[Bullet,label=left :{$e_5$}] (E5) at (0,0) {} ;
\draw[thick] (E1)--(E2)--(E3)--(E4)--(E5)--(E1) {} ;
\end{tikzpicture}
\end{document}

And I have this shape (a pentagram):

\documentclass{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}
\tikzset{Bullet/.style={circle,draw,fill=black,scale=0.75}}
\node[Bullet,label=left :{$c_1$}] (C1) at (0,2) {} ;
\node[Bullet,label=above:{$c_2$}] (C2) at (1,3) {} ;
\node[Bullet,label=right:{$c_3$}] (C3) at (2,2) {} ;
\node[Bullet,label=right:{$c_4$}] (C4) at (2,0) {} ;
\node[Bullet,label=left :{$c_5$}] (C5) at (0,0) {} ;
\draw[thick] (C1)--(C3)--(C5)--(C2)--(C4)--(C1) {} ;
\end{tikzpicture}
\end{document}

The code is basically the same for each one. Other than the names & labels on the vertices, the only real difference between the two, is the edges are joining different pairs vertices together. So the pentagon goes 1-2-3-4-5-1, and the pentagram goes 1-3-5-2-4-1.

Anyway, all I need to know is how to animate one morphing into the other and back again. I'm still getting the hang of LaTeX, so I'm trying to keep it simple. Thanks in advance.

  • Maybe you could indicate where your first difficulty arises when you try to adapt the code from that example, to save effort for the people who might answer. – Benjamin McKay Mar 10 '19 at 9:05
  • @BenjaminMcKay I think my issue is just simply drawing the new graphs. It seems like if I could draw the graphs, I could probably just cut and paste their code/coordinates, etc. into the original animation script. – voices Mar 10 '19 at 9:20
  • To show that the first two graphs are isomorphic is straightforward and an animation can easily be written. However, how would one use an animation to show that two graphs are not isomorphic? – user121799 Mar 10 '19 at 22:50
  • @marmot I'm not sure. How would I? – voices Mar 11 '19 at 4:39
  • @tjt263 Yes, this is what I am wondering. You can draw an animation which shows that you cannot do a certain deformation without cutting the connections, but this does not prove that there is no such deformation. – user121799 Mar 11 '19 at 4:45
6

One way to show equivalence is to draw the graph in 3d and then move the vertices around.

\documentclass[tikz,border=3.14mm]{standalone}
\usepackage{tikz-3dplot}
\begin{document}
\pgfmathsetmacro{\t}{135}
\pgfmathsetmacro{\R}{3}
\tdplotsetmaincoords{70}{0}
\foreach \t in {0,4,...,180}
{\begin{tikzpicture}[tdplot_main_coords,font=\sffamily,
bullet/.style={circle,fill,inner sep=1.5pt}]
 \path[use as bounding box,tdplot_screen_coords] 
 (-1.2*\R,-1.2*\R) rectangle (1.2*\R,1.2*\R);
 \pgfmathsetmacro{\tmax}{2*max(\t-90,0)}
 \node[bullet,label=above:v1] (v1) at (0,0,\R){};
 \node[bullet,label=\tmax:v2] (v2) at 
  ({\R*cos(min(\t,90))*cos(18)+\R*sin(min(\t,90))*cos(-54)
  +2*\R*cos(max(\t,90))*cos(-54)},{\R*sin(min(2*\t,180))},%
   {\R*cos(min(\t,90))*sin(18)+\R*sin(min(\t,90))*sin(-54)}){};
 \node[bullet,label=right:v3] (v3) at 
  ({\R*sin(min(\t,90))*cos(18)+\R*cos(min(\t,90))*cos(-54)},{-\R*sin(min(2*\t,180))},%
   {\R*sin(min(\t,90))*sin(18)+\R*cos(min(\t,90))*sin(-54)}){};
 \node[bullet,label=left:v4] (v4) at 
  ({-1*\R*sin(min(\t,90))*cos(18)-\R*cos(min(\t,90))*cos(-54)},{-\R*sin(min(2*\t,180))},%
   {\R*sin(min(\t,90))*sin(18)+\R*cos(min(\t,90))*sin(-54)}){};
 \node[bullet,label=180-\tmax:v5] (v5) at 
  ({-1*\R*cos(min(\t,90))*cos(18)-\R*sin(min(\t,90))*cos(-54)
  -2*\R*cos(max(\t,90))*cos(-54)},{\R*sin(2*\t)},%
   {\R*cos(min(\t,90))*sin(18)+\R*sin(min(\t,90))*sin(-54)}){};
 \draw[thick]   (v1) -- (v3) -- (v5) -- (v2) -- (v4) -- (v1);
\end{tikzpicture}}
\end{document}

enter image description here

If you want to follow the strategy of this answer, you may define a dictionary between the original and mapped vertex names and its inverse, called \LstMapped and \LstMappedInverse in what follows. Then you may use partway modifiers, as in the original post and as explained in section 4.2.1 Using Partway Calculations for the Construction of D of the pgfmanual to interpolate between the coordinates.

\documentclass[tikz,border=3.14mm]{standalone}
\usetikzlibrary{calc}
\begin{document}
\foreach \t in {0,0.05,...,1,1,0.95,...,0}
{\begin{tikzpicture}[bullet/.style={fill,circle,inner sep=1.5pt},font=\sffamily]
 \path[use as bounding box] (-3.5,-3.5) rectangle (3.5,3.5);
 \edef\LstMapped{{1,3,5,2,4}}
 \edef\LstMappedInverse{{1,4,2,5,3}}
 \foreach \X in {1,...,5}
  {\pgfmathtruncatemacro{\Xmapped}{\LstMapped[\X-1]}
   \coordinate[alias=v'\Xmapped] (v\X) at (90+72-72*\X:3);}
  \foreach \X in {1,...,5} 
  {\pgfmathtruncatemacro{\Xmapped}{\LstMappedInverse[\X-1]}
  \node[bullet,label={[opacity=1-\t]90+72-72*\X:$v_\X$},
 label={[opacity=\t]90+72-72*\Xmapped:$v_\Xmapped'$}] (m\X) at ($(v\X)!\t!(v'\X)$){};}
 \draw (m1) -- (m3) -- (m5) -- (m2) -- (m4) -- (m1);
\end{tikzpicture}}
\end{document}

enter image description here

  • This is good, but what I really want is to understand the coordinates in the referenced code. I tried to draw the new graphs with the same coordinate system, but I can't figure it out. I'm still experimenting. – voices Mar 11 '19 at 5:09
  • @tjt263 The coordinates in the referenced code are easily understood. There is a set of coordinates Ci and Hi where 1 <= i <= 7. The coordinates Mi are then at ($(H\i)!\nxb!(C\i)$), where 0 <= \nxb <= 1 indicates the decomposition. – user121799 Mar 11 '19 at 7:30
  • Easily understood by you maybe. I'll have another look. – voices Mar 11 '19 at 7:49
  • @tjt263 Sorry, the comment may sound differently from what I wanted to say. Please have a look at section 4.2.1 Using Partway Calculations for the Construction of D of the pgfmanual to see what the syntax ($(A)!\fraction!(B)$) means. In formulas, ($(A)!\fraction!(B)$) = (1-\fraction) * (A) + \fraction * (B). So if \fraction=0 you get (A), for \fraction=1 B, and something in between for other values of \fraction. – user121799 Mar 11 '19 at 7:57
  • Thanks, I appreciate your help, but it's a bit over my head at this stage. I updated the question to include my code. It's pretty basic in comparison, but that's where I'm at. I mean, I could just copy and paste your example verbatim, but I wouldn't really learn anything that way. Can I just drop the animate code into what I've already got? – voices Mar 11 '19 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.