.
Приклад.
Лекція 16, 17
Програмування на мережах
Запитання:
1. Основні поняття теорії графів. p>. Матричне завдання графів. Впорядкування вершин. p>. Мережі і потоки на мережах. Постановка задачі про максимальний потік. p>. Поняття розрізу. Теорема Форда-Фалкерсона. Алгоритм розв'язання задачі про максимальний потік. p>. Елементи мережевого планування. br/>
1. Основні поняття теорії графів
Теорія графів - область дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів.
Основним об'єктом є граф і його обощения. Синонімами графа є карта, діаграма, мережа, лабіринт. p> Результати та методи теорії графів використовуються у фізиці, хімії, електротехніки, біології, економіці, соціології тощо В економіці методи теорії графів застосовуються при вирішенні транспортних задач про перевезеннях, завдань про призначення, в календарному і мережевому плануванні, при моделюванні складних технологічних процесів, у вирішенні завдань масового обслуговування і завдань управління динамічними процесами і т.п.
Формально граф визначається завданням двох (кінцевих) дискретних множин: безліччю вершин Х = {х1, ..., хn} і безліччю ліній зв'язку між ними
U = {u1, ..., um}.
Лінії зв'язку ui називають ребрами, якщо не вказана їх орієнтація, і - дугами, якщо задано напрямок зв'язку.
Граф з дугами називають орієнтованим графом (орграфом), - з ребрами - неорієнтованим.
Приклад. а) орграф б) неорієнтовані граф
Вершини х i і хj, пов'язані дугою/ребром uk, називають кінцевими вершинами цієї дуги/ребра. Якщо кінцеві вершини збігаються, то дуга/ребро називається петлею. Дуги/ребра з однаковими кінцевими вершинами називаються паралельними. Граф без петель і паралельних ліній зв'язку називають простим. p> Кінцеві вершини хi і хj однієї дуги/ребра або дуги up і uq із загальною вершиною називають суміжними.
Якщо вершина хi є кінцевий для дуги/ребра uk, то ці xi і uk інцидентні: вершина хi інцидентна дузі/ребру uk, а дуга/ребро uk - вершині хi.
Т.ч., суміжність - відношення пов'язаності між однорідними елементами (вершинами або дугами/ребрами), а инцидентность - між різнорідними (вершинами і дугами/ребрами).
Вершина, яка не має відносин суміжності, називається ізлірованной.
Графи з однаковим ставленням інцидентності називаються ізоморфними.
Приклад.
Ізоморфні графи відрізняються тільки геометричною конфігурацією.
Число дуг/ребер, інцидентних вершині хi, називають ступенем цієї вершини P (xi). У орграфе розрізняють полустепені заходу P + (xi) і полустепені результату P-(xi) вершини хi, рівні відповідно числу заходять у хi і виходять з хi дуг. P + (xi) + P-(xi) = P (xi). p> У ряді випадків дуг ставляться у відповідність числові характеристики (довжина шляху, час зміни станів, пропускна здатність зв'язку тощо), звані вагою дуг/ребер, а графи з такими числами називають зваженими.
Граф називають простим, якщо він не містить петель і паралельних дуг/ребер. Простий граф, в якому кожна пара вершин суміжна, називають повним. p> Шлях у орграфе - послідовність неповторюваних дуг, в якій кінець кожної попередньої дуги збігається з початком наступної. Шлях, що проходить через усі вершини тільки по одному разу, називається гамільтоновим. Шлях, що містить всі дуги тільки по одному разу, називають ейлеровим. Кінцевий шлях, у якого початкова вершина збігається з кінцевою, називають контуром. У неорієнтованому графі шлях називають ланцюгом, а контур - циклом. p> Орграф (неорієнтовані граф) називають зв'язковим, якщо будь-які дві його вершини можна з'єднати шляхом (ланцюгом). В іншому випадку - незв'язним. Зв'язний орграф називають сильно зв'язковим, якщо для будь-яких двох вершин хi і хj існують шляхи з хi в хj і з хj в хi. p> Приклад.
2. Матричне завдання графа. Впорядкування вершин
При великому числі вершин і дуг/ребер зображення графа втрачає наочність. У цих випадках для завдання графів і роботи з ними використовують матриці. p>. Граф без петель, що має n вершин і m дуг/ребер можна задати матрицею інціденцій , рядки якої відповідають вершинам, а стовпці - дуг. Елементи матриці, розмірності nm, визначаються за формулою
+1, якщо дуга uj входить у вершину xi,
В
Для неорієнтованого графа замість -1 ставиться 1.
Приклад.
. Граф можна матрицею суміжності вершин , рядки і стовпці якої відповідають вершинам графа. Елементи матриці Sij рівні числу дуг/ребер, що йдуть із хi в хj. Матриця суміжності для неорієнтованого графа буде симетричною. p> Приклад.
Аналогічно може бути задана матриця суміжності дуг/ребер. p> Розрахунки в задачах, пов'язаних з графами, помітно спрощують...
