Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

СМРЗДП / Максимальне паропоєднання. Мін верш покр.МОД

.doc
Скачиваний:
6
Добавлен:
05.03.2016
Размер:
460.29 Кб
Скачать

Лекція

Більше ребер, менше вершин

Максимальне паропоєднання. Основні означення.

Підмножина ребер граф називається паропоєднанням, якщо серед них немає інцидентних. Паропоєднання називається максимальним по включенню, якщо воно не є підмножиною паропоєднання з більшим числом ребер. Паропоєднання називається максимальним, якщо воно складається з максимально можливої кількості ребер.

Приклад. Нехай маємо граф n = 8, m = 13.

Підмножина ребер утворює паропоєднання оскільки ці ребра не інцидентні. Але це паропоєднання не є максимальним по включенню: його можна доповнити ng ребром . Отримана підмножина також є паропоєднанням, причому максимальною по включенню, оскільки є інше ребро інцидентне хоча б одному із ребер чи . Хоча максимальне по в включенню, воно не є максимальним. Якщо ми доповнимо не , , і , та отримаємо підмножину не з трьох, а з чотирьох ребер . Це одне з можливих максимальних паропоєднань. Тут розмір і потужність графа невеликі, тому можна перебрати всі варіанти і переконатись, що серед будь-яких п’яти ребер обов’язково будуть інцидентні.

Зведення до задачі цілочисельного лінійного програмування

Розглянемо задачу про знаходження максимального паропоєднання в графі.

Якщо ребра графа зважені, то узагальненням є задача про максимальне зважене паропоєднання. В ній треба знайти паропоєднання максимально можливої ваги.

Прикладом такої задачі є розбиття колективу людей на групи, екіпажі, бригади тощо. Якщо кожне ребро означає можливість сумісної роботи, то отримаємо незважену задачу : створити максимально можливу кількість працездатних бригад. Якщо ж ребра зважені, то зазвичай вага ребра означає продуктивність даної бригади. В цьому випадку формування колективу з максимальною загальною продуктивністю є задачею про максимальне зважене паропоєднання.

Задача про максимальне (зважене) паропоєднання – одне з класичних задач теорії графів.

Введемо в розгляд вектор – стовбець довжиною . Назвемо цей вектор асоційованим з ребрами графа Е, так як кожна координата вектора буде характеризувати відповідне ребро. Якщо ребро в паропоєднання, то асоціативне з ним змінне буде приймати значення 1, а якщо ні, то 0. Тоді загальна кількість ребер, що входить в паропоєднання, може бути записана у вигляді , тут 1 – вектор – стовбець із одиниць потрібної розмірності.

В задачі про максимальне паропоєднання цю величину можна максимізувати при умові, що всі зміни можуть приймати значення тільки 0 або 1:

і серед ребер немає інцидентних.

Останнє означає, що для кожної вершини існує не більше одного ребра, інцидентного їй.

Перейдемо від ребер до асоційованих з ними змінних . Тоді для кожної вершини сума змінних , асоційованих з ребрами, інцидентними з , не перевищує 1. Так для графа

Якщо скористатись матрицею інцидентності, то умову відповідності інцидентних ребер запишемо так: .

Таким чином, маємо задачу цілочисельного лінійного програмування (ЦЛП)

В задачі про максимальне зважене паропоєднання потрібно максимізувати не загальну кількість ребер, а їх сумарну вагу. Позначимо вектор – стовбець ваг ребер С, тоді отримаємо :

У випадку двочастинного графа задача про максимальне зважене паропоєднання, це класична задача про призначення. Тут перша частина вершин V – це робітники; друга W – роботи; ребра – можливість того чи іншого робітника виконати дану роботу. Вага ребра – продуктивність. Потрібно розставити робітників на роботи так, щоб кожну роботу виконував максимум один робітник, кожний робітник виконував максимум одну роботу, а загальна продуктивність була максимальною.

Мінімальна вершина покриття

Основні означення і постановка задачі.

df. Підмножина вершини граф називається вершинним покриттям, якщо вони інцидентні всім ребрам.

Вершинне покриття називається мінімальним по включенню, якщо будь-яке його підмножинне з меншим числом вершин не є вершинним покриттям.

Вершинне покриття називається мінімальним, якщо воно включає мінімально можливу кількість вершин.

Однією з класичних задач теорії графів є знаходження мінімального вершинного покриття.

Якщо вершини зважені, то можна говорити про мінімальне зважене вершинне покриття, коли потрібно мінімізувати загальну вагу вершин при умові, що вони повинні бути інцидент ними всім ребрам.

Приклад 2.

Нехай маємо той же граф, що у попередньому прикладі з n = 8, m = 13.

Множина всіх вершин V, очевидно утворює вершинне покриття, оскільки вони інцидентні всім ребрам. Якщо ми відкинемо вершину , то вершини що залишились також покривають всі ребра.

Але це покриття не є мінімальним по включенню і ми можемо виключити з нього ще й вершину. Підмножина є мінімальним по включенню вершинним покриттям: із нього вже не можна виключити жодної вершини, щоб не оголити яке-небудь

ребро.

Але якщо вилучати з V вершини по-іншому, то можна добитися що не 6, а 5 вершин будуть покривати всі ребра. Одне з можливих мінімальних вершинних покриттів .

Якби не старались, меншою кількістю ребер обійтись не вдасться.

До знаходження мінімального вершинного покриття зводиться, наприклад, військова задача про знищення всіх комунікацій противника, шляхом нанесення мінімальної кількості ударів по його опорним пунктам.

Зведення до задачі ЦЛП

Введемо в розгляд вектор-стовбець V довжиною n. Цей вектор буде асоційованим з вершинами якщо вершина входить в вершинне покриття, то відповідно змінна приймає значення 1, а якщо ні, то 0.

І так координати вектора V – цілочисельні і можуть приймати тільки одне з двох можливих значень: 0 або 1:

Потрібно мінімізувати загальну кількість вершини:

(1)

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

За допомогою матриці інцидентності А ця система запишеться так:

Отримаємо задачу ЦЛП: Мінімізувати цільову функцію (1) при обмеженнях – нерівностях (2).

Задача про мінімальне зважене вершинне покриття відрізняється від (3) тільки коефіцієнтами при цільовій функції: замість одиниць буде вага вершин. Якщо вектор – стовбець ваг вершин позначимо d , то задача про мінімальне зважене вершинне покриття формулюється так:

Максимальне реберне покриття (паропоєднання)

Лекція 4

Задача зводиться до максимізації лінійної функції

А-матриця інцидентності графа, розміром ,

- вектор – стовбець змінних ,

1 – вектор з одиниць потрібної розмірності. В матриці інцидентності А елемент, якщо вершина інцидентна ребруі в протилежному випадку.

Крім того, на змінні накладається умова цілочисельності: ;

Задача про максимальне зважене паропоєднання відрізняється лише цільовою функцією: замість (1) маємо:

(4)

Розроблена функція, яка по заданій структурі графа (і при необхідності, вагах ребер) будує цільову функцію, виду (1) або (4) і обмеженням (2); додатковими умовами цілочисельності (3). Далі розв’язується задача ЦЛП, а результати повертаються в викликаючи програму. Задача ЦЛП розв’язується за допомогою функції milp.m, яку можна переписати з сайта: www.ie.ncsu.edu/kay/matlog/

Заголовок функції : function nMM=MaxMatch (E)

Вхідний параметр Е(m,2) або E(m,3) – список ребер графа і, можливо, їх вага, як в функції PlotGraph. Якщо задано граф з незваженими ребрами, то вважається, що всі ваги – одиничні. Вихідний параметр nMM – список номерів ребер, що входять в максимальне паропоєднання (вектор - стовбець).

Для графа з малюнку (1) розв’язок задачі про максимальне паропоєднання може бути отримано так:

nMM=MaxMatch(E); % розв’язуємо задачу

PlotGraph(V,E(nMM,:),’g’); % маємо ребра

Мал.1 В результаті мал.рабра, що входять в

максимальне зважене паропоєднання

L2.m

Максимальне вершинне покриття

В цій задачі потрібно знайти підмножину вершини мінімальної потужності, які були б інцидент ними всім ребрам графа. Узагальнення – задача про мінімальне зважене вершинне покриття, коли потрібно мінімізувати сумарну вагу вершини, що входить в…

По заданій структурі графа (і при необхідності, вагах вершин) функція MatLab будує цільову функцію виду

Далі з допомогою функції milp.m розв’язується задача ЦЛП, а результати повертаються в викликаючи програму. Заголовок функції

function nMC = MinVerCover(E,d)

Вхідні параметри

  • E(m,2) – список ребер графа, як в функції PlotGraph.

  • D – вага вершин (необов’язковий параметр). Якщо ваги не задані, то вони вважаються одиничними.

Вихідний параметр nMC – список номерів вершин, що входять в мінімальне вершинне покриття. Для графа з мал.1 програма виглядає так:

L2.m

clear all

V = [[0 0];[1 1];[1 0];[1 -1];

[2 1];[2 0];[2 -1];[3 1]

[3 0];[3 -1];[4 0]]; % координати вершини

E = [[1 2 5];[1 3 5];[1 4 5];…

[2 3 2];[3 4 2];[2 5 3];…

[2 6 2];[3 6 5];[3 7 2];…

[4 7 3];[6 5 1];[6 7 1];…

[5 8 5];[6 8 2];[6 9 3];…

[7 9 2];[7 10 3];[8 9 2];…

[9 10 2];[8 11 5];[9 11 4];…

[10 11 4]]; % малюємо граф

Set (get(gef,’CurrentAxes’),…

‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title(‘\bfВихідний граф зі зваженими ребрами’)

_

% звичайна (незважена) задача про максимальне паропоєднання

_

nMM=MaxMatch (E(:,1:2));% розв’язуємо задачу

fprintf (‘кількість ребер в паро поєднанні = % d\n’,length(nMM));

disp (‘В паропоєднання ввійшли ребра з номерами :’);

fprintf(‘%d ’nMM);

fprintf (‘\n загальн а вага = %d\n’, sum (E(nMM,3)));

PlotGraph (V(:,1:2),E(nMM,:),’g’); малюємо

set(get (gef,’CurrentAxes’), ‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title (‘\bfмаксимальне паропоєднання’)

_

% розв’язуємо задачу про максимальне зважене паропоєднання.

_

nMM=MaxMatch(E);% розв’язуємо задачу

fprintf (‘кількість ребер в паро поєднанні = % d\n’,length(nMM));

disp (‘В паропоєднання ввійшли ребра з номерами :’);

fprintf(‘%d ’nMM);

fprintf (‘\n загальн а вага = %d\n’, sum (E(nMM,3)));

PlotGraph (V(:,1:2),E(nMM,:),’g’); малюємо

set(get (gef,’CurrentAxes’), ‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title (‘\bfмаксимальне паропоєднання’)

L2.m (мінімальне вершинне покриття)

clear all

V = [[0 0 2];[1 1 3];[1 0 3];[1 -1 4];…

[2 1 1];[2 0 2];[2 -1 3];[3 1 4];…

[3 0 5];[3 -1 1];[4 0 5]]; % координати вершини їх вага

E = [[1 2 ];[1 3];[1 4];…

[2 3];[3 4] ;[2 5];…

[2 6];[3 6];[3 7];…

[4 7];[6 5];[6 7];…

[5 8];[6 8];[6 9];…

[7 9];[7 10];[8 9];…

[9 10];[8 11];[9 11];…

[10 11]; % ребра

PlotGraph (V,E);

set(get (gef,’CurrentAxes’), ‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title (‘\bfвихідний граф зі зваженими вершинами’)

1) Розв’язуємо незважену задачу.

Друкуємо кількість вершин, їх номери і загальну вагу.

Малюємо вершини, що ввійшли в знайдене мінімальне вершинне покриття

nMC=MinVerCover (E);

fprintf (‘кількість вершин в мінімальному вершинному покритті = % d\n’,length(nMС));

disp (‘В мінімальне вершинне покриття ввійшли вершини з номерами: ’);

fprintf(‘%d ’nMС);

fprintf (‘\n загальн а вага = %d\n’, sum (М(nMС,3)));

PlotGraph (V(nMC));% малюємо

set(get (gef,’CurrentAxes’),…

‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title (‘\bfмінімальне вершинне покриття’)

Мінімальне вершинне покриття

Загальна вага 22

Розв’яжемо зважену задачу задачу

nMC=MinVerCover (E,V(:,3));

fprintf (‘кількість вершин в мінімальному вершинному покритті = % d\n’,length(nMС));

disp (‘В мінімальне зважене вершинне покриття ввійшли вершини’…’ з номерами: ’);

fprintf(‘%d ’nMС);

fprintf (‘\n загальн а вага = %d\n’, sum (V(nMС,3)));

PlotGraph (V(nMC));% малюємо

set(get (gef,’CurrentAxes’),…

‘FontName’,’Times New Roman Cyr’,’FontSize’,10)

title (‘\bfмінімальне pdf;tyt вершинне покриття’)

Загальна вага 21

В першій задачі (незважена задача) – зменшили загальну кількість вершин. В результаті виявилось, що 7 вершин з 11 достатньо, щоб покрити всі ребра.

В другому випадку мінімізувалась сумарна вага вершин, в не їх кількість. В результаті отримали 8 вершин, сумарна вага яких менша, ніж у 7-ми вершин в першому випадку.

Мінімальне основне дерево (зв’язаного графа)

Лекція 5

Приклад 1. Потрібно знайти максимум лінійної функції

на перестановці значень її аргументів x.

, де вектор аргументів - одне з перестановок чисел (2,3,4,5). На які місця в векторі x потрібно поставити числа 2,3,4 і 5, щоб максимізувати функцію z. Застосуємо для розв’язку задачі такий алгоритм:

Бачимо, що коефіцієнт при максимальний: він дорівнює 4. Тому присвоюємо змінній максимальне із даних значень: 5. Наступний по величині коефіцієнт – це 2 при , тому змінній присвоєно максимальне із значень, що залишились: 4. Далі змінній присвоєно значення 3, а - 2. Отримаємо z = 7.

Можна перебрати всі 24 перестановки, і переконатись, що дійсно знайдемо максимальні значення.

Алгоритм, що був застосований для розв’язку цього прикладу називається «скупим». Його загальний принцип такий же простий, як і людська скупість: бери як можна більше з того, що залишилось.

Спробуємо застосувати цей алгоритм у наступному прикладі.

Приклад 2. Задача про максимальне зважене паропоєднання на повному двочастинному графі

G = (V,W,E) з |V| = 3, |W|=4, |E| = 12.

Будемо нумерувати ребра подвійними індексами : парша цифра-номер вершини з V, друга з W.

Таблиця ваг ребер

Скористаємось скупим алгоритмом.

Бачимо, що 1-й робітник краще всього справляється з 1-ю роботою, тому включимо в паропоєднання ребро . Другого робітника посилаємо на 4-ту роботу, оскільки саме на ній його продуктивність максимальна: добавляємо ребро . Тепер у 3-го робітника залишився невеликий вибір: або 2-га або 3-тя роботи з однаковою продуктивністю 6. Виберемо . Таким чином, побудуємо максимальне по включенню зважене паропоєднання з загальною вагою 22. Але цей зв'язок не найкращий. Можна взяти з загальною вагою 23 і це дійсно буде максимальне зважене паропоєднання. Тут скупий алгоритм дав збій: (в першому прикладі скупий алгоритм привів до успіху, а в другому - ні). Відповідь на це запитання дає структура області допустимих значень. В першому прикладі, коли на черговому етапі розв’язку задачі ми забирали одне значення із множини, що залишалась, ми забирали тільки його, а решта залишались недоторканими. В другому ж прикладі, коли на 1-му етапі ми забирали ребро , то ми забирали насправді не тільки його, ми позбавляли себе можливості на наступних етапах забирати всі ребра, інцидентні і ; а саме і , як виявляється, входять в одне із максимальних зважених паропоєднань.

Структури, для яких працює скупий алгоритм, називають в математиці матроїідами. Існує біля півсотні різних означень матроїдів. Одне з них формулюється так: матроїди – це структури, на яких працює скупий алгоритм.

Основне дерево мінімальної ваги

(будемо розглядати графи і мультиграфи)

df1. Шлях – (маршрут) в графі G(V,E) – це послідовність вершин і ребер виду в якій сусідні елементи інцидентні.

df2. Маршрут називається простим, якщо кожна вершина вершина зустрічається в ньому тільки один раз. (В простому маршруті немає перетинів (вершин, що повторюються) і відповідно не може бути ребер, що повторюються).

df3. Граф G(V,E) – називається зв’язним, якщо існує шлях із кожної її вершини в будь -яку іншу.

Розглянемо зв’язний граф (або мультиграф) G. Якщо з нього видалити деякі ребра, він може залишитись зв’язним, а може і розпастись на окремі компоненти. Оскіьки (по максимуму) ребері які можна видалити, щоб граф залишився зв’язним. Якщо задано граф зі зваженими ребрами, то можна поставити задачу так: як по максимуму видалити ребра максимальної ваги, щоб залишився зв’язний граф з загальною мінімальною вагою ребер.

Яка мінімальна кількість ребер потрібна для зв’язності графа з n вершинами.

Теорема1. В зв’язному графіG = (V,E) виконується :. Т.т мінімально можливе число ребер зв’язного графа дорівнює .

Доведення.

При говорити про зв’язність немає сенсу: одну вершину немає з чим зв’язати. Можна сказати, що одна вершина зв’язана сама з собою нульовою кількістю ребер. Дві вершини можна зв’язати одним ребром – і граф стане зв’язним. Третю вершину можна під’єднати з допомогою ще одного, вже другого ребра. За індукцією: нехай теорема справджується для , т.т. граф з к вершинами і ребрами зв’язний. Чергову вершину можна під єднати до нього за допомогою - го ребра. Отримаєм граф з вершинами і ребрами теж буде зв’язним. За індукцією теорема доведена.

Ця теорема показує, скільки (мінімум) ребер потрібно залишити в графі, щоб він залишився зв’язним.

df. Зв’язний граф з вершинами і ребрами називається основним деревом.

Дано граф а) і деякі з його основних дерев б) в)

Якщо зв’язний граф G=(V,E) не є основним деревом, то з нього можна видалити деякі ребра так, що ребра які залишились разом з множиною вершин V утворюють основне дерево .

Доведемо деякі цікаві властивості, якими володіє основне дерево.

df. Шлях називається циклом, якщо в ньому початкова і кінцева вершини співпадають.

df. Цикл називається простим, якщо на шляху, що його визначає, кожна проміжна вершина зустрічається тільки один раз.

Простий цикл, це цикл без самоперетинів. Якщо першу і останню вершини рахувати за одну, то в ньому немає вершин, що повторюються, а значить немає і ребер, що повторюються.

(очевидно і непростого циклу можна виділити, принамні, 2 різних простих цикли, а із непростого маршруту, принаймні 1 простий цикл).

Теорема 2. В основному дереві G=(V,E) зв’язного графа G=(V,E) немає циклів