6.5. Алгоритмы решения некоторых задач теории графов на графах

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

1. В графе выбрать вершину с наименьшей степенью в качестве элемента исходного множества.

2. Удалить выбранную вершину из графа вместе с ее окрестностью (смежные вершины и инцидентные им ребра).

Шаги 1—2 повторять до тех пор, пока множество вершин не станет пустым.

Алгоритм поиска наибольшего паросочетания:

1. Выбираем ребро с наименьшей степенью (число инцидентных вершин) и включаем в искомое паросочетание. Если таковых несколько, выбираем то из них, для которого степень второй граничной вершины наименьшая.

2. Удаляем из графа это ребро и ребра, смежные с ним.

Шаги 1—2 повторять до тех пор, пока множество ребер не станет пустым.

Для решения задачи о нахождении доминирующего множества графа применяется следующий алгоритм:

1. Дополнить матрицу смежности единицами по главной диагонали.

2. Выбрать из матрицы смежности строку с наибольшим числом единиц и ввести ее в искомое покрытие.

3. Вычеркнуть строку из матрицы и столбцы, покрываемые этой строкой.

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

Для решения задачи о наименьшем вершинном покрытии необходимо найти кратчайшее строчное покрытие для матрицы инцидентности по алгоритму:

1. В матрице инцидентности графа отыскивается столбец с наименьшим числом единиц (если таких столбцов несколько, берем самый левый).

2. Среди строк, покрывающих столбец, отыскивается строка с наибольшим числом единиц и включается в искомое покрытие (если таких строк несколько, выбирается самая верхняя).

3. Из матрицы вычеркивается выбранная строка и столбцы, которые она покрывает.

Повторять шаги 1-3 до тех пор, пока в матрице множество столбцов не окажется пустым.

Доминирующее множество ребер, или реберное покрытие - такое множество ребер связного графа, что каждая вершина графа инцидентна хотя бы одному ребру, входящему в доминирующее множество ребер.

Всякое множество одноцветных вершин графа является независимым подмножеством, поэтому задачу о раскраске графа в минимальное количество цветов можно осуществить следующим образом (приближенный алгоритм):

1. Найти все независимые подмножества.

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