В стране, где 60 городов, некоторые из которых соединены дорогами, известно, что из столицы выходит 30 дорог. Также известно, что если между городами А и Б есть дорога, и между городами Б и В, то между городами А и В тоже должна быть дорога. Какое максимальное количество дорог может быть в этой стране?
Математика 11 класс Теория графов
Давайте разберемся с задачей шаг за шагом.
У нас есть 60 городов, и известно, что из столицы (обозначим ее как город 1) выходит 30 дорог. Это означает, что столица соединена с 30 другими городами.
Далее, нам дано условие, что если между городами А и Б есть дорога, и между городами Б и В, то между городами А и В тоже должна быть дорога. Это свойство говорит о том, что города образуют комплекс (или клику), где все города связаны друг с другом.
Таким образом, если мы обозначим города, с которыми соединена столица, как C1, C2, ..., C30, то между любыми двумя городами из этой группы также должна быть дорога. Это значит, что между всеми 30 городами, соединёнными со столицей, будут дороги.
Теперь давайте посчитаем количество дорог между этими 30 городами:
Теперь добавим количество дорог, которые выходят из столицы. У нас 30 дорог, соединяющих столицу с другими городами:
Таким образом, максимальное количество дорог, которое может быть в этой стране, равно 465.