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

IP>Здравствуйте!
IP>Вот попросила девушка решить задачку.ТОлько вот я с ними дело раньше не имел. Чуток разобрался с ними... но пока в голове каша. Не могу привязать теорию именно к этой задаче. В общем вот:

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

IP>Условие перпендикулярности есть. Только вот как, за что схватиться и как это привязать к графам... что то я не соображу... Как человеку, никогда не имевшему дело с теорией графов мне лезут в голову лишь алгоритмы которые с графами связать трудно)).
IP>Вобшем, подскажите логику решения, а лучше намек алгоритмом))

Строим неориентированный граф, вершины которого будут соответствовать векторам, а ребро между вершинами (i,j) будет существовать, если соответсвующие вектора ортогональны. Далее получаем задачу о нахождении максимального независимого подмножества
http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
либо эквивалентную ей задачу о нахождении максимальной клики в графе, множество ребер которого является дополнением множества ребер первой задачи
http://mathworld.wolfram.com/Clique.html
http://en.wikipedia.org/wiki/Clique_problem