Контрольные задания > Задание 1. "Друзья в классе" классе 6 учеников: Аня, Боря, Вася, Галя, Даша и Егор. Известно, что: • Аня дружит с Борей и Васей. • Боря дружит с Аней, Дашей и Егором. • Вася дружит с Аней и Галей. • Галя дружит с Васей и Дашей. • Даша дружит с Борей и Галей. • Егор дружит с Борей. 1. Постройте граф: Обозначьте каждого ученика вершиной графа. Соедините две вершины ребром, если соответствующие ученики дружат друг с другом. 2. Ответьте на вопросы: • У кого больше всего друзей в классе? (Определите по степени вершины). • Кто дружит только с одним человеком? • Можно ли выделить группу из трех учеников, где каждый дружит с каждым? (Покажите эту группу на графе, если она существует).
Вопрос:

Задание 1. "Друзья в классе" классе 6 учеников: Аня, Боря, Вася, Галя, Даша и Егор. Известно, что: • Аня дружит с Борей и Васей. • Боря дружит с Аней, Дашей и Егором. • Вася дружит с Аней и Галей. • Галя дружит с Васей и Дашей. • Даша дружит с Борей и Галей. • Егор дружит с Борей. 1. Постройте граф: Обозначьте каждого ученика вершиной графа. Соедините две вершины ребром, если соответствующие ученики дружат друг с другом. 2. Ответьте на вопросы: • У кого больше всего друзей в классе? (Определите по степени вершины). • Кто дружит только с одним человеком? • Можно ли выделить группу из трех учеников, где каждый дружит с каждым? (Покажите эту группу на графе, если она существует).

Смотреть решения всех заданий с листа

Ответ:

1. Построение графа дружбы


Граф будет состоять из 6 вершин, представляющих учеников: Аня, Боря, Вася, Галя, Даша, Егор. Ребро между двумя вершинами означает, что соответствующие ученики дружат.


Список рёбер (дружба):



  • Аня - Боря

  • Аня - Вася

  • Боря - Аня

  • Боря - Даша

  • Боря - Егор

  • Вася - Аня

  • Вася - Галя

  • Галя - Вася

  • Галя - Даша

  • Даша - Боря

  • Даша - Галя

  • Егор - Боря


Графическое представление (можно нарисовать):


Представьте 6 точек (вершин) с именами. Соедините их линиями (рёбрами) согласно списку выше.



2. Ответы на вопросы



• У кого больше всего друзей в классе?


Определим степень каждой вершины (количество друзей):



  • Аня: 2 друга (Боря, Вася)

  • Боря: 3 друга (Аня, Даша, Егор)

  • Вася: 2 друга (Аня, Галя)

  • Галя: 2 друга (Вася, Даша)

  • Даша: 3 друга (Боря, Галя)

  • Егор: 1 друг (Боря)


Ответ: Больше всего друзей у Бори и Даши (по 3 друга).



• Кто дружит только с одним человеком?


Исходя из степеней вершин:



  • Егор имеет степень 1.


Ответ: Егор дружит только с одним человеком (с Борей).



• Можно ли выделить группу из трех учеников, где каждый дружит с каждым?


Ищем так называемый 'клику' размера 3 (треугольник на графе).



  • Рассмотрим пару Боря-Даша (они дружат). Кто из их друзей дружит с обоими?

  • Аня дружит с Борей, но с Дашей не дружит.

  • Егор дружит с Борей, но с Дашей не дружит.

  • Галя дружит с Дашей, но с Борей не дружит.


Других групп из трёх, где все дружат со всеми, не находится. Например, Аня-Боря-Вася: Аня дружит с Борей и Васей, Боря дружит с Аней, Вася дружит с Аней. Но Боря и Вася не дружат.


Ответ: Нет, такую группу выделить нельзя.

ГДЗ по фото 📸