Постройте граф дружбы ребят: Маша дружит с Леной и Настей, Оля дружит с Ксюшей и Олегом, Петя дружит с Ксюшей и Полиной, Дима дружит с Леной и Полиной, Аня дружит с Настей и Олегом, Саша ни с кем не дружит. Является ли граф связным? Сколько в нём компонент связности?

Решение:

Построим граф, где вершины — ребята, а рёбра — дружба.

Вершины: М (Маша), Л (Лена), Н (Настя), О (Оля), К (Ксюша), Ол (Олег), П (Петя), Д (Дима), А (Аня), С (Саша).

Ребра (дружба):

• (М, Л), (М, Н)
• (О, К), (О, Ол)
• (П, К), (П, Д)
• (Д, Л), (Д, П)
• (А, Н), (А, Ол)
• (С) - Саша ни с кем не дружит.

Граф:

Визуально представьте граф: вершины М, Л, Н, Д, П, О, К, Ол, А образуют одну связную часть. Вершина С (Саша) изолирована.

Является ли граф связным?

Нет, граф не является связным, так как существует изолированная вершина (Саша), и из неё нельзя попасть в другие вершины графа.

Сколько в нём компонент связности?

Компонента связности — это максимальный связный подграф. В данном случае у нас:

• Одна большая связная часть, включающая всех, кроме Саши.
• Одна изолированная вершина — Саша.

Таким образом, в графе 2 компоненты связности.

Ответ: Нет, 2