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

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

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

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

• Аня - Боря


• Аня - Вася


• Боря - Аня


• Боря - Даша


• Боря - Егор


• Вася - Аня


• Вася - Галя


• Галя - Вася


• Галя - Даша


• Даша - Боря


• Даша - Галя


• Егор - Боря

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

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

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

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

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

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


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


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


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


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


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

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

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

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

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

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

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

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

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


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


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


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

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

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