Задача 15. Наташа и шесть её друзей хотят сесть за круглый стол так, чтобы соседимогли говорить на одном языке. Матеуш говорит по-польски, по-английски и по-украински. Наташа – по-русски, по-английски и по-польски. Ваня по-русски, по-английски и по французски. Сергей — по-русски и по-украински. Герберт по-немецки и по-английски. Маленький Куба — только по-польски. Рената – по-немецки и по-французски. а) Постройте граф, в котором Наташа и её друзья были бы вершинами, а ребра соответствовализнанию общего языка.
б) Какие вершины в этом графе имеют наименьшую степень?
в) Какие вершины в этом графе имеют наибольшую степень?
г) Сколько есть всем семерым сесть за круглый стол так, чтобы соседи могли говорить на одном языке?
Матеуш знает польский, английский и украинский. Значит, его вершина будет соединена с вершинами Наташи (русский, английский, польский), Вани (русский, английский), Сергея (русский, украинский) и Герберта (немецкий, английский).
Наташа знает русский, английский и польский. Значит, её вершина будет соединена с вершинами Матеуша (польский, английский, украинский), Вани (русский, английский) и Герберта (немецкий, английский).
Ваня знает русский, английский и французский. Значит, его вершина будет соединена с вершинами Наташи (русский, английский, польский) и Герберта (немецкий, английский).
Сергей знает русский и украинский. Значит, его вершина будет соединена с вершинами Матеуша (польский, английский, украинский) и Ренаты (немецкий, французский).
Герберт знает немецкий и английский. Значит, его вершина будет соединена с вершинами Матеуша (польский, английский, украинский), Наташи (русский, английский, польский) и Вани (русский, английский).
Маленький Куба знает только польский. Значит, его вершина будет соединена только с вершиной Наташи (русский, английский, польский).
Рената знает немецкий и французский. Значит, её вершина будет соединена с вершинами Вани (русский, английский, французский) и Сергея (русский, украинский).
Таким образом, получается следующий граф:
Матеуш
/ | \
/ | \
(3) (3) (2)
/ | \
/ | \
Наташа------Ваня------Герберт
| |
|(3) | (3)
| |
| |
Маленький Куба
|
|
|
Рената
|
|
|
Сергей
б) Чтобы определить вершины с наименьшей степенью, нужно посчитать, с каким количеством вершин каждая вершина соединена. Из графа видно, что вершины Маленький Куба и Рената соединены только с одной вершиной. Значит, у них наименьшая степень.
в) Чтобы определить вершины с наибольшей степенью, нужно также посчитать, с каким количеством вершин каждая вершина соединена. Из графа видно, что вершины Наташа, Матеуш, Ваня и Герберт соединены с тремя вершинами. Значит, у них наибольшая степень.
г) Чтобы узнать, сколько всего семерым сесть за круглый стол так, чтобы соседи могли говорить на одном языке, нужно ответить на вопрос: сколько вершин имеет граф? В данном случае, в графе 7 вершин, так как каждая вершина соответствует одному человеку. Получается, что всего могут сесть за круглый стол 7 человек.