В графе найти максимальное (по количеству ребер) подмножество попарно несмежных ребер

Тип работы:
Курсовая
Предмет:
Программирование, компьютеры и кибернетика
Страниц:
1

1400 Купить готовую работу
Узнать стоимость

Детальная информация о работе

Содержание

Описание алгоритма перебора для отыскания максимального подмножества попарно несмежных ребер

Подмножество попарно несмежных ребер графа является максимальным, если при добавлении хотя бы одного ребра исходного графа полученное подмножество будет содержать смежные ребра.

Будем строить требуемое максимальное подмножество, добавляя к полученному множеству дополнительные, не принадлежащие ему ребра и выясняя, сохраняется ли условие попарной несмежности ребер.

Сделаем это на примере следующего графа:

Граф состоит из 4 ребер: {1, 3}, {1, 4}, {3, 4}, {2, 4}

Искомое подмножество пока пусто.

Добавляем к искомому подмножеству первое ребро графа {1, 3} и проверяем, что все ребра подмножества попарно несмежны. В случае одного ребра это выполнение этого условия очевидно.

Добавляем второе ребро и проверяем подмножество, состоящее из ребер {1, 3} и {1, 4}. Вновь добавленное ребро нарушает условие несмежных ребер (вершина 1 общая), поэтому удаляем его из искомого подмножества. Полученное на этом шаге подмножество {1, 3}.

Добавляем ребро {3, 4}. Условие несмежных ребер опять нарушено (вершина 3 общая). Удаляем ребро. Полученное на этом шаге подмножество опять состоит из одного ребра {1, 3}.

Добавляем ребро {2, 4}. Ребра {1, 3} и {2, 4}, из которых состоит подмножество, несмежны, поэтому оставляем вновь добавленное ребро. Удаляем ребро. Полученное на этом шаге подмножество опять состоит из одного ребра {1, 3}. Полученное на этом шаге подмножество состоит из двух ребер {1, 3}, {2, 4}.

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

Заполнить форму текущей работой