Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, i.pilat, Вы писали:

IP>>Задача по теме "поиск с возвратом. Задачи на графах".
IP>>Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает).

V_>Если построить граф, где вершины — вектора, а между двумя вершинами есть ребро, если соответствующие вектора ортогональны, то исходная задача будет сведена к поиску минимального вершинного покрытия для данного графа. Эта задача является NP-полной, насколько я знаю.
Вот и возникает вопрос причем тут графы.

Итак,
V -- исходное множество векторов.
W -- линейное многообразие V, то есть линейная комбинация векторов из множества V (заранее извиняюсь, если я напутал с терминами).
Размер базиса W (число ортоганальных векторов, линейная комбинация которых равна W) не зависит от входящих в него векторов. Таким образом нужно просто найти все ортогональные вектора, а все остальные и будут тем минимальным количеством векторов. Зачем здесь графы я не понимаю, но если у нас вершины графа -- это вектора, а ребра означают ортоганальность векторов, то получается что нужно просто найти все смежные вершины для какой то одной. Все не смежные нужно удалить.