2
$\begingroup$

Suppose I have a graph which is like this:

A--B--C--D

What is the diameter and radius of this graph?

Here r = 1 and d = 3 and r < d/2 ..right ?

  • 2
    The diameter is $3$, but the radius is $2$: the eccentricities of $A,B,C$ and $D$ are $3,2,2$, and $3$, and the radius is the minimum of these numbers.2012-04-15
  • 0
    Oh yes, you are right. I got the definition of eccentricity wrong.2012-04-15
  • 0
    @Brian, I guess that should be posted as an answer.2012-04-15

1 Answers 1

3

The diameter is $3$, but the radius is $2$: the eccentricities of $A,B,C$, and $D$ are $3,2,2$, and $3$, respectively, and the radius is the minimum of the eccentricities.

Note that you can never have $r<d/2$. If $u$ is a vertex of eccentricity $r$, and $v$ and $w$ are any vertices, there must be paths of length at most $r$ from $v$ and $w$ to $u$, so there must be a path of length at most $2r$ from $v$ to $w$. Thus, $d\le 2r$.

  • 0
    Hi Brian, When I read this answer, I ran into a challenge. I knows $D$ Diameter is maximum of minimum paths between two vertex of a graph. $L(S)$ is maximum length of minimum paths from $s$ to other vertexes and $R$ Radius of graph is minimum number of $L(s)$ between all vertex of a graph. so in undirected graph can we conclude always $R \leq D$ and $ R \geq D/2 $ is hold?2015-03-27
  • 0
    @user153695: Yes.2015-03-28
  • 0
    Prof. Brian, my last question is, if you want choose one of these condition for undirected graph G, which one is better to select?2015-03-28
  • 0
    @user153695: I would not say that either is better than the other: they express two different facts about the radius and diameter.2015-03-28
  • 0
    Prof. Brian thanks so much, I found a new link on http://math.stackexchange.com/questions/1209847/questions-on-diameter-and-radius-of-an-undirected-graph that exactly mentioned this question,would you please see it and share your experience? thanks.2015-03-29
  • 0
    @user153695: That one has now been deleted by one of the moderators. He didn’t say why, but I suspect that it was for the same reason that I can’t really answer the question: it doesn’t make sense to me to call either of the inequalities better in general (though in any given problem one of them might be more useful than the other).2015-03-30
  • 0
    Thanks so much Prof. Brian. In context of graph theory in computer science, can we say which one is better? is it possible to make any difference between them ( you say in specific domain can be better inequalities there? which one ?) ? thanks from wasting your valuable time. thanks.2015-03-30
  • 0
    @user153695: I think that it will depend more on the specific problem than on the domain from which the problem comes. It’s possible, I suppose, that in conputer science one of the inequalities is useful more often than the other, but if so, it would take someone with more knowledge of the field than I have to say which. If the question comes from some sort of exam, my honest opinion is that it’s probably just a bad question.2015-03-30
  • 0
    my prof. exactly copy the question 4 from http://stolzen.googlecode.com/svn/trunk/courses/coursera/Algorithms%20Design%20and%20Analysis%20Part%201/week4/week4_quiz_feedback.pdf but say choose the best answer (it means just one of them is correct) thanks again.2015-03-30
  • 0
    @user153695: Are you sure that you gave the right link? On that PDF Question $4$ is about computing topological orderings. Question $3$ is about radius and diameter, but it allows multiple correct answers.2015-03-30
  • 0
    Question (3) on that link. sorry professor. when my professor copy this question in his exam, wrote one of them is best and in answer sheet say $r \geq D/2$2015-03-30
  • 0
    @user153695: Okay. In question $3$ you don’t have to pick a single best answer: you have to pick all of the statements that are always true, which is the first three statements.2015-03-30
  • 0
    No, just second and third in that link is True, and when my prof. copy it on our exam, just $r \geq D/2$ is right because it's better. :)2015-03-30
  • 0
    @user153695: Sorry, you’re right about the first one: I misremembered the question when I typed the last comment. I don’t have any idea what your professor is thinking; I agree with the PDF that both the second and third are correct, and I see no basis for saying that one is better than the other. You’ll have to ask him, I guess.2015-03-30
  • 0
    you means there is no counterexample with these two statements? if the graph is not connected again two of them is hold ? or one of them? thanks professor. you are the best person2015-03-30
  • 0
    @user153695: That’s right: if $G$ is connected, both statements are always true. You’re welcome!2015-03-30
  • 0
    wow, one last question, if $G$ is not connected, none of them?2015-03-30
  • 0
    @user153695: If $G$ is not connected, the diameter and radius are both infinite, so we don’t normally talk about them.2015-03-30