Questões de Concurso Público INMETRO 2010 para Pesquisador Tecnologista - Metrologia em Informática

Um caminho é dito simples se passa exatamente uma vez por cada um dos vértices do grafo, e é unitário se passa exatamente uma vez por cada uma das arestas.

O comprimento de um percurso em um grafo não valorado corresponde à soma dos custos de percorrer cada aresta, e em um grafo valorado é igual ao número de arestas que o compõem.

Um ciclo que passa por todas as arestas de um grafo é dito hamiltoniano, e um circuito elementar que passa por todos os vértices denomina-se euleriano.

O problema do caixeiro viajante consiste em analisar todos os circuitos hamiltonianos existentes para n - 1 pontos.

Segundo o conceito de conexidade em grafos orientados, não é necessário que haja um caminho ligando qualquer par de vértices; se isso ocorrer, diz-se que o grafo é fortemente conexo, tal que, dados dois vértices, qualquer um pode ser atingido a partir do outro.