2. Графы (2 балла) Дан граф знакомств между шестью друзьями: Аня (А), Боря (Б), Витя (В), Галя (Г), Дима (Д), Елена (Е). Ребро есть, если они знакомы. Ребра: А-Б, А-В, Б-Г, В-Г, В-Д, Г-Е, Д-Е а) Нарисуйте граф. 6) Есть ли путь из А в Е? Если да, запишите любой путь. в) Кто из ребят имеет наибольшую степень вершины (сколько знакомых)?

Решение:

Дано: Друзья: Аня (А), Боря (Б), Витя (В), Галя (Г), Дима (Д), Елена (Е).

Ребра (знакомства): А-Б, А-В, Б-Г, В-Г, В-Д, Г-Е, Д-Е.

а) Рисунок графа:

Представим друзей как вершины, а знакомства как ребра между ними.

б) Путь из А в Е:

Да, путь из А в Е существует. Вот один из возможных вариантов:

• А → В → Г → Е

Другой возможный путь:

• А → Б → Г → Е

Еще один вариант:

• А → В → Д → Е

в) Наибольшая степень вершины:

Степень вершины — это количество ребер, которые к ней присоединены (количество знакомых).

• А: 2 знакомства (с Б, В)
• Б: 2 знакомства (с А, Г)
• В: 3 знакомства (с А, Г, Д)
• Г: 3 знакомства (с Б, В, Е)
• Д: 2 знакомства (с В, Е)
• Е: 2 знакомства (с Г, Д)

Наибольшую степень вершины имеют В и Г, у каждого по 3 знакомых.

Ответ:

• а) Граф нарисован выше.
• б) Путь: А → В → Г → Е (или другие варианты).
• в) Наибольшую степень вершины имеют В и Г (по 3 знакомых).