Графы, 2 часть, 6 класс

«Графы в решении логических задач»

Условие задачи №1

Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз ,

участвуют семь школьников.

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

Пригласить старшеклассников для показа. Лена Павловна им торжественно вручает: ватман, ручку, клей, кружки и серпантин

Требуется определить:

с кем сыграл Леша.

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

С кем сыграл Леша?

Для решения задачи будем использовать геометрическое представление графа

Для каждой точки укажем ее имя (по первой букве имени игрока)

и количество партий, сыгранные этим игроком

Изобразим участников турнира точками

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Ж еня (1)

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины

С емен (2)

Эти точки называются вершинами графа

И лья (2)

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

С кем сыграл Леша?

Начать построение ребер следует с вершины В,

так как это единственная вершина,

которая соединяется со всеми другими вершинами графа

Будем строить ребра графа с учетом степеней вершин

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Ж еня (1)

Первые выводы:

Для вершин В и Ж построены все возможные ребра

С емен (2)

И лья (2)

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

С кем сыграл Леша?

Теперь однозначно определяются ребра вершины Т.

С учетом ребра ВТ надо построить четыре ребра

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Ж еня (1)

Новые выводы:

Все возможные ребра теперь построены для вершин Ж, В, Т,

и для вершин С и И

С емен (2)

И лья (2)

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

С кем сыграл Леша?

Теперь становится очевидным, каким должно быть недостающее ребро.

Оно должно соединить вершины Л и Д

Посмотрим и оценим вместе решение-аппликацию…

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Ж еня (1)

Последний вывод

Леша играл с Толей, Ваней и Димой

С емен (2)

И лья (2)

Условие задачи №2

В шахматном турнире по круговой системе, в котором участвуют пять школьников , сыграно шесть партий .

Больше всего встреч к настоящему моменту провели Ваня и Миша – по три .

Какое число партий сыграл участник, проведший наименьшее число встреч ?

В шахматном турнире по круговой системе, в котором участвуют пять школьников , сыграно шесть партий .

Больше всего встреч к настоящему моменту провели Ваня и Миша – по три .

Какое число партий сыграл участник, проведший наименьшее число встреч ?

В данной задаче однозначно построить граф нельзя

Построим граф к данной задаче

В аня (3)

М иша (3)

2 (?)

3 (?)

1 (?)

1 случай

В шахматном турнире по круговой системе, в котором участвуют пять школьников , сыграно шесть партий .

Больше всего встреч к настоящему моменту провели Ваня и Миша – по три .

Какое число партий сыграл участник, проведший наименьшее число встреч ?

Ваня и Миша

не играли

друг с другом

В аня (3)

М иша (3)

2 (?)

3 (?)

1 (?)

2

2

2

В этом случае каждый из остальных участников провел по две встречи

В шахматном турнире по круговой системе участвуют 5 школьников.

Миша и Саша провели по 4 встречи, Костя и Женя – по 3, Ваня – 2.

С кем сыграл Ваня?

М иша (4)

В аня (2)

С аша (4)

Ж еня (3)

К остя (3)

ОТВЕТ. Ваня сыграл с Мишей и Сашей

Задача №1

В шахматном турнире по круговой системе участвуют 6 школьников. Известно, что Кеша сыграл 5 партий, Толя – 4, Семен – 2, Вася -1. Сколько встреч провели еще 2 участника: Андрей и Олег?

К еша (5)

Т оля (4)

С емен (2)

О лег (?)

А ндрей (?)

В ася (1)

ОТВЕТ. 2 встречи, если Олег и Андрей НЕ играли друг с другом; 3 встречи, если совместный матч был

Задача №2

Комбинаторная задача.

У каждого из четырёх друзей есть в лесу свой шалаш. Они решили установить между собой связь с помощью проволочного телефона.

Вопрос: какое наименьшее количество линий из проволоки им придётся провести, чтобы каждый из них мог поговорить с каждым?

Решение:

1

2

3

4

Ответ: им придется провести не меньше шести линий из проволоки.