Решение задачи о минимальном рёберном покрытии

Постановка задачи

Задача о минимальном рёберном покрытии формулируется следующим образом: для заданного неориентированного графа требуется найти такое подмножество E^* рёбер из всего их множества E (E^* Ì E) минимальной мощности, что каждая вершина в графе будет инцидентна по крайней мере одному ребру из подмножества E^*.

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

(7.1)

i = 1,…,m. (7.2)

Здесь x_j – переменные, ассоциированные с рёбрами, при этом x_j = =1, если ребро с номером j входит в минимальное покрытие, и x_j = 0 –в противном случае.

Коэффициенты a_ij – компоненты булевой матрицы инцидентности А размерности m´n – принимают значение 1, если вершина с номером i инцидентна ребру с номером j, и значение 0 – в противном случае.

Выражение (7.2) – ограничение в виде системы линейных неравенств – задаёт условие того, что каждой вершине инцидентно хотя бы одно ребро, т.е. сумма рёбер, инцидентных каждой вершине, не меньше единицы.

Задача о минимальном взвешенном рёберном покрытии отличается только целевой функцией, т.е. вместо выражения (7.1) имеет место

(7.3)

где с_j – вес ребра с номером j.

Формулировка задания

Решить задачу о минимальном взвешенном рёберном покрытии для графа, изображённого на рисунке 5.1. Значения весов рёбер для различных вариантов выполнения задания представлены в таблице.

Номер варианта

Значения весов рёбер

Рисунок 7.1 – Неориентированный граф

Код программы
Файл 3_7_5:

clc

clear

f = [6;8; 9; 10; 11;

7; 12; 9; 6; 7;

8; 10; 11; 7; 5; 9];

 

A = [ 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0;

1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0;

0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0;

0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0;

0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1;

0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0;

0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1;

0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0];

b = ones(8,1);

x = bintprog(f, -A, -b)

y = find(x) % номера ребер

Решение:

x =

 

 

 

y =

 

 

Таким образом, E^* = {1, 6, 9, 15}, т.е. в минимальное рёберное покрытие входят рёбра с номерами 1, 6, 9, 15.

 

 

 

 

 

Задача 8

РЕШЕНИЕ ЗАДАЧИ О МАКСИМАЛЬНОМ НЕЗАВИСИМОМ МНОЖЕСТВЕ ВЕРШИН

Постановка задачи

Задача о максимальном независимом множестве вершин формулируется следующим образом: для заданного неориентированного графа из всего множества вершин V требуется найти максимальное по величине подмножество V^* (V^*ÌV) попарно несмежных вершин.

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

(8.1)

, j = 1,…,n. (8.2)

Здесь x_i – переменные, ассоциированные с вершинами, при этом x_i = 1, если вершина с номером i входит в максимальное независимое множество вершин, и x_i = 0 – в противном случае.

Коэффициенты a_ij – компоненты булевой матрицы инцидентности А размерности m´n – принимают значение 1, если ребро с номером j инцидентно вершине с номером i, и значение 0 – в противном случае.

Выражение (8.2) – ограничение в виде системы линейных неравенств – задаёт условие того, что каждому ребру сумма инцидентных ему переменных (вершин) не превышает единицы.

Задача о максимальном взвешенном независимом множестве вершин отличается только целевой функцией, т.е. вместо выражения (8.1) имеет место

(8.3)

где с_i – вес вершины с номером i.

Следует отметить, что данная задача является двойственной по отношению к задаче о минимальном рёберном покрытии.

Формулировка задания

Решить задачу о максимальном взвешенном независимом множестве вершин для графа, изображённого на рисунке 6.1. Значения весов вершин для различных вариантов выполнения задания представлены на рисунке.

 

Номер вари-анта	Значения весов вершин

 

 

 

Рисунок 8.1 – Неориентированный граф

Код программы:

Файл 3_8_5:

clc

clear

f = [9; 6; 7; 8; 10; 8; 9; 7; 9];

A = [ 1 1 0 0 0 0 0 0 0;

1 0 1 0 0 0 0 0 0;

1 0 0 1 0 0 0 0 0;

0 1 1 0 0 0 0 0 0;

0 0 1 1 0 0 0 0 0;

0 1 0 1 0 0 0 0 0;

0 0 1 0 1 0 0 0 0;

0 0 0 1 1 0 0 0 0;

0 0 0 1 0 0 0 1 0;

0 0 0 1 0 0 1 0 0;

0 0 0 1 0 1 0 0 0;

0 1 0 0 0 0 1 0 0;

0 1 0 0 0 1 0 0 0;

0 0 0 0 1 0 1 0 0;

0 0 0 0 0 1 1 0 0;

0 0 0 0 1 0 0 1 0;

0 0 0 0 0 0 1 1 0;

0 0 0 0 0 1 0 1 0;

0 0 0 0 0 0 1 0 1;

0 0 0 0 0 1 0 0 1;

0 0 0 0 0 0 0 1 1];

b = ones(21, 1);

x = bintprog(-f,A,b)

y = find(x) % номера вершин

Решение:

 

x =

 

 

 

y =

 

 

Таким образом, V^* = {1, 5, 9}, т.е. в максимальное независимое множество вершин входят вершины с номерами 1, 5, 9.

 

⇐ Предыдущая123

Поделиться:

Воспользуйтесь поиском по сайту: