КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Декартіво добуток графів
Перетин графів Граф G (X, F) називається перетином графів G1 (X1, F1) і G2 (X2, F2) та позначається G = G1 ∩ G2, якщо X = X1 ∩ X2; F = F1 ∩ F2. Граф G (X, F) називається декартовим, або прямим добутком графів G1 (X1, F1) і G2 (X2, F2), якщо X = X1 ´ X2; F = F1 ´ F2. Для побудови нового графа, що є об'єднанням, перетином або декартовим добутком вихідних графів, необхідно вивчити означення основних операцій і застосувати їх до конкретних графів. Приклад 10. 1. Знайти граф G (X, F), що є об'єднанням графів G1 (X1, F1) і G2 (X2, F2 G1 (X1, F1) G2 (X2, F2)
Рисунок 9. Вихідні графи. X1 = { x1, x2, x3 }; X2 = { x1, x2 }; F (x1) = { x2 }; F2 (x1) = { x1 }; F (x2) = F (x3) = { x1, x2 }; F2 (x2) = { x1, x2 }. Знаходимо, що X = X1 U X2 = { x1, x2, x3 }; F = F1 U F2; F (x1) = F (x2) = F (x3)={ x1, x2 }. Геометричне зображення графа G (X, F): Рисунок 10. Об'єднання графів G1 і G2
2. Знайти граф G (X, F), що є перетином графів G1 (X1, F1) і G2 (X2, F2), розглянутих вище. Одержуємо X = X1 ∩ X2 = { x1, x2 }; F = F1 ∩ F2; F (x1) = Æ; F (x2) = { x1, x2 }. Геометричне зображення графа G:
Рисунок 11. Перетин графів G1 (X1, F1) і G2 (X2, F2) Лекція 13. ЗАДАЧА ПРО МАКСИМАЛЬНИЙ ПОТІК Однією із найбільш важливих задач теорії графів є задача визначення максимального потоку, що протікає від деякої вершини графа S (джерела) до деякої кінцевої вершини t (стоку). При цьому кожній дузі (xi, xj) графа G приписана деяка пропускна спроможність qij, вона визначає найбільше значення потоку, що може протікати по даній дузі. Розглянемо граф G (Х, F) із пропускними спроможностями дуг qij, джерелом S і стоком t; S, t Î X. Множини чисел x ij, визначених на дугах (хi, хj) Î F називаються потоками в дугах, якщо виконуються такі умови: (1) і x ij £ qij для всіх (xi, xj) Î F. Рівняння (1) є рівнянням зберігання потоку. Воно підтверджує, що потік, що втікає у вершину, дорівнює, потокові, що випливає з вершини, за винятком джерела S і стоку t. Співвідношення (2) вказує на те, що пропускні спроможності обмежені для кожної дуги графа G. Задача полягає в знаходженні множин потоків по дугах, щоб величина (2) була максимальною. Ця задача та її варіанти можуть виникати в багатьох практичних застосуваннях. Наведем визначення величини розріза графа. Разобьемо множину X усех верщин графа на дві взаємно дополнюючих підмножини: , () при цьому множина містить вершину S (джерело), а множина - кінцеву вершину t (сток). Множина дуг (), де називают розрізом графа. Теорема о максимальном потіке (Форда-Фалкерсона). Максимальне значення сумарного потіка по дугах дорівнюється минимальной пропускной спроможности розріза. Алгоритм Форда-Фалкерсона Алгоритм Форда-Фалкерсона складається з двох етапів: 1. Розставляння позначок. 2. Збільшення потоку.
Дата добавления: 2015-06-04; Просмотров: 1252; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |