Вход


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

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

  


Номер 6


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


Задача 6. N шестеpенок пpонумеpованы от 1 до N (N<=10). Заданы M (0<=M<=45) соединений паp шестеpенoк в виде (i,j), 1<=i<j<=N (шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть шестеpню с номеpом 1? Если да, то найти количество шестеpен, пpишедших в движение. Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен ( если такой набоp не один, то любой из них ) и количество шестеpен, пpишедших в движение.

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


Решение задачи 6. Будем обозначать вращение по часовой стрелке нулем, против единицей. Сначала припишем шестерне с номером 1 число нуль. На следующем шаге всем шестерням, сцепленным с первой, будут приписаны числа 1 (они будут вращаться в противоположную шестерне 1 сторону). Далее всем шестерням, находящимся в зацеплении с занумерованными на предыдущем шаге, припишем значения 0 и и.т.д. Процесс будем повторять до тех пор, пока либо на очередном шаге ни одной шестерне не будет приписано новое значение, и тогда шестерню с номером 1 удастся повернуть, и число рассмотренных шестеренок и есть искомое число пришедших в движение, либо на каком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1, и тогда система в движение не придет. Перебирая сначала все возможные варианты выбрасывания по одной, затем, в случае неудачи по две, три, ... ,N-1 шестерни и проводя аналогичные рассуждения мы получаем максимальное число шестерен, которое могло бы прийти в движение. О генерации вариантов выбрасывания шестерен см. задачу 2 (перебор).

Назад



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

  


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