Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Графы >> Номер 21

[Назад]    [Содержание ]    [Вперед]

  


Номер 21


  Условие: Номер 21


Задача 21. Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань. Помогите Янке расставить многогранники так, чтобы наклейка каждого типа была видна pовно K-1 раз.

  Решение задачи: Номер 21


Решение задачи 21. Можно сформировать граф, состоящий из 2*N вершин, соответствующих К-гранникам и типу наклеек, причем две вершины соединены ребром, если одна соответствует наклейке, а другая - К-граннику, при этом наклейка соответствующего типа находится на соответствующем К-граннике. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим типам наклеек, а другая - всем вершинам, соответствующим К-гранникам, сведем задачу к задаче нахождения максимального потока между этими вершинами.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017