Добрый день!

Треугольником в неор.графе называется тройка вершин, попарно соединенных дугами. Склеиванием треуг. называется операция замены вершин треуг. новой вершиной с сохранением всех связей с остальными вершинами графа. Дан неор. граф. Склеить все треугольники.

Подскажите, пожалуйста, какой тут алгоритм? немножко не понимаю суть, алгоритм решения.

задан 28 Июн '17 11:57

10|600 символов нужно символов осталось
0

Наличие треугольников легко отслеживается при помощи полного перебора троек вершин. Поскольку в условии не сказано, в каком порядке надо проводить склейки, считаем этот порядок произвольным.

Пусть мы нашли тройку вершин a, b, c, которые попарно соединены рёбрами. Из графа, заданного в виде "базы данных", удаляем эти три вершины, и вместо них вводим новую вершину d. Далее перебираем все вершины, отличные от трёх удалённых, и если вершина x была соединена хотя бы с одной из трёх, то соединяем её с d в новом графе.

Указанное действие повторяем в цикле, пока не получится граф без треугольников. Ввиду того, что количество вершин всё время уменьшается, мы за конечное время придём к ответу.

Алгоритм имеет полиномиальную сложность в зависимости от числа вершин графа.

ссылка

отвечен 28 Июн '17 15:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×548
×242

задан
28 Июн '17 11:57

показан
544 раза

обновлен
28 Июн '17 15:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru