Я читал алгоритмы для поиска минимального остовного дерева (в случае взвешенных графов) и для определения, имеет ли граф гамильтонов путь (который зависит от наличия гамильтонова цикла). Я все испортил. Так в чем же разница между гамильтоновым путем и остовным деревом? Оба покрывают все вершины графа. Хотя у нас могут быть эффективные алгоритмы для поиска остовного дерева (возможно, минимального остовного дерева), почему мы не можем иметь алгоритмы для поиска гамильтоновой схемы? Мы можем продолжать добавлять и удалять по одному ребру за раз, пока не дойдем до цикла и, возможно, мы сможем найти гамильтонов цикл ??