Permutação de vértices

Uma permutação, ou listagem, ou ordenamento, dos vértices de um grafo é uma sequência de vértices em que cada vértice aparece uma e uma só vez.  Por exemplo,

d e f g h a b c

é uma permutação dos vértices de um grafo cujos vértices são  a b c d e f g h .  Outro exemplo:

4 1 3 5 0 2

é uma permutação dos vértices de um grafo cujos vértices são  0 1 2 3 4 5 . 

Uma permutação dos vértices pode ser representada por um vetor cujos elementos são os vértices.  Se  vv[]  é um tal vetor, então vv[i] é o i-ésimo vértice da permutação.  Por exemplo,

   i   0 1 2 3 4 5 6 7
vv[i]  d e f g h a b c

representa a permutação dada num dos exemplos acima.  O outro exemplo pode ser representado pelo vetor

   i   0 1 2 3 4 5
vv[i]  4 1 3 5 0 2

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