Застосування елементів теорії графів для рішення задачі розміщення пунктів обслуговування

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

Для того, щоб формулювати і розв'язувати задачі про розміщення, необхідно ввести нові поняття теорії графів:

  1. центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої від неї вершини є мінімальною.
  2. головним центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої точки на ребрах графа є мінімальною.
  3. абсолютним центром графа називається будь-яка точка на ребрі, відстань від якої до найвіддаленішої вершини графа є мінімальною.
  4. головним абсолютним центром графа називається будь-яка точка, відстань від якої до найвіддаленішої точки є мінімальною.
  5. медіаною графа називається точка, в якій сума відстаней до усіх вершин графа є мінімальною (аналогічно центрам можна ввести поняття головної, абсолютної і головної абсолютної медіани).

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

Читати повністю

Алгоритм послідовної розмальовки графа

Розглядаючи задачу знаходження хроматичного числа графа (мінімальна кількість кольорів, в які можна розфарбувати його вершини) нами зазначалось, що єдиним підходом для знаходження оптимального рішення задач такого типу є перебір варіантів. До прикладу в параграфі, що міститься за посиланням вище, нами було розглянуто переборний алгоритм, результатом виконання якого є дерево варіантів, обхід якого дозволяє знайти рішення задачі. Але, як видно з прикладу, навіть для графів з мінімальним числом вершин, отримане дерево може бути достатньо громіздким, не кажучи про графи кількість верин яких перевищує число десять і більше. Таким чином, перебрний метод при знаходженні оптимального розв'язку задачі на розфарбування вершин графа вимагає великих обчислювальних затрат і, як правило, застосовується для графів, з достатньо малою кількістю вершин.

Використання алгоритму послідовної розмальовки для розв'язку задачі про розфарбування графа

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

Читати повністю

Розв'язок задачі про найкоротший шлях використовуючи алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда — це алгоритм, який обчислює найкоротші шляхи від однієї вихідної вершини до всіх інших вершин в зваженому орієнтованому графі. Безумовно, він являється повільнішим, ніж алгоритм Дейкстри для тієї ж задачі, але більш універсальний, оскільки здатний обробляти графи, в яких вага деяких ребер приймає від'ємного значення. Алгоритм зазвичай називають на честь двох його розробників, Річарда Беллмана і Лестера Форда, які опублікували його у 1958 та 1956 роках відповідно. Тим не менш, Едвард Форест Мур також опублікував даний алгоритм у 1957 році, і з цієї причини його також іноді називають алгоритмом Беллмана-Форда-Мура.

Різниця в кінцеваому результаті між алгоритмом Беллмана Форда та алгоритмом Дейкстри

Як уже зазначалося вище, алгоритм Беллмана-Форда підходить для роботи з графами, що мають ребра з від'ємною вагою. Однак, якщо граф містить «від'ємний цикл», тобто цикл, сума ваги ребер якого дорівнює від'ємному значенню, тоді, для даного графа, не існує дерева найкоротших шляхів (будь-який шлях такого типу може бути покращений ще одним проходом через ребра, що утворюють від'ємний цикл). В такому випадку алгоритм Беллмана-Форда може виявити цикли від'ємної довжини і повідомити про їх існування, але він не може дати правильну відповідь, тобто знайти найкоротший шлях, якщо від'ємний цикл досяжний з вершини джерела.

Читати повністю

Задача про рюкзак. Математична модель задачі про рюкзак

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

Ілюстрація задачі про ранець

Запишемо математичну модель задачі такого типу. Для цього, припустимо, що розглядається скінченна множина предметів , для кожного з яких відома вартість і визначений об'єм . Також є рюкзак об'ємом . Необхідно упакувати рюкзак таким чином, щоб загальна вартість запакованих предметів була якнайбільшою, а їх загальний об'єм не перевищував величини . Традиційно вважають, що  — цілі невід'ємні числа.

Читати повністю

Переборний алгоритм для розфарбування вершин графа

Розфарбуванням вершин графа називається процес призначення певного кольору кожній з його вершин. Зазвичай кольори — це числа . Тоді, розфарбування є функцією, визначеною на множині вершин графа, яка приймає значення з множини .

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

Розфарбування вершин графа найменшим набором кольорів

У правильному розфарбуванні повного графа , кожна з його вершин повинна бути зафарбована у свій колір, тому хроматичне числа графа такого типу дорівнює кількості його вершин, тобто . Якщо в графі існує повний підграф з вершинами, то для розмальовки цього підграфа необхідно  кольорів. Звідси випливає, що для будь-якого графа виконується нерівність , де  — клікове число графа .

Читати повністю

Перевірка графа на дводольність

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

Дводольний граф

Приклад дводольного графа

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

Читати повністю

Топологічне сортування орієнтованого графа методом видалення вершини-джерела

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

Задача про топологічне сортуванна графа

Топологічне сортування графа методом видалення вершини-джерела

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

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

Читати повністю

Наступна сторінка »