КАТЕГОРИИ:


Астрономия- (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) П Архитектура- (3434) Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Война- (14632) Високи технологии- (1363) География- (913) Геология- (1438) Древна литература и фантастика Култура, Изкуство, Култура, Изкуство, Култура, Изкуство, Образование, Наука и Образование, Списания, Художествена литература (373) Култура- (8427) Лингвистика- (374 ) Медицина- (12668 ) Naukovedenie- (506) Образование- (11852) Защита на труда- ( 3308) Педагогика- (5571) P Политика- (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) Олимпиада- (1312) Политика- (7869) Право- (5454) Инструменти- ( 1369) Програмиране- (2801) Производство- (97182) Промишленост- (8706) Психология- (18388) Земеделие- (299) Социология- (6455) Спорт- (42831) Строителство- (4793) Търговия- (5050) Транспорт- (2929) Туризъм- (1568) Физика- (3942) ) Химия- (22929) Екология- (12095) Икономика- (9961) Електроника- (8441) Електротехника- (4623) Енергетика- (12629 )

Потоци в мрежи. Изложение на проблема с максималния поток

Вижте също:
  1. Задачи за планиране на съдържанието и разходите
  2. I. Задачи на статистическото изследване на промените
  3. I. Медицинско и хигиенно обучение, цели, цели, принципи.
  4. I. Основни цели
  5. I. Концепцията и целите на метода за разследване незабавно.
  6. I. КОНЦЕПЦИЯ, ПРЕДМЕТ, ЦЕЛИ И ЗАДАЧИ НА УЧЕБНАТА ДИСЦИПЛИНА. СТРУКТУРА НА УЧЕБНАТА ДИСЦИПЛИНА, ВЗАИМОДЕЙСТВИЕ С ДРУГИ УЧИЛИЩНИ ДИСЦИПЛИНИ.
  7. I. Предмет и цели на курса
  8. I. Предмет, цели, цели, принципи на специалната психология
  9. I. Предмет, цели, цели, принципи на специалната психология
  10. I. Отчитане на разходите в системата за контрол на производствените разходи. Задачата за отчитане на производствените разходи.
  11. I. Цели и цели на урока
  12. II. Основни задачи и функции

Матрични методи за задаване на графики. Поръчване на елементи от дигата

При голям брой елементи графичната схема губи видимост. В този случай графиката се препоръчва да зададете матричния метод. Този метод е удобен и за решаване на проблем на компютър.

Определение 12.3. Матрицата на разпространението на digraph без бримки с n върхове и m arcs е матрица, всеки елемент от който се определя от следната формула:

За ненасочена графика вместо "-1" се поставя "1".

Пример. За дадена ориентирана графика (Фигура 12.10), конструирайте матрица на честотата:

Фиг. 12.10

Матрицата на разпространението на digraph:

,

Определение 12.4. Матрицата на съседство на върховете на digraph е квадратна матрица от n-тия ред ( n е броят на върховете). Редовете и колоните на матрицата съответстват на върховете на графиката. Елементите S ij на матрицата са равни на броя на дъгите, насочени от i- ти връх към j-то .

В случай на неопределена графика, заедно с ръба ( x i , x j ) също принадлежи към ръба ( x j , x i ), така че матрицата ще бъде симетрична.

Пример. За дадена ориентирана графика (Фигура 12.11), конструирайте върхова матрица на съседство:

Фигура 12.11

Матрицата на съседство на върховете на digraph:

,

Определение 12.5. Матрицата на съседство на дъгите на digraph е квадратна матрица от mth ред ( m е броят на дъгите). Редовете и колоните на матрицата съответстват на дъгите на графиката. Елементите q ij са равни на 1, ако дъгата u i непосредствено предхожда дъгата u j , и до нула в останалите случаи.

За неопределена графика съседната матрица на дъгите е симетрична с елементите, равна на 1, ако ръбовете имат общ връх, а 0 в противен случай.

Пример. За дадена ориентирана графика (Фигура 12.12), конструирайте съседната матрица на дъгите:

Ris.12.12

Матрицата на съседство на дигиталните дъги:

,

Изчисленията в проблемите, свързани с графиките, значително се опростяват, ако се поръчат техните елементи.

Определение 12.6. Върхът x i предхожда връх х j, ако има път от x i до x j , тогава x i се нарича предходния връх x j , а x j е следващият x i .

Чрез подреждането на върховете на свързан ортеграф без контури имаме предвид разделянето на върховете му на групи, така че:

1) върховете на първата група нямат предходни и върховете на последната група нямат последващи;

2) върховете на всяка друга група нямат предходни в следващата група;

3) върховете на една и съща група не са свързани с дъги.

В резултат на поръчането на елементите се получава графика, която е изоморфна за тази.

Графичен начин за подреждане на върховете - Fulkerson алгоритъм:

1) Намерете върховете на графиката, които не съдържат дъга. Те образуват първата група.

2) Върховете и дъгите, излъчвани от тях, се изключват от по-нататъшното разглеждане (т.е. заличават се).



3) Задайте следващата група върхове, която не включва дъга. Тази стъпка се повтаря, докато всички върхове бъдат поръчани.

Пример. Сортирайте върховете на digraph (фигура 12.13):

Фиг. 12.13

Ние подреждаме върховете на digraph с Fulkerson алгоритъм (Фигура 12.14):

Фиг. 12.14

Определение 12.7. Мрежата е претеглена окончателна диграфия без цикли и цикли, ориентирани в една обща посока от върха I , който е входът (източникът) на графиката, до върха S , който е изходът (изтичането) на графиката.

За яснота ще си представим, че дадено вещество (товар, ресурс, информация и т.н.) е насочено по дъгите от източник I към потъващия S

Определение 12.8. Максималното количество rjj на вещество, което дъгата може да мине през единица време от върха x i до x j се нарича неговата производителност. В общия случай, rjj ≠ r ji .

Определение 12.9. Количеството x ij на веществото, минаващо през дъгата от върха x i до x j на единица време, се нарича поток по дъгата.

Предполага се, че ако от върха x i до x j е насочен поток с размер x ij , тогава стойността на потока от x j към x i е равна на - x ij , т.е. xjj = -x ij . (12.1)

Предполага се също, че x ii = 0. (12.2)

Определение 12.10. Наборът от X = { x ij } тече по всички дъги на мрежата се нарича поток по мрежата или просто поток.

Потокът по всяка дъга не надвишава неговата носеща способност:

x ij ≤ r ij , (12.3)

Ако x ij <r ij , тогава дъгата между върховете x i и x j се нарича ненаситена .

Общото количество на веществото, изтичащо от източника I, съвпада с общото количество вещество, навлизащо в дренажа S , т.е. силата на потока (12.4)

където j са крайните върхове на дъгите, излъчвани от I ; i - началните върхове на дъгите, включени в S.

Проблемът за максималния поток е формулиран по следния начин: Намерете комплекта X * = { x * ij } потоци x * ij върху всички дъги на мрежата, които отговарят на условията (12.1) - (12.3) и максимизират линейната функция (12.4).

Задачата на максималния поток е намалените задачи: доставка на товари; намиране на най-ниския план за изпълнение на работен пакет за определена продължителност; задачи, свързани с най-икономичното изграждане на енергийни мрежи и др.

<== предишна лекция | следващата лекция ==>
Екстремно дърво графика | Разрезът е в мрежата. Теорема на Фордърсън. Алгоритъм за решаване на проблема с максималния поток

; Дата на добавяне: 2014-01-13 ; ; Виждания: 416 ; Нарушение на авторски права? ;


Вашето мнение е важно за нас! Дали публикуваният материал е полезен? Да | не



ТЪРСЕНЕ ПО САЙТА:


Препоръчителни страници:

Вижте също:



ailback.ru - Edu Doc (2013 - 2018) година. Всички материали, представени на сайта само с цел запознаване с читателите и не извършват търговски цели или нарушаване на авторски права! Последно добавяне на IP: 11.45.9.12
Повторно генериране на страницата: 0.003 сек.