how to draw a graph

Question

Kajal Agrawal 2023-6-3

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1977639-how-to-draw-a-graph

评论： Dyuman Joshi 2023-6-4

i have 12 vertices and 36 edges, how to draw a regular graph (all vertices having same degree).

3 个评论
显示 1更早的评论隐藏 1更早的评论

Kajal Agrawal 2023-6-3

degree= 2 edges/ vertices

and all the vertices should be same degree. (6-regular graph).

Dyuman Joshi 2023-6-4

@Kajal Agrawal

My solution which is currently the accepted answer, is incorrect.

Please accept the other answer, which provides a correct and concise solution to your problem. I shall be deleting my answer shortly.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Diwakar Diwakar 2023-6-3

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1977639-how-to-draw-a-graph#answer_1249519

To draw a regular graph with 12 vertices and 36 edges, we need to find the degree of each vertex. In a regular graph, all vertices have the same degree.

To find the degree, we can use the formula:

2 * number of edges = sum of degrees of all vertices

In this case, the number of edges is 36, so:

2 * 36 = sum of degrees of all vertices

72 = sum of degrees of all vertices

Since the graph is regular, all vertices will have the same degree, which we can denote as 'd'. Therefore, we have:

12 * d = 72

Dividing both sides of the equation by 12, we find:

d = 72 / 12

d = 6

So, each vertex in the graph will have a degree of 6.

Now, let's draw the graph. Since it is a regular graph, we can use a symmetric pattern to make it easier to visualize. Here's one possible way to draw the graph:

1 -- 2 -- 3 -- 4 -- 5 -- 6 -- 7 -- 8 -- 9 -- 10 -- 11 -- 12 -- 1

In this representation, the vertices are numbered from 1 to 12, and each vertex is connected to the next vertex in a circular manner. Each vertex is connected to its two neighboring vertices, and the degree of each vertex is 6.

Note that there can be multiple valid drawings of a regular graph with the same specifications. The example above is just one possible representation.

3 个评论
显示 1更早的评论隐藏 1更早的评论

John D'Errico 2023-6-4

编辑：John D'Errico 2023-6-4

在 MATLAB Online 中打开

A good answer. It is clear, explains everything. I like what you have written so far, but it stops short a little, because you don't show the last steps of how a graph where each node has degree 6 might be constructed. That may be by choice, since no effort was shown in the question. But since there is already an accepted answer, I'll add a bit in this comment.

S = 1:12;

T = circshift(S,1);

G1 = graph(S,T)

G1 =

graph with properties: Edges: [12×1 table] Nodes: [12×0 table]

That constructs the simple graph you describe, where each node is connected to its immediate neighbor.

plot(G1)

The degree of those nodes is only 2 however.

But we can arbitrarily choose a second and a third set of shifts, each of which will add 2 more degrees to each node. I've chosen 3 and 7 below for no good reason, except to point out that many other choices would have been equally as good. (A shift of 11 would have been a bad choice, because a circular shift of 11 is equivalent to a circular shift of -1, which is equivalent to a circular shift of 1 in this respect when we create the graphs.)

T3 = circshift(S,3);
T7 = circshift(S,7);
G3 = graph(S,T3);
G7 = graph(S,T7);

Finally, build a complete graph. There may be a better way than extracting the adjacency matrices here, but I don't terribly care. ;-)

G = graph(adjacency(G1) + adjacency(G3) + adjacency(G7))

G =

graph with properties: Edges: [36×2 table] Nodes: [12×0 table]

degree(G)

ans = 12×1

6 6 6 6 6 6 6 6 6 6

plot(G)

As you can see, each node has degree 6. There are 36 edges in total, 12 nodes. If one (carefully) counts the number of edges emanating from every node in that last plot, there should be 6 edges.

Kajal Agrawal 2023-6-4

thank you so much

John D'Errico 2023-6-4

As I think about it, this can lead into greater mathematical depths. For example the concept of a derangement.

A derangement is a permutation of a set, such that no element resides in its original position. For even 12 elements, the number of possible derangements is pretty large.

https://en.wikipedia.org/wiki/Derangement

As well, The OEIS tells us there are 176,214,841 possible derenagements of 12 elements.

https://oeis.org/A000166

There we would also learn the subfactorial is useful to enumerate that number.

But you should also note that at least SOME of the derangements of the numbers 1:12 can lead to a regular graph with degree 2. And then we can use that idea to build a graph where each node has degree 6.

请先登录，再进行评论。