Задачи решаемые с помощью графов 6 класс

Метод графов. Решение задач методом графов.

Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи.

 Граф – это несколько точек, часть которых соединены друг с другом отрезками или стрелками . Точки называются вершинами графа, а соединяющие линии – рёбрами.

Виды графов

1.Граф-вершина. Элемент (точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же: узел, точка.

2.Граф-ребро. Линия, соединяющая пару смежных вершин графа.

3. Пустой граф. Пустым называется граф без ребер

4. Неориентированный граф. Если ребра не имеют ориентации, граф называется неориентированным.

5. Ориентированный  граф. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Задача № 1 Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).
Сколько всего рукопожатий было сделано?

Неориентированный граф.

Задача № 2

4 человека из нашего класса захотели поздравить друг друга с новым годом. Сделать это решили с помощью SMS-ок. Сколько всего SMS-ок было отправлено? (12)

Задача № 3 Любители мультфильмов:

Рассмотрим множество людей: мама, папа, сын и множество мультфильмов «Ну, погоди!», «Покемоны», «Том и Джерри». Обозначим элементы этих двух множеств точками

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

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

Теперь мы установили, что папа любит мультфильм «Ну, погоди!», сын – «Покемоны». В обеих множествах остается только по одной точке, следовательно мама любит мультфильм «Том и Джерри». Задача решена. 
Таким же способом можно находить соответствие между тремя множествами. Тогда при решении мы можем получить треугольники трех видов:
а) все стороны являются сплошными отрезками (решение задачи);
б) одна сторона – сплошной отрезок, а две другие – штриховые;
в) все стороны – штриховые отрезки.
Таким образом, нельзя получить треугольник, у которого бы две стороны были сплошными отрезками, а третья – штриховой отрезок.
Следующая страница