Паросочетания в двудольных графах. Тема 15

1.

Тема 15
«Паросочетания в
двудольных графах»
«Дискретная математика»
Олейник Татьяна Анатольевна
кафедра ВМ-1

2.

План лекции
1. Алгоритм поиска в ширину в ориентированном графе
2. Понятие паросочетания
3. Задача о наибольшем паросочетании
4. Задача о назначениях
2

3.

План лекции
1. Алгоритм поиска в ширину в ориентированном графе
2. Понятие паросочетания
3. Задача о наибольшем паросочетании
4. Задача о назначениях
3

4.

Поиск в ширину в ориентированном графе
1
2
3
4
Дан орграф