City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Семинар 5. Паросочетания в двудольных графах
Advanced chapters of algorithms, part 2

What: Seminar
When: Thursday, 10 March 2022, 20:00–21:30
Where: Онлайн, занятие в zoom

Description

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

Задача 1

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

Задача 2

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

Задача 3

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

Задача 4

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

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

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

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

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

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

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