Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Семинар 5. Паросочетания в двудольных графах
Дополнительные главы алгоритмов, часть 2

Что: Семинар
Когда: Пятница, 11 марта 2022, 00:00–01:30
Где: Онлайн, занятие в zoom

Описание

Разбор теоретического задания 3

Задача 1

Ольга Самойлова, Михаил Слабодкин

Задача 2

Лиана Хазалия

Задача 3

Ольга Самойлова

Задача 4

Михаил Слабодкин

Задачи с семинара 5

  1. Что было на лекции?

  2. Дан ациклический орграф. Покройте все его вершины наименьшим числом вершинно непересекающихся путей

  3. а) Дано поле \(n\times m\), вместо некоторых клеток дырки. Нужно поставить наибольшее число ладей на клетки без дырок, чтобы никакие две ладьи не били друг друга. Ладьи бьют сквозь дырки.

    б) Дано поле \(n\times m\), вместо некоторых клеток стенки. Нужно поставить наибольшее число ладей на клетки без стенок, чтобы никакие две ладьи не били друг друга. Ладьи не бьют сквозь стенки.

  4. Дано поле \(n\times m\), вместо некоторых клеток дырки. Нужно поставить наибольшее число доминошек на клетки без дырок, чтобы никакие две доминошки не имели общих внутренних точек.