Если нужен гамильтонов цикл(цепь) то тут только перебор с возвратом. А вот «минимальное количество раз проходить по одним и тем же вершинам», тут, наверное, надо сначала пытаться найти гамильтонов цикл(цепь), а потом увеличивать макс. возможное число вхождений вершин.
