(The eigenvalues are all integers.) = eig(L) Īnd here is the resulting plot. Here are all of the eigenvalues and three of the eigenvectors. The coordinates of possible layouts for the plot of the graph can be obtained by picking three of the eigenvectors of the Laplacian. The Laplacian could also be obtained from the original adjacency matrix. For the 3-d hypercube the degrees are all 4. The Laplacian of a graph is a matrix that has the degree of the nodes on the diagonal and -1's off the diagonal marking the edges. % 8-by-3 array of vertices of a unit cube. I can supply my own coordinates for the vertices. The blue dot in the center is not a node - it is just the point where many edges cross. Notice that '3' is not connected to '4' because 00 differ by more than a single bit. nodes = num2cellstr(0:15)' īut 'circle' is another attractive layout. I think the default layout of the 4-d hypercube is attractive. The default layout of the 3-d hypercube graph is a perspective view of an ordinary cube. 'subspace3' 3-D Subspace embedding layout. 'auto' (Default) Automatic choice of layout method based on Here are the currently available layouts. Coming up with good layouts is an art, as well as a science. In order to plot it you specify a layout, or coordinates, for the nodes. nodes = num2cellstr(0:7)īy itself, a graph doesn't have any geometric structure. We'll label the nodes with '0' through '7'. To get other views, let's use the new MATLAB graph object. (It's so small that it's not necessary to make use of the sparsity.) A = hypercube(3)
Here is the adjacency matrix of a 3-d hypercube. If you had a wire-frame cube made from rubber bands and squished it around without destroying the connectivity, you wouldn't have a cube any more, but you would still have a model of a hypercube. The cube itself includes its surfaces and interior. The 3-d hypercube is only the vertices and edges of the cube. But undirected graphs have simpler plots.) 3dĪ 3-dimensional hypercube is not a conventional cube. (Actually, the IPSC's graph is a directed graph, a digraph, because the connections are two-way. The d6 model has the same graph as the patience puzzle that I wrote about in my previous post.
For the d6 that's 384 connections instead of 4096. For a machine with $n = 2^d$ processors, that's $n \log_2$ instead of $n^2$ connections. Since it was impractical to connect every processor directly to every other processor, the connection network formed a hypercube. We had three models - d5, d6 and d7 - with 32, 64 or 128 processors. The IPSC was constructed from single board computers, similar to the mother boards in the PCs of the day. For a couple of years in the late 1980s I was involved with one of the world's first commercial parallel computers, the IPSC, the Intel Personal Super Computer. I first encountered hypercubes thirty years ago. % Flip bits to get corresponding row indices. % hypercube(d) is a logical adjacency matrix for a d-dimensional hypercube.į2b = floor(rem(j./pow2,2)) % flint to binary NAMES must have as many elements asĪnd here is a function that generates the adjacency matrix for a hypercube. G = graph(A,NAMES) additionally uses the cell array of strings NAMES as If A is logical then no weights are added. G = graph(A) uses the square symmetric matrix A as an adjacency matrixĪnd constructs a weighted graph with edges corresponding to the nonzeroĮntries of A. Here is an abbreviated help entry for graph. Recent versions of MATLAB include two new objects, graph and digraph. That connectivity arrangement - those vertices and the connections between them - form a graph known as a hypercube. Each vertex is connected to six other vertices, the ones whose numbers, expressed in binary, differ from its own by one bit. There are 64 vertices, numbered 0 from to 63.
The puzzle's state lives in a six-dimensional space.
My previous blog post was about the Patience Chinese Rings Puzzle.
0 kommentar(er)
