Бихроматические графы - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Бихроматические графы. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

БИХРОМАТИЧЕСКИЕ ГРАФЫ Лекция 3

Слайд 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) максимальное паросочетание :

Слайд 6

Описание слайда:

Задача о назначениях –минимизация затрат

Слайд 7

Описание слайда:

ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ

Слайд 8

Описание слайда:

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

Слайд 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. Конец алгоритма. На множестве нулей полученной матрицы есть оптимальное назначение.