Вопрос про графы - Public forum of MSU united student networks

Если хочется найти нетривиальное решение, то может быть тебе поможет такая идея. Запишем матрицу смежности для этого графа (при этом считаем, что на диагонали стоят 1 - из вершины можно пройти в саму себя). Для каждого из векторов вида (1,0,0,...,0), (0,1,0,...,0),..., (0,0,0,...,1) проделываем следующую операцию: применяем к нему матрицу смежности (один или несколько раз) до тех пор, пока количесво ненулевых координат в нем возрастает. Получаем n векторов, по крайней мере один из которых имеет все ненулевые координаты (тот, который соответствует вершине из которой можно пройти во все другие), так вот такие векторы не рассматриваем

. Теперь наша задача выбрать среди оставшихся систему попарно ортогональных векторов с максимальной суммой количества ненулевых координат в них. Это можно сделать, например, рекурсией: берем какой-нибудь вектор и из нашего набора оставляем лишь те векторы, которые ему ортогональны (т.е. имеют нули на тех местах, где выбранный вектор их не имеет) и с этим поднабором проводим ту же операцию; перебрав все допустимые наборы, находим тот из них, который имеет максимальную сумму количества ненулевых координат. Когда такой набор найден, по нему строим искомые подграфы: k-ый подграф содержит те вершины, которые имеют номера ненулевых координат в k-ом векторе найденного набора.
Надеюсь, мне удалось объяснить алгоритм достаточно внятно, если нет - извини и задавай вопросы. Может, конечно, он тебя не устроит.