Задача 15. Наташа и шесть её друзей хотят сесть за круглый стол так, чтобы соседимогли говорить на одном языке. Матеуш говорит по-польски, по-английски и по-украински. Наташа – по-русски, по-английски и по-польски. Ваня по-русски, по-английски и по французски. Сергей — по-русски и по-украински. Герберт по-немецки и по-английски. Маленький Куба — только по-польски. Рената – по-немецки и по-французски. а) Постройте граф, в котором Наташа и её друзья были бы вершинами, а ребра соответствовализнанию общего языка.

б) Какие вершины в этом графе имеют наименьшую степень?

в) Какие вершины в этом графе имеют наибольшую степень?

г) Сколько есть всем семерым сесть за круглый стол так, чтобы соседи могли говорить на одном языке?​

а) Чтобы построить граф, в котором вершины соответствуют Наташе и её друзьям, а ребра - общим языкам, нужно проследить, какие языки знают каждый человек.

Матеуш знает польский, английский и украинский. Значит, его вершина будет соединена с вершинами Наташи (русский, английский, польский), Вани (русский, английский), Сергея (русский, украинский) и Герберта (немецкий, английский).

Наташа знает русский, английский и польский. Значит, её вершина будет соединена с вершинами Матеуша (польский, английский, украинский), Вани (русский, английский) и Герберта (немецкий, английский).

Ваня знает русский, английский и французский. Значит, его вершина будет соединена с вершинами Наташи (русский, английский, польский) и Герберта (немецкий, английский).

Сергей знает русский и украинский. Значит, его вершина будет соединена с вершинами Матеуша (польский, английский, украинский) и Ренаты (немецкий, французский).

Герберт знает немецкий и английский. Значит, его вершина будет соединена с вершинами Матеуша (польский, английский, украинский), Наташи (русский, английский, польский) и Вани (русский, английский).

Маленький Куба знает только польский. Значит, его вершина будет соединена только с вершиной Наташи (русский, английский, польский).

Рената знает немецкий и французский. Значит, её вершина будет соединена с вершинами Вани (русский, английский, французский) и Сергея (русский, украинский).

Таким образом, получается следующий граф:

Матеуш
/ | \
/ | \
(3) (3) (2)
/ | \
/ | \
Наташа------Ваня------Герберт
| |
|(3) | (3)
| |
| |
Маленький Куба
|
|
|
Рената
|
|
|
Сергей

б) Чтобы определить вершины с наименьшей степенью, нужно посчитать, с каким количеством вершин каждая вершина соединена. Из графа видно, что вершины Маленький Куба и Рената соединены только с одной вершиной. Значит, у них наименьшая степень.

в) Чтобы определить вершины с наибольшей степенью, нужно также посчитать, с каким количеством вершин каждая вершина соединена. Из графа видно, что вершины Наташа, Матеуш, Ваня и Герберт соединены с тремя вершинами. Значит, у них наибольшая степень.

г) Чтобы узнать, сколько всего семерым сесть за круглый стол так, чтобы соседи могли говорить на одном языке, нужно ответить на вопрос: сколько вершин имеет граф? В данном случае, в графе 7 вершин, так как каждая вершина соответствует одному человеку. Получается, что всего могут сесть за круглый стол 7 человек.