Ответы Mail.ru
Домашние задания
Русский язык
Литература
Математика
Алгебра
Геометрия
Иностранные языки
Химия
Физика
Биология
История
Обществознание
География
Информатика
Экономика
Другие предметы
Лидеры категории
Лена-пена
М.И.
Y.Nine
•••
Искусственный Интеллект
Искусственный Интеллект
Искусственный Интеллект
1 ответ
Влад Викторов
(2019)
3 дня назад
Решения задач по теории графов
Задача 1
Пусть в стране живёт N рыцарей. Рассмотрим произвольного рыцаря A. У него есть 3 врага, обозначим их B, C и D.
• Рыцари B, C и D попарно дружат: Если бы, например, B и C враждовали, то у рыцаря A был бы друг (B) и его враг (C), с которым A дружит, что противоречит условию.
• У каждого из рыцарей B, C и D, кроме A, есть еще по 2 врага: Всего у каждого рыцаря 3 врага, и один из них - рыцарь A.
Таким образом, мы имеем рыцаря A, его 3 врагов (B, C, D), которые дружат между собой, и у каждого из этих врагов есть еще по 2 врага. Всего получается 1 + 3 + 3*2 = 10 рыцарей.
Ответ: 10
Задача 2
• Оценка сверху: Поскольку с каждого острова ведёт не более 5 мостов, то всего в архипелаге не более N*5/2 мостов (делим на 2, так как каждый мост соединяет два острова). Среди любых 7 островов есть два соединенных мостом, значит, всего мостов не менее N-6 (иначе бы нашлись 7 островов без мостов между собой). Получаем неравенство: N*5/2 >= N-6. Решая его, находим N <= 12.
• Пример: Рассмотрим 12 островов, расположенных по кругу. Соединим каждый остров с пятью следующими за ним по часовой стрелке. Легко проверить, что этот граф удовлетворяет условию задачи.
Ответ: 12
Задача 3
• Связь степени и количества ребер: Сумма степеней всех вершин графа равна удвоенному количеству рёбер. Так как у нас каждая из N вершин имеет степень 4, то всего рёбер 4N / 2 = 2N.
• Оценка на количество вершин: Если подвесить граф за вершину, то на каждом уровне, кроме первого, будет находиться не более чем на 3 вершины больше, чем на предыдущем (так как степень каждой вершины равна 4, и одно ребро уже использовано для соединения с предыдущим уровнем). На первом уровне 1 вершина, на втором - не более 4, на третьем - не более 7, на четвертом - не более 10.
• Пример: Рассмотрим граф-дерево, где каждая вершина, кроме листьев, имеет ровно 4 потомка. В этом случае на четвертом уровне будет 10 вершин.
Ответ: 10
Задача 4
• Максимальное расстояние: Максимальное расстояние между вершинами будет равно 7. Это достигается, например, если граф представляет собой путь из 8 вершин.
• Промежуточные значения: Можно построить графы, в которых максимальное расстояние между вершинами будет равно любому числу от 1 до 7.
Ответ: 1, 2, 3, 4, 5, 6, 7
Задача 1
Пусть в стране живёт N рыцарей. Рассмотрим произвольного рыцаря A. У него есть 3 врага, обозначим их B, C и D.
• Рыцари B, C и D попарно дружат: Если бы, например, B и C враждовали, то у рыцаря A был бы друг (B) и его враг (C), с которым A дружит, что противоречит условию.
• У каждого из рыцарей B, C и D, кроме A, есть еще по 2 врага: Всего у каждого рыцаря 3 врага, и один из них - рыцарь A.
Таким образом, мы имеем рыцаря A, его 3 врагов (B, C, D), которые дружат между собой, и у каждого из этих врагов есть еще по 2 врага. Всего получается 1 + 3 + 3*2 = 10 рыцарей.
Ответ: 10
Задача 2
• Оценка сверху: Поскольку с каждого острова ведёт не более 5 мостов, то всего в архипелаге не более N*5/2 мостов (делим на 2, так как каждый мост соединяет два острова). Среди любых 7 островов есть два соединенных мостом, значит, всего мостов не менее N-6 (иначе бы нашлись 7 островов без мостов между собой). Получаем неравенство: N*5/2 >= N-6. Решая его, находим N <= 12.
• Пример: Рассмотрим 12 островов, расположенных по кругу. Соединим каждый остров с пятью следующими за ним по часовой стрелке. Легко проверить, что этот граф удовлетворяет условию задачи.
Ответ: 12
Задача 3
• Связь степени и количества ребер: Сумма степеней всех вершин графа равна удвоенному количеству рёбер. Так как у нас каждая из N вершин имеет степень 4, то всего рёбер 4N / 2 = 2N.
• Оценка на количество вершин: Если подвесить граф за вершину, то на каждом уровне, кроме первого, будет находиться не более чем на 3 вершины больше, чем на предыдущем (так как степень каждой вершины равна 4, и одно ребро уже использовано для соединения с предыдущим уровнем). На первом уровне 1 вершина, на втором - не более 4, на третьем - не более 7, на четвертом - не более 10.
• Пример: Рассмотрим граф-дерево, где каждая вершина, кроме листьев, имеет ровно 4 потомка. В этом случае на четвертом уровне будет 10 вершин.
Ответ: 10
Задача 4
• Максимальное расстояние: Максимальное расстояние между вершинами будет равно 7. Это достигается, например, если граф представляет собой путь из 8 вершин.
• Промежуточные значения: Можно построить графы, в которых максимальное расстояние между вершинами будет равно любому числу от 1 до 7.
Ответ: 1, 2, 3, 4, 5, 6, 7
Похожие вопросы
Если правильных ответов несколько, введите их все в произвольном порядке
2. Архипелаг состоит из N⩾7 островов. Любые два острова соединены не более чем одним мостом. Известно,что с каждого острова ведёт не более чем 5 мостов, а среди любых 7 островов обязательно есть два, соединённые мостом. Какое наибольшее значение может принимать N?
3.Степени всех вершин связного графа равны 4. Граф подвесили за вершину. Какое наибольшее количество вершин может располагаться на четвёртом уровне?
4.Связный граф подвесили за вершину. Оказалось, что последний уровень имеет номер 4. Расстоянием между вершинами называется длина наименьшего пути, который соединяет эти вершины. Для каждой пары вершин графа посчитаем расстояние между ними и из этих чисел выберем наибольшее. Введите все числа, которые могут получиться.