Метод графов. Решение задач методом графов. (материалы для занятий математического кружка в 5 классе)
материал по математике (5 класс) на тему

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

(материалы для занятий математического кружка в 5 классе)

Один из способов решения задач типа «Кто есть кто?» - метод графов. 
Граф – это несколько точек, часть которых соединены друг с другом отрезками или стрелками (в этом случае граф называется ориентированным). 

Другой способ решения таких задач – табличный метод.
Рассмотрим метод графов на примере решения задачи № 1 из предложенных ниже задач.

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

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

Рассмотрим метод графов на примере решения задачи:

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

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

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

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

Задача №2:  Любители музыки:

В клубе «Отдых» познакомились 3 любителя клубной музыки видов техно, хаус, рейв. Один говорит: «Вы какую музыку больше любите? Я техно люблю!». Другой ответил, что любит хаус, а третий сказал, что не любит ни техно, ни хаус, но зато обожает рейв. Интересно то, что все они были в банданах и рубашках черного, белого и желтого цветов, но цвет банданы и рубашки совпадал только у любителя техно. А у любителя хаус ни рубашка, ни бандана не были белыми. А любитель рейв был в желтой рубашке. Определите цвет рубашек и бандан каждого из любителей клубной музыки.

Задача №3: Три поросёнка:

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

Задача №4: Друзья

Встретились три друга - Белов, Серов и Чернов. Чернов сказал другу, одетому в серый костюм: «Интересно, что на одном из нас белый костюм, на другом - серый и на третьем — черный, но на каждом костюм цвета, не соответствующего фамилии». Какой цвет костюма у каждого из друзей?

Задача №5: Подруги:

Когда три подруги — Надя, Валя и Маша — вышли гулять, на них были белое, красное и синее платья. Туфли их были тех же трех цветов, но только у Нади цвета туфель и платья совпадали. При этом у Вали ни платье, ни туфли не были синими, а Маша была в красных туфлях. Определите цвет платьев и туфель каждой из подруг.

Задача №6: Друзья

Встретились трое друзей: Белов, Рыжов и Чернов. Брюнет сказал Белову: "Любопытно, что ни у кого из нас цвет волос не соответствует фамилии, да и ты не брюнет".

Какой цвет волос у каждого из друзей?

Задача №7: Подруги:

Три ученицы – Валя, Галя и Катя – пришли в театр в платьях разного цвета: одна – в белом, другая – в сером, а третья – в черном. Катя была не в черном, Валя не в черном и не в сером. Угадай, в какое платье каждая из них была одета.

Задача № 8 

В семье четверо детей. Им 5, 8, 13 и 15 лет, а зовут их Аня, Юра, Света и Лена. Сколько лет каждому из них, если одна девочка ходит в детский сад, Аня старше, чем Юра, а сумма лет Ани и Светы делится на три?

Задача № 9 

Катя, Боря, Витя и Юра заняли первые четыре места на олимпиаде. Катя не заняла ни первое, ни последнее место, Боря занял второе место, Витя оказался в числе первых трех призеров. Какое место на олимпиаде занял Юра?

Задача № 10 

Три друга Алеша, Боря и Витя  едут после школы домой на различном транспорте: автобусе, троллейбусе, трамвае. Однажды после уроков Алеша пошел проводить своего друга домой до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадку». Кто на чем ездит домой?

Задача № 11 

Клоуны Бам, Бим, Бом вышли на арену в красной, синей и зеленой рубашках. Их туфли тоже были этих трех цветов. Туфли и рубашка Бима были одного цвета. на Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Какого цвета были туфли и рубашка у Бома и Бима?

Задача № 12 Мушкетёры:

Атос, Портос, Арамис и Д’Артаньян – четыре талантливых молодых мушкетёра. Один из них лучше всех сражается на шпагах, другой не имеет равных в рукопашном бою, третий лучше всех танцует на балах, четвертый без промаха стреляет с пистолетов. О них известно следующее: 
• Атос и Арамис наблюдали на балу за их другом – прекрасным танцором. 
• Портос и лучший стрелок вчера с восхищением следили за боем рукопашника. 
• Стрелок хочет пригласить в гости Атоса. 
• Портос был очень большой комплекции, поэтому танцы были не его стихией. 
Кто чем занимается?

Ответы:

1. Папа любит мультфильм «Ну, погоди!», сын – «Покемоны», мама любит мультфильм «Том и Джерри».
2. У любителя «техно» рубашка и бандана белого цвета; у любителя «хаус» черная рубашка и желтая бандана; у любителя «рейв» желтая рубашка и черная бандана.
3. Наф-Наф живет в кирпичном домике и выращивает розы; Ниф-Ниф живет в деревянном домике и выращивает ромашки; Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.
4. Чернов в белом костюме, Белов - в сером, Серов - в черном.
5. У Нади туфли и платье синего цвета; у Вали туфли белые, платье красное; у Маши туфли красные, платье белое.
6. Белов – рыжий, Чернов – блондин, Рыжоа – брюнет
7. Валя – в белом, Галя – в черном, Катя – в сером
8. Анне – 13 лет, Юре – 8 лет, Свете – 5 лет, лене – 15 лет.
9. Последнее (четвертое)
10. Леша ездит на трамвае, Боря - на автобусе, Витя – на троллейбусе.
11. У Бома  синяя рубашка и зеленые туфли, у Бама  зеленая рубашка и синие туфли.
12. Арамис – стрелок; Д’Артаньян – танцор; Портос – шпажист; Атос – рукопашник.