Алгоритми на графах Незалежні та домінуючі безлічі

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Курсова робота
"Алгоритми на графах. Незалежні та домінуючі безлічі"

Введення
Визначимо граф як кінцеве безліч вершин V і набір E невпорядкованих і впорядкованих пар вершин і позначимо G = (V, E). Потужності множин V і E будемо позначати буквами N і M. Невпорядкована пара вершин називається ребром, а впорядкована пара - дугою. Граф, який містить лише ребра, називається неорієнтованим; граф, що містить тільки дуги, - орієнтованим, або орграфамі. Вершини, з'єднані ребром, називаються суміжними. Ребра, що мають спільну вершину, також називаються суміжними. Ребро і будь-яка з його двох вершин називають iнцидентною. Кажуть, що ребро (u, v) з'єднує вершини u і v. Кожен граф можна на площині безліччю точок, відповідних вершин, які з'єднані лініями, відповідними ребрах. У тривимірному просторі будь граф можна уявити таким чином, що лінії (ребра) не будуть перетинатися.
Способи опису. Вибір відповідної структури даних для представлення графа має принципове значення при розробці ефективних алгоритмів. При вирішенні завдань використовуються наступні чотири основних способи опису графа: матриця інціденцій; матриця суміжності; списки зв'язку та переліки ребер. Ми будемо використовувати тільки два: матрицю суміжності і перелік ребер.
Матриця суміжності - це двовимірний масив розмірності N * N.
A [i, j] =
Для зберігання переліку ребер необхідний двовимірний масив R розмірності M * 2. Рядок масиву описує ребро.

1. Незалежні безлічі
Завдання пошуку підмножин множини вершин V графа G, які відповідають певним умовам, властивостями, виникає досить часто.
Дан неорієнтований граф G = (V, E). Незалежне безліч вершин є безліч вершин графа G, таке, що будь-які дві вершини в ньому не суміжні, тобто ніяка пара вершин не з'єднана ребром. Отже, будь-яка підмножина S, що міститься в V, і таке, що перетинання S з безліччю вершин суміжних з S порожньо, є незалежним безліччю вершин.
Приклад.
Множини вершин (1, 2), (3, 4, 5), (4, 7), (5, 6) - незалежні. Незалежне безліч називається максимальним, коли немає іншого незалежного множини, в яке воно б входило. Якщо Q є сімейством всіх незалежних множин графа G, то число
a [G] = max ½ S ½
SÎQ
називається числом незалежності графа G, а множина S *, на якому цей максимум досягається, називається найбільшим незалежним безліччю. Для нашого прикладу a [G] = 3, а S * є (3, 4, 5).
Поняття, протилежне максимальному незалежного безлічі, є максимальний повний підграф (кліка). У максимальному незалежному безлічі немає суміжних вершин, в кліці всі вершини попарно суміжні. Максимальна незалежна множина графа G відповідає кліці графа G ', де G' - доповнення графа G.
Для нашого прикладу додаток G 'наведено на наступному малюнку, кліка графа G' відповідає максимальному незалежного безлічі графа G. Число незалежності графа G 'дорівнює 4, максимальне незалежна множина (2, 5, 7, 8), йому відповідає кліка графа G.

2. Метод генерації всіх максимальних незалежних множин графа

Завдання вирішується перебором варіантів. «Родзинкою» є відсутність необхідності запам'ятовувати генеруються множини з метою перевірки їх на максимально шляхом порівняння з раніше сформованими множинами. Ідея полягає в послідовному розширенні поточного незалежного безлічі (k - номер кроку або номер ітерації в процесі побудови). Очевидно, що якщо ми не можемо розширити поточне рішення, то знайдено максимальне незалежна множина. Виведемо його і продовжимо процес пошуку. Будемо зберігати поточне рішення в масиві Ss (Ss: array [1 .. N] of integer), його перші k елементів визначають поточне рішення. Логіка виведення.
procedure Print (k: integer);
var i: byte;
begin
writeln; for i: = 1 to k do write (Ss [i], '');
end;
У процесі рішення нам доведеться багаторазово розглядати вершини графа, суміжні з даною. При описі графа матрицею суміжності - це перегляд відповідного рядка, при описі списками зв'язку - перегляд списку. Спростимо знаходження суміжних вершин за рахунок використання нового способу опису графа. Використовуємо множинний тип даних. Введемо тип даних:
type Sset = set of 1 .. N; і змінну
var A: array [1 .. N] of Sset;.
Отже, щоб визначити вершини графа, суміжні з вершиною i, необхідно просто викликати відповідний елемент масиву A.
Приклад.
Основна складність алгоритму у виборі чергової вершини графа. Введемо змінну Gg для зберігання номерів вершин - кандидатів на розширення поточного рішення. Значення змінної формується на кожному кроці k. Що є вихідною інформацією для формування Gg? Очевидно, що деяке безліч вершин, своє для кожного кроку (ітерації) алгоритму. Логічно правомірно розбити це безліч вершин на не використані раніше (Qp) і використані раніше (Qm). Зміна значень Qp і Qm відбувається при поверненні на вибір k-го елемента максимального незалежного множини. Ми вибирали на k кроці, наприклад, вершину з номером i, і природно виключення її з Qp і Qm при пошуку наступного максимального незалежного множини. Крім того, при переході до кроку з номером (k +1) з поточних множин Qp і Qm для наступного кроку необхідно виключити вершини, суміжні з вершиною i, обраної на даному кроці (з визначення незалежного безлічі) і, певна річ, саму вершину i. Отже, загальна логіка.
procedure Find (k: integer; Qp, Qm: Sset);
var Gg: Sset;
i: byte;
begin
if (Qp = []) and (Qm = []) then begin Print (k); exit end;
{Чорний ящик А}
<Формування безлічі кандидатів Gg для розширення поточного рішення (k елементів у масиві Ss) за значеннями Qp і Qm>;
i: = 1;
while i <= N do begin
if i in Gg then begin
Ss [k]: = i;
Find (k +1, Qp-A [i] - [i], Qm-A [i] - [i]);
{Чорний ящик Б}
<Зміна Qp, Qm для цього рівня (значення k) і, відповідно, зміна безлічі кандидатів Gg>;
end;
Inc (i);
end; {while}
end; {Find}
Продовжимо уточнення логіки. Нам буде потрібно проста функція підрахунку кількості елементів у змінних типу Sset.
function Number (A: Sset): byte;
var i, cnt: byte;
begin
cnt: = 0; for i: = 1 to N do if i in A then Inc (cnt); Number: = cnt;
end;
Використовуємо метод трасування для того, щоб знайти подальшу логіку уточнення рішення. Будемо робити розриви таблиці для внесення пояснень у роботу чорних ящиків.
k
Qp
Qm
Gg
Ss
Примітки
1
[1 .. 5]
[]
[1 .. 5]
(1)
Вибираємо першу вершину
2
[4,5]
[]
[4,5]
(1,4)
Отже, перше уточнення чорного ящика А.
if Qm <> [] then <чорний ящик АА>
else Gg: = Qp;
Його суть у тому, що якщо вибирати з раніше використаних вершин нічого, то безліч кандидатів збігається зі значенням Qp, і далі за логікою ми «тупо» вибираємо першу вершину з Qp. Переходимо до наступного викликом процедури Find.

3
[]
[]
[]
(1,4)
Висновок перший максимального незалежного множини і вихід в попередню копію Find.
2
[5]
[4]
[5]
(1,5)
Виключаємо вершину 4 з Qp і включаємо її в Qm.
Продовжує роботу цикл while процедури Find. Вибираємо наступну вершину - це вершина 5. І викликаємо процедури Find з іншими значеннями параметрів.
3
[]
[]
[]
(1,5)
Висновок другий максимального незалежного множини.
2
[]
[4,5]
[]
Цикл while закінчений, вихід в попередню копію процедури Find.
Уточнення чорного ящика Б. Перше: необхідно виключити вершину i з Qp і включити її в Qm. Друге: слід відкоригувати безліч Gg. Вибір на цьому кроці вершин, не суміжних з i, призведе до генерації повторюваних максимальних незалежних множин, тому слід вибирати вершини з перетину множин Qp і A [i]. Отже, чорний ящик Б.
Qp: = Qp - [i]; Qm: = Qm + [i];
if Number (Qp * A [i]) <Number (Gg) then Gg: = Qp * A [i] &Gg; Наступний крок - вихід у попередню версію Find, при цьому значення k дорівнює 1.
1
[2 .. 5]
[1]
[1 .. 5]
Однак після роботи чорного ящика Б маємо наступні значення змінних
1
[2 .. 5]
[1]
[2 .. 3]
(2)
2
[3,5]
[]
[3,5]
(2,3)
3
[5]
[]
[5]
(2,3,5)
4
[]
[]
[]
Висновок третій максимального незалежного множини.
3
[]
[5]
[]
2
[5]
[3]
[]
Згідно з логікою чорного ящика Б безліч кандидатів Gg стає порожнім.
1
[3 .. 5]
[1,2]
[2,3]
(3)
2
[5]
[2]
Отже, ми перший раз потрапляємо в процедуру Find, і безліч Gm при цьому не порожньо.
Має працювати логіка чорного ящика АА. Зауваження 1. Якщо існує вершина j, що належить Qm, така, що перетин A [j] і Qp порожньо, то подальше побудова максимального незалежного безлічі безглуздо - вершини з A [j] не потраплять до нього. Зауваження 2. Якщо немає вершин з Qm, задовольняють першому зауваженням, то яку вершину з Qp слід вибирати? Відповідь: вершину iÎ (QpÇA [j]) для деякого значення jÎQm, причому потужність перетину множин A [j] і Qp мінімальна. Даний вибір дозволяє скоротити перебір. Отже, логіка чорного ящика АА.
begin
delt: = N +1;
for j: = 1 to N do if j in Qm then if Number (A [j] * Qp) <delt then
begin i: = j; delt: = Number (A [j] * Qp); end;
Gg: = Qp * A [i];
end
Закінчимо трасування прикладу.
2
[5]
[2]
[]
1
[5]
[1,2,3]
[]
Вихід в основну програму.

Ми знайшли всі максимальні незалежні множини.

3. Домінуючі безлічі

Для графа G = (V, E) домінуюче безліч вершин є безліч вершин SÌV, таке, що для кожної вершини j, що не входить в S, існує ребро, що йде з деякою вершини множини S у вершину j. Домінуюче безліч називається мінімальним, якщо немає іншого домінуючого безлічі, що міститься в ньому.
Приклад.
Домінуючі безлічі (1, 2, 3), (4, 5, 6, 7, 8, 9), (1, 2, 3, 8, 9), (1,2, 3, 7) і т.д. Множини (1, 2, 3), (4, 5, 6, 7, 8, 9) є мінімальними. Якщо Q - сімейство всіх мінімальних домінуючих множин графа, то число b [G] = min ½ S ½
SÎQ
називається числом домінування графа, а множина S *, на якому цей мінімум досягається, називається найменшим домінуючим безліччю. Для нашого прикладу b [G] = 3.
Завдання. Нехай місто можна зобразити як квадрат, розділений на 16 районів. Вважається, що опорний пункт міліції, розташований в будь-якому районі, може контролювати не тільки цей район, але і сусідні з ним райони. Потрібно знайти найменшу кількість пунктів міліції і місця їх розміщення, такі, щоб контролювався все місто.
Представимо кожний район вершиною графа і ребрами з'єднаємо тільки ті вершини, які відповідають сусіднім районам. Нам необхідно знайти число домінування графа і хоча б одне найменше домінуюче безліч. Для даної задачі b [G] = 4, і одне з найменших множин є (3, 5, 12, 14). Ці вершини виділені на малюнку.

4. Завдання про найменший покритті

Розглянемо граф. На малюнку показана його матриця суміжності А і транспонована матриця суміжності з одиничними діагональними елементами А *. Задача визначення домінуючого безлічі графа G еквівалентна задачі знаходження такого найменшого безлічі стовпців у
матриці А *, що кожен рядок матриці містить одиницю хоча б в одному з вибраних стовпців. Задачу про пошук найменшого безлічі стовпців, «покриває» всі рядки матриці, називають задачею про найменшому покритті. У загальному випадку матриця не обов'язково є квадратною, крім того, вершинам графа (стовпцям) може бути приписана вага, в цьому випадку необхідно знайти покриття з найменшою загальною вартістю. Якщо введено додаткове обмеження, суть якого в тому, щоб будь-яка пара стовпців не мала загальних одиниць в одних і тих же рядках, то завдання називають задачею про найменшому розбивці.
Зауваження. 1. Якщо деяка рядок матриці А * має одиницю в єдиному стовпці, тобто більше немає стовпців, що містять одиницю в цьому рядку, то даний стовпець слід включати в будь-яке рішення. 2. Розглянемо безліч стовпців матриці А *, що мають одиниці в конкретного рядка. Для нашого прикладу: U 1 = (1, 6, 7, 8), U 2 = (1, 2, 5, 8), U 3 = (2, 3, 5), U 4 = (3, 4), U 5 = (2, 3, 4, 5), U 6 = (5, 6), U 7 = (6, 7), U 8 = (7,8). Бачимо, що U 4 ÌU 5. З цього випливає, що 5-й рядок можна не розглядати, оскільки будь-яка множина стовпців, що покриває 4-й рядок, має покривати і 5-ю. Четвертий рядок домінує над п'ятою.

5. Метод рішення задачі про найменшому розбитті

Спробуємо усвідомити метод рішення задачі, розглядаючи, як зазвичай, приклад. У нас є орієнтований граф, його матриця суміжності і транспонована матриця суміжності з одиничними діагональними елементами. Досліджуємо структуру матриці А *. Нас цікавить, які стовпці містять одиницю в першому рядку, які стовпці містять одиницю в другому рядку і не містять в першій і так далі. З цією метою можна було б переставляти стовпці в матриці А *, але залишимо її «у спокої». Будемо використовувати додаткову матрицю Bl, її тип:
type Pr = array [1 .. MaxN, 1 .. MaxN +1] of integer;
var Bl: Pr;, де MaxN - максимальна розмірність задачі. Чому плюс одиниця (технічний прийом - «бар'єр»), буде ясно з подальшого викладу (процедура Press).
При ініціалізації матриця Bl повинна мати вигляд:
· У першому рядку - [1 2 3. № 0];
· Всі інші елементи дорівнюють нулю.
Тобто наше вихідне припущення полягає в тому, що всі стовпці матриці А * мають одиниці в першому рядку. Перевіримо його. Будемо переглядати елементи чергового рядка (i) матриці Bl. Якщо Bl [i, j] <> 0, то зі значенням Bl [i, j], як номером стовпця матриці A *, перевіримо відповідний елемент А *. При його нерівність нулю елемент Bl залишається на своєму місці, інакше він переписується в наступний рядок матриці Bl, а елементи поточного рядка Bl зсуваються вправо, стискуються (Press). Отже, для N-1 рядка матриці Bl. Для нашого прикладу матриця Bl після цього перетворення буде мати вигляд:
1
3
4
6
0
...
0
2
5
7
0
0
....
0
Bl =
0
0
0
0
0
...
0
... ...
0
0
0
0
0
0

4 3 6 1 0 ... 0
5 Липень 2 0 ... 0
Bl = 0 0
....
0 ... 0
У нашій задачі визначені вартості вершин графа чи вартості стовпців матриці А *, і необхідно знайти розбиття найменшої вартості. Нехай вартості описуються в масиві Price (Price: array [1 .. MaxN] of integer) і для прикладу на малюнку мають значення [15 13 4 3 8 9 10]. Залишилася чисто технічна деталь - відсортувати елементи кожного рядка матриці Bl за зростанням вартості відповідних стовпців матриці А. Логіка формування наведена нижче по тексту (Blocs).
procedure Blocs; {виділення блоків}
{Bl - глобальна змінна}
procedure Sort;
{Price і Bl - глобальні змінні}
begin
...
end;
procedure Press (i, j: integer); {Зрушуємо елементи рядка з номером i, починаючи з позиції (стовпчик) j, на одну позицію вправо}
{Bl - глобальна змінна}
var k: integer;
begin
k: = j;
while Bl [i, k] <> 0 do begin {Тому розмірність матриці з плюс одиницею. В останній колонці рядка завжди записаний 0.}
Bl [i, k]: = Bl [i, k +1];
Inc (k);
end; {while}
end; {Press}
var i, j, cnt: integer;
begin
FillChar (Bl, SizeOf (Bl), 0);
for i: = 1 to N do Bl [1, i]: = i; {передбачається, що в першому блоці всі стовпці}
for i: = 1 to N-1 do begin
j: = 1; cnt: = 0;
while Bl [i, j] <> 0 do begin
if A * [i, Bl [i, j]] = 0 then begin {стовпець не в цьому блоці}
Inc (cnt);
Bl [i +1, cnt]: = Bl [i, j]; {переписати в наступний рядок}
Press (i, j);
Dec (j);
end; {if}
Inc (j);
end; {while}
end; {for}
Sort;
end; {Blocs}
Після цієї роботи ми маємо цілком «пристойну» організацію даних для вирішення задачі шляхом перебору варіантів. Матриця Bl розбита на блоки, і необхідно вибрати по одному елементу (якщо відповідні рядки ще не покриті) з кожного блоку. Процес вибору слід продовжувати до тих пір, поки не будуть включені в «покриття» всі рядки або виявиться, що деяку рядок не можна включити.
Продовжимо розгляд методу. Якщо при пошуку незалежних множин ми йшли «зверху вниз», послідовно уточнюючи логіку, то зараз спробуємо йти «знизу вгору», складаючи остаточне рішення із зроблених «цеглинок». Як звичайно, слід почати зі структур даних. По-перше, ми шукаємо краще рішення, тобто те безліч стовпців, що задовольняє умовам завдання (неперетинання і «покриття» всього безлічі рядків), і сумарна вартість цієї множини мінімальна. Значить, необхідна структура даних для зберігання цієї множини і значення найкращої вартості і, відповідно, структури даних для зберігання поточного (чергового) рішення та його вартості. По-друге, у вирішенні рядок може бути або не бути. Отже, нам потрібно якось фіксувати цю інформацію. Отже, дані.
type Model = array [1 .. MaxN] of boolean;
var Sbetter: Model; Pbetter: integer; {краще рішення}
S: Model; P: integer; {поточне рішення}
R: Model; {R [i] = true - ознака того, що рядок i "покрита" поточним рішенням}
Логіка включення (виключення) стовпця з номером k в рішення (з рішення) має вигляд:
procedure Include (k: integer); {включити стовпець у вирішення}
{A *, R, Price, S, P - глобальні змінні}
var j: integer;
begin
P: = P + Price [k]; {поточна ціна рішення}
S [k]: = true; {стовпець з номером k в рішення}
for j: = 1 to N do
if A * [j, k] = 1 then R [j]: = true; {рядки, «покриті» стовпцем k}
end; {Include}
procedure Exclude (k: integer); {виключити стовпець з рішення}
var j: integer;
begin
p: = p-Price [k];
S [k]: = false;
for j: = 1 to N do if (A * [j, k] = 1) and R [j] then R [j]: = false;
end; {Exclude}
Перевірка, сформовано чи рішення, полягає в тому, щоб проглянути масив R і визначити, чи всі його елементи рівні істини.
function Result: boolean;
var j: integer;
begin
j: = 1;
while (j <= N) and R [j] do Inc (j);
if j = N +1 then Result: = true else Result: = false;
end; {Result}
Крім перерахованих «цеглинок», нам необхідно вміти визначати, чи можна стовпець з номером k включати в рішення. Для цього слід переглянути стовпець з номером k матриці A * і перевірити, чи немає збігів одиничних елементів зі значенням true відповідних елементів масиву R.
function Cross (k: integer): boolean; {перетин стовпця з частковим рішенням, сформованим раніше}
var j: integer;
begin
j: = 1;
while (j <= N) and Not (R [j] and (A * [j, k] = 1)) do Inc (j);
if j = N +1 then Cross: = true else Cross: = false;
end; {Cross}
Заключна логіка пошуку (Find) має в якості параметрів номер блоку (рядки матриці Bl) - мінлива bloc і номер позиції в рядку. Перший виклик - Find (1,1).
procedure Find (bloc, jnd: integer);
{Змінні глобальні}
begin
if Result then begin if P <Pbetter then begin Pbetter: = P;
Sbetter: = S;
end;
end
else if Bl [bloc, jnd] = 0 then exit
else if Cross (Bl [bloc, jnd]) then begin
Include (Bl [bloc, jnd]);
Find (bloc +1,1);
Exclude (Bl [bloc, jnd]);
end
else if R [bloc] then Find (bloc +1,1);
Find (bloc, jnd +1);
end; {Find}
Нам залишилося дати загальну логіку, але після виконаної роботи вона не викликає труднощів.
program R_min;
const MaxN = ...;
type ... var ...
procedure Init; {введення і ініціалізація даних}
begin
...
end;
procedure Print; {висновок результату}
begin
...
end;
{Процедури і функції, розглянуті раніше}
{Основна логіка}
begin
Init;
Blocs;
Find (1,1);
Print;
end.


Висновок

Поняття, протилежне максимальному незалежного безлічі, є максимальний повний підграф (кліка). У максимальному незалежному безлічі немає суміжних вершин, в кліці всі вершини попарно суміжні. Максимальна незалежна множина графа G відповідає кліці графа G ', де G' - доповнення графа G.

Література
1. Адельсон-Бєльський Г.М., Дініц Е.А., Карзанов А.В. Потокові алгоритми. - М.: Наука, 1975.
2. Берж К. Теорія графів та її застосування. - М.: ІЛ, 1962.
3. Емелічев В.А., Мельников О.І., Сарванов В.І., Тишкевич Р.І. Лекції з теорії графів. - М.: Наука, 1990.
4. Зиков А.А. Теорія скінченних графів. - К.: Наука; Сиб. отд-ня, 1969.
5. Йенсен П., Барнес Д. Потокове программірованіе.-М.: Радіо і зв'язок, 1984.
6. Касьянов В.М., Сабельфельд В.К. Збірник завдань з практикуму на ЕОМ. - М.: Наука, 1986.
7. Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978.
8. Кофман А. Вступ у прикладну комбінаторику. - М.: Наука, 1975.
9. Липський В. Комбінаторика для програмістів. - М.: Мир, 1988.
10.Майніка Е. Алгоритми оптимізації на мережах і графах.-М.: Світ, 1981.
11.Нечепуренко М.І., Попков В.К., Майнагашев С.М. та ін Алгоритми і програми вирішення задач на графах і мережах. - К.: Наука; Сиб. отд-ня, 1990.
12.Окулов С.М. Конспекти занять з інформатики (алгоритми на графах). Навчальний посібник для студентів і вчителів шкіл. - Кіров, 1996.
13.Пападімітріу Х., Стайгліц К. Комбінаторна оптимізація: Алгоритми і сложность.-М.: Світ, 1985.
14.Свамі М., Тхуласіраман К. Графи, мережі та алгоритми. - М.: Світ, 1984.
15.Філіпс Д., Гарсіа-Діас А. Методи аналізу мереж. - М.: Світ, 1984.
16.Форд Л.Р., Фалкерсона Д.Р. Потоки в мережах. - М.: Світ, 1963.
17.Френк Г., Фріш І. Мережі, зв'язок і потоки. - М.: Зв'язок, 1978.
18.Харарі Ф. Теорія графів. - М.: Світ, 1973.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
80кб. | скачати


Схожі роботи:
Алгоритми на графах Найкоротші відстані на графах
Динамічне програмування алгоритми на графах
Операції на графах
Які переваги американській економіці дає те що долар займає домінуючі позиції на світовому
Рішення задач на графах
Алгоритми в програмуванні
Допоміжні алгоритми
Алгоритми нейрокібернетики
Алгоритми з многочленами
© Усі права захищені
написати до нас