Como criar gráficos regulares (planares) ?
Como criar programaticamente e plotar gráficos planares regulares comk=3,4 ou 6 (não hipercubos) e gráficos não planares regulares dek=8 (veja a figura)? Observe que o que importa é a conectividade média, já que nós nas bordas e cantos têm menork valores. Existe algum método fácil de fazer isso, ou é preciso escrever sua própria VertexCoordinates função e o método para gerar o gráfico apropriado?
Além disso, como criar e plotar gráficos planares aleatórios , onde apenas a conectividade média é fornecida e os nós possivelmente têm conectividade variável. Observe que o Pacote de Geometria Computacional tem alguns meios para lidar com gráficos planares, mas, por exemplo, PlanarGraphPlot só pode fornecer a triangulação de Delaunay do conjunto de dados fornecido. Assim, as arestas não podem ser especificadas para, por exemplo, gráficos superior direito e inferior esquerdo na figura
Meu amigo CP e eu descobrimos essas soluções. O primeiro é CPs 'Aqui vamos nós. Primeiras coisas a saber:
1) A funcionalidade nova Graph[] e relacionada na v8.0.4 é poderosa no sentido de que não apenas cria uma imagem, mas também armazena todas as informações, incluindo as coordenadas do vértice, naquele Graph[] objeto.
2) Há uma GridGraph[...] função que faz exatamente o que foi nomeado
Agora, começando com GridGraph[...] você pode simplesmente adicionar ou remover arestas para obter seus diagramas.
g[m_, n_] := GridGraph[{m, n}, VertexSize -> 0.3, VertexStyle -> White, EdgeStyle -> Black] edges[m_, n_] := Flatten[Table[ If[Mod[j, m] != 0 && (j + m + 1 <= n*m), UndirectedEdge[j + m + 1, j], {}], {j, 1, n*m}]] altg[m_, n_] := EdgeAdd[g[m, n], edges[m, n]] altg[7, 5] 
O resto de seus diagramas pode seguir da mesma maneira. Outra forma seria descobrir a fórmula para construção da matriz de adjacência de seus diagramas. Depois é só usar AdjacencyGraph[...].
Mas provavelmente a maneira mais fácil de resolver isso (não necessariamente eficiente) é entender a conexão visual entre seus vértices. Em seguida, conecte os elementos de uma matriz exatamente dessa maneira e nivele a matriz. Você deve ser criativo com as coordenadas do vértice.
mat[m_, n_] := Flatten@Table[{ If[i < m, a[i, j] \[UndirectedEdge] a[i + 1, j], {}], If[j < n, a[i, j] \[UndirectedEdge] a[i, j + 1], {}], If[i < m && j < n, a[i, j] \[UndirectedEdge] a[i + 1, j + 1], {}] }, {i, m}, {j, n}] g[m_, n_] := Graph[mat[m, n], VertexCoordinates -> Thread[Sort[VertexList[Graph[mat[m, n]]]] -> Flatten[Table[{i, j}, {i, m}, {j, n}], 1]], VertexSize -> 0.4, VertexStyle -> White] g[7, 5]
===================== ATUALIZAÇÃO ===================
Acabei de perceber que temos alguns dados lindos embutidos para esse tipo de coisas.
SetProperty[GraphData[{"KingsTour", {10, 10}}], {VertexSize -> 0.4, VertexStyle -> White, EdgeStyle -> Black}] 
SetProperty[GraphData[{"KnightsTour", {10, 10}}], {VertexSize -> 0.4, VertexStyle -> White, EdgeStyle -> Black}] 