I have read few research papers in which given a graph $G$ where $V$ denotes its vertex set and $E$ denotes its edge set. Model of computation is word RAM. "Without loss of generality assume that vertices are numbered from $1$ to $n$"

Question : How to justify the above mentioned assumption? I am not getting why this assumption is valid?

  • 1
    $\begingroup$ Usually the set of vertices are given as an array $v_1,\dots,v_n$. You can mentally replace $v_i$ with $i$. $\endgroup$ Jan 25 '19 at 6:52
  • $\begingroup$ @I_wil_break_wall that just means names of the vertices don't really matter (as long as they are not too long). $\endgroup$ Jan 25 '19 at 7:02
  • $\begingroup$ @Yuval Filmus Exactly that is my question why i can assume that $v_i$ to $i$. From where this ordering is comming. Is it input ordering? $\endgroup$
    – user94342
    Jan 25 '19 at 7:58
  • $\begingroup$ Can you give an example where it’s not the case? This might help us understand your question. $\endgroup$ Jan 25 '19 at 8:52

Typically, graph problems don't depend on the "names" of the vertices. Finding a route from Paris to Berlin doesn't get any easier or harder if you rename the cities Sirap and Nilreb, or 6 and 32, or anything else. Indeed, in many cases, the vertices of the graph don't even have explicit names: they're just a set. Since changing the names of the vertices makes no difference, an algorithm doesn't become less powerful by assuming that the names are $1, \dots, n$, where $n$ is the total number of vertices. That is, there is no loss of generality in doing this.

$1, \dots, n$ is a useful choice of names because computers are good at dealing with numbers and because, typically, the vertices will be stored in some kind of array anyway (an array of adjacency lists or just an adjacency matrix). It makes sense to name the vertex after the array cell it occupies, so that the algorithm never has to worry about the distinction between "vertex $x$" and "the place where vertex $x$ is stored".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy