Бихроматические графы

Сентябрь 13, 2022

Главная
Математика
Бихроматические графы

Содержание

2. Обозначения и определения Х – множество вершин неориентированного графа G(X,U); - «левое» подмножество вершин; - «правое»
3. ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ Подмножество U’ ребер называется паросочетанием, если любые два ребра из него не имеют общей
4. Формальная постановка задачи поиска максимального паросочетания где:
5. САМОСТОЯТЕЛЬНО Выделить на двудольном графе G(X,U) максимальное паросочетание : 1 3 2 1 3 2
6. Задача о назначениях –минимизация затрат Заданы n работ и n рабочих, причем известна стоимость r(i, j)
7. ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ X’ x”
8. Формальная постановка задачи минимизации затрат Примечание: если i-й рабочий не может делать j-ю работу, то r(i,j)=∞
9. Форма представления исходных данных (пример для случая n=3)
10. Алгоритм поиска решения задачи Шаг 1. i = 1 Шаг 2. В i – ой строке
11. Алгоритм поиска решения задачи (продолжение) Шаг 8. j=j+1. Шаг 9. Если j>n, то перейти к Шагу
12. Пример (n=5) 2
13. РЕШИТЬ САМОСТОЯТЕЛЬНО
14. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М: №1 №2
15. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М: №3 №4
16. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М: №5 №6
17. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М: №7 №8
18. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №9 №10
19. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №11 №12
20. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №13 №14
21. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №15 №16
22. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М: №17 №18
23. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №19 №20
24. Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М : №21 №22
26. Скачать презентацию

Слайд 2

Обозначения и определения
Х – множество вершин неориентированного графа G(X,U);
- «левое»

подмножество вершин;
- «правое» подмножество вершин (X’+X”=X);
U – множество ребер графа G(X,U);
r(i,j) – вес ребра
Содержательная постановка задачи о максимальном паросочетании: На множестве ребер U графа G(X,U) выделить подмножество , такое, что:
- существует не более одного ребра, принадлежащего U’ и инцидентного одной вершине подмножества X’;
- существует не более одного ребра принадлежащего U’ и , инцидентного одной вершине подмножества X”;
- мощность множества U’ максимальна.

Слайд 3

ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯ
Подмножество U’ ребер называется паросочетанием, если любые два ребра из

него не имеют общей вершины.

Слайд 4

Формальная постановка задачи поиска максимального паросочетания
где:

Слайд 5

САМОСТОЯТЕЛЬНО
Выделить на двудольном графе G(X,U) максимальное паросочетание :
1
3
2
1
3
2

Слайд 6

Задача о назначениях –минимизация затрат
Заданы n работ и n рабочих, причем

известна стоимость r(i, j) выполнения i-м рабочим j-й работы. Требуется распределить работы между рабочими т.о., чтобы:
1. Все работы были выполнены;
2. Все рабочие были заняты;
3. Суммарные задачи на выполнение всего
цикла работ были минимальны.

Слайд 7

ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ
X’ x”

Слайд 8

Формальная постановка задачи минимизации затрат
Примечание: если i-й рабочий не может делать

j-ю работу, то r(i,j)=∞

Слайд 9

Форма представления исходных данных (пример для случая n=3)

Слайд 10

Алгоритм поиска решения задачи
Шаг 1. i = 1
Шаг 2. В

i – ой строке матрицы М выбирается элемент, вес которого равен Q = min M(i,j) и уменьшаем вес каждого элемента этой строки на Q.
Шаг 3. i = i + 1
Шаг 4. Если i>n, то перейти к Шагу 5, нет к Шагу 2.
Шаг 5. j = 1
Шаг 6. В j –ом столбце матрицы М выбирается элемент, вес которого равен D = min M(i,j).
Шаг 7. Вес каждого элемента j –го столбца уменьшается на величину D.

Слайд 11

Алгоритм поиска решения задачи (продолжение)
Шаг 8. j=j+1.
Шаг 9. Если j>n, то

перейти к Шагу 10, нет - к Шагу 6.
Шаг 10. Нули матрицы вычеркиваются минимальным числом линий L, проводимых по строкам и столбцам матрицы.
Шаг 11. Если L = n, то перейти к Шагу 14, в противном случае – к Шагу 12.
Шаг 12. На множестве неперечеркнутых элементов матрицы М выбирается тот, вес которого минимален и равен W.
Шаг 13. Вес неперечеркнутых элементов матрицы уменьшаем на W, а перечеркнутых дважды – увеличиваем на W. Перейти к Шагу 8.
Шаг 14. Конец алгоритма. На множестве нулей полученной матрицы есть оптимальное назначение.

Слайд 12

Пример (n=5)
2

Слайд 13

РЕШИТЬ САМОСТОЯТЕЛЬНО

Слайд 14

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М:
№1 №2

Слайд 15

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М:
№3

№4

Слайд 16

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М:

№5 №6

Слайд 17

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М:
№7

№8

Слайд 18

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№9

№10

Слайд 19

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№11

№12

Слайд 20

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№13

№14

Слайд 21

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№15

№16

Слайд 22

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М:
№17 №18

Слайд 23

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№19

№20

Слайд 24

Задания к контрольной работе:
Решить задачу о назначениях, заданную матрицей М :
№21

№22

Бихроматические графы

Содержание

Обозначения и определенияХ – множество вершин неориентированного графа G(X,U); - «левое»

ОПРЕДЕЛЕНИЕ ПАРОСОЧЕТАНИЯПодмножество U’ ребер называется паросочетанием, если любые два ребра из

Формальная постановка задачи поиска максимального паросочетаниягде:

САМОСТОЯТЕЛЬНОВыделить на двудольном графе G(X,U) максимальное паросочетание :132132

Задача о назначениях –минимизация затратЗаданы n работ и n рабочих, причем

ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ X’ x”

Формальная постановка задачи минимизации затратПримечание: если i-й рабочий не может делать

Форма представления исходных данных (пример для случая n=3)

Алгоритм поиска решения задачи Шаг 1. i = 1Шаг 2. В

Алгоритм поиска решения задачи (продолжение)Шаг 8. j=j+1.Шаг 9. Если j>n, то

Пример (n=5)2

РЕШИТЬ САМОСТОЯТЕЛЬНО

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М:№1 №2

Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М:№3

Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М:

Задания к контрольной работе: Решить задачу о назначениях, заданную матрицей М:№7

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№9

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№11

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№13

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№15

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М:№17 №18

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№19

Задания к контрольной работе:Решить задачу о назначениях, заданную матрицей М :№21

Похожие презентации