How do I prove that diameter of undirected Ring Topology is n/2?


closed as unclear what you're asking by Evil, David Richerby, Rick Decker, Tom van der Zanden, Juho Sep 30 '16 at 10:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Welcome to CS.SE! Please ask only one question per question. I've edited out the 2nd question; you can ask it separately. Also, what did you try? Where did you get stuck? Have you tried working through some small examples? Have you tried writing down the definition of such a graph and working from there? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. $\endgroup$ – D.W. Sep 25 '16 at 3:00
  • 2
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Sep 25 '16 at 11:58
  • $\begingroup$ My apologies, This is the first time am asking a question to the CS community of stackexchange. But I found the link really helpful. Really thankful for that. I will try to follow the instructions for my next questions. $\endgroup$ – Shaan Sep 26 '16 at 22:13

To prove that the diameter of the undirected ring topology is $n/2$:

  1. Find two vertices $x,y$ at distance $n/2$.

  2. Show that any two vertices $x,y$ are at distance at most $n/2$.

By the way, the diameter is more accurately $\lfloor n/2 \rfloor$.

  • $\begingroup$ Is there any general way to calculate the diameter of a connected graph with a uniform degree equal to n? $\endgroup$ – Shaan Sep 25 '16 at 3:18
  • $\begingroup$ No, it depends on the graph, though you can get bounds on the diameter in terms of the degree and the number of vertices. $\endgroup$ – Yuval Filmus Sep 25 '16 at 3:21
  • $\begingroup$ so, what is the relation of diameter with dimension and number of vertices? $\endgroup$ – Shaan Sep 25 '16 at 3:24
  • 1
    $\begingroup$ I don't know what dimension is, but I think it's a good exercise to find such relations on your own. $\endgroup$ – Yuval Filmus Sep 25 '16 at 3:25

I tried this:
If n is even then n/2th node is the farthest node, else (n-1)/2th or (n+1)/2th node would be the farthest node.
In case of 'n' nodes the number of edges is 'n'
Assuming : If we have a ring of n/2 nodes(in case of even number of nodes) or (n-1)/2 (in case if n is odd) then the number of edges would be n/2 or (n-1)/2 for the rings to be connected which we can consider as the diameter.

Hence, n/2 with a lower bound would be the answer.


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