Numeração dos vértices

Uma numeração dos vértices de um grafo é uma atribuição de rótulos numéricos inteiros aos vértices.  A numeração é injetiva (= ranking) se vértices diferentes recebam rótulos diferentes.  Como estamos supondo que os vértices são 0 1 2 3 ... , você pode imaginar que uma numeração injetiva é uma atribuição de novos nomes aos vértices.

Se os vértices do grafo são 0 1 2 ... n-1, uma numeração pode ser representada por um vetor cujos índices são vértices e cujos elementos são números inteiros.  Por exemplo, o seguinte vetor num[] representa uma numeração injetiva dos vértices 0 1 2 ... 5:

               v   0 1 2 3 4 5
           num[v]  4 1 5 2 0 3

Outro exemplo: uma numeração não injetiva dos mesmos vértices:

               v   0 1 2 3 4 5
           num[v]  0 0 0 1 1 1

Se os vértices do grafo são um subconjunto de 0 1 2 ... n-1 (como acontece quando estamos tratando do sub­grafo de um grafo maior), podemos representar uma numeração por um vetor indexado por 0 1 2 ... n-1 e restringir nossa atenção aos vértices relevantes.

(Veja também o conceito de permutação dos vértices e a relação entre permutação e numeração.)