Task 15. Natasha and her six friends want to sit at a round table in such a way that neighbors can speak the same

Милочка

27

a) Для начала построим граф, где вершины представляют собой Наташу и ее шестерых друзей. Для этого задания нам понадобятся следующие данные о языках, которыми они владеют:

- Матеуш: польский, английский и украинский.
- Наташа: русский, английский и польский.
- Ваня: русский, английский и французский.
- Сергей: русский и украинский.
- Герберт: немецкий и английский.
- Маленький Куба: только польский.
- Рената: немецкий и французский.

Теперь построим граф, соединив вершины между собой, если у них есть общий язык, на котором они могут общаться. Ниже представлен граф, соответствующий этим условиям:

\[
\begin{array}{c}
\text{Наташа} \longleftrightarrow \text{Матеуш} \\
\text{Наташа} \longleftrightarrow \text{Сергей} \\
\text{Наташа} \longleftrightarrow \text{Ваня} \\
\text{Наташа} \longleftrightarrow \text{Герберт} \\
\text{Наташа} \longleftrightarrow \text{Маленький Куба} \\
\text{Наташа} \longleftrightarrow \text{Рената} \\
\text{Матеуш} \longleftrightarrow \text{Сергей} \\
\text{Матеуш} \longleftrightarrow \text{Ваня} \\
\text{Матеуш} \longleftrightarrow \text{Герберт} \\
\text{Матеуш} \longleftrightarrow \text{Маленький Куба} \\
\text{Матеуш} \longleftrightarrow \text{Рената} \\
\text{Ваня} \longleftrightarrow \text{Сергей} \\
\text{Ваня} \longleftrightarrow \text{Герберт} \\
\text{Ваня} \longleftrightarrow \text{Маленький Куба} \\
\text{Ваня} \longleftrightarrow \text{Рената}
\end{array}
\]

b) Теперь определим вершины графа, у которых наименьшая степень. Степень вершины - это количество ребер, связанных с данной вершиной. В данном случае нам нужно найти вершины с наименьшим числом ребер.

Матеуш и Сергей имеют наименьшую степень, так как они общаются только с двумя другими вершинами.