Блог пользователя izat

Автор izat, 10 лет назад, По-русски

Всем привет. Встретил одну интересную задачу по математике, с какой-то олимпиады, но не смог решить. У кого есть идеи?

Имеется n городов и несколько самолетов. Каждый самолет летает только между двумя городами и между любыми двумя городами летает не более одного самолета. Найти минимальное количество самолетов так, чтобы при любой организации авиарейсов из каждого города можно попасть в любой другой не более чем с одной пересадкой.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Подобная задача было на одном контесте (не помню, как она называется). Если я правильно понял, то минимальное число самолётов — n-1. Идея такая: выберем один из городов в качестве хаба. Из всех остальных городов пустим туда авиарейсы. Таким образом, в любой другой город можно попасть из текущего, совершив не более одной пересадки.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    не более чем с одной пересадкой

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Так и выйдет: путь из каждой вершины до любой другой будет проходить через максимум одну вершину. Картинка для пояснения идеи

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        при любой организации авиарейсов

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Рассмотрим худший случай: Имеется полный граф с n-1 вершинами, количество ребер будет равно (n-1)*(n-2)/2. Ответ будет (n-1)*(n-2)/2+1 для n>=2.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Точно, большое спасибо!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Доказательство: Из этого следует, что каждый город гарантированно соединен с кем-либо. Пусть m-количество ребер, знаем m>=(n-1)*(n-2)/2+1 Допустим есть два города расстояния между ними,которая больше двух. Посчитаем максимальное возможное количество ребер, соединим все вершины кроме этих двух, то есть (n-2)*(n-3)/2. Первая вершина соединена x-вершинами, вторая y-вершинами. И заметим множество вершин x не пересекается со множеством вершин у, то x+y<=n-2. Максимальное количество возможных ребер будет (n-2)*(n-3)/2+x+y<=(n-2)*(n-3)/2+n-2=(n-1)*(n-2)/2-1<(n-1)*(n-2)/2+1<=m, что невозможно. Значит для (n-1)*(n-2)/2+1 ребер не существует вершин, которые отдалены друг от друга больше чем на 2. Ответ меньше не может быть, т.к может существовать вершина не соединенная ни с кем.