Как можно проверить образуют ли заданные вершины в заданном порядке гамильтонов цикл. с++
Граф, имеющий n вершин, задан соответствующей матрицей смежности и даны вершины v1, v2, v3,…, vn+1. Напишите программу, которая проверяет, образуют ли вершины в заданном порядке гамильтонов цикл. Можете написать функцию, которая это проверяет?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Если v1 не совпадает с vn+1 - fail.
Если для любой из пар соседей (например v2 и v3) в данном списке не существует ребро в таблице смежности -fail
Для каждой пары пометить первую вершину из пары. Если вершина уже была помечена - fail.