Задание 1. 'Друзья в классе'. В классе 6 учеников: Аня, Боря, Вася, Галя, Даша и Егор. Постройте граф и ответьте на вопросы.

Фотография

Ответ ассистента

Для решения задачи воспользуемся теорией графов. Вершины графа — это ученики, а рёбра — связи дружбы между ними. **1. Построение графа** Составим список пар (рёбер) на основе условия: - Аня (А) — Боря (Б), Вася (В) - Боря (Б) — Аня (А), Даша (Д), Егор (Е) - Вася (В) — Аня (А), Галя (Г) - Галя (Г) — Вася (В), Даша (Д) - Даша (Д) — Боря (Б), Галя (Г) - Егор (Е) — Боря (Б) :::div .chart-container @chart-1::: **2. Ответы на вопросы:** - **У кого больше всего друзей в классе?** Степень вершины (количество рёбер, выходящих из неё) определяет количество друзей: $deg(A) = 2$ (Боря, Вася) $deg(B) = 3$ (Аня, Даша, Егор) $deg(V) = 2$ (Аня, Галя) $deg(G) = 2$ (Вася, Даша) $deg(D) = 2$ (Боря, Галя) $deg(E) = 1$ (Боря) **Ответ:** Больше всего друзей у Бори (3 друга). - **Кто дружит только с одним человеком?** Это вершина со степенью 1. **Ответ:** Только с одним человеком (с Борей) дружит Егор. - **Можно ли выделить группу из трех учеников, где каждый дружит с каждым?** В теории графов такая группа называется «клик» размера 3 (треугольник). Проверим циклы из трёх вершин: 1. Аня — Боря — ? (Аня и Боря дружат, но нет третьего общего друга: Аня дружит с Васей, а Боря с Дашей и Егором). 2. Боря — Даша — Галя — Вася — Аня (это один большой цикл). Если проверить все связи, то ни в одной тройке нет полной взаимосвязи «все со всеми». **Ответ:** Нет, такую группу выделить нельзя.

Задать вопрос История вопросов

Другие решения

Что ещё задавали пользователи

Задание 1. 'Друзья в классе'. В классе 6 учеников: Аня, Боря, Вася, Галя, Даша и Егор. Постройте граф и ответьте на вопросы.

Ответ ассистента

Похожие задачи

Другие решения