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

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

В статье предложена подборка задач, одним из способов решения которых является метод графов. Этот метод позволяет легко и красиво решать задачи типа «Кто есть кто?», весьма интересен и вызывает живой интерес у обучающихся.

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

Скачать:

Вложение	Размер
metod_grafov._reshenie_zadach_metodom_grafov.doc	65.5 КБ

Предварительный просмотр:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Решение задач с помощью графа

Теория графов применяется при решении задач из многих предметных областей: математика, биология, информатика

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе — семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках — проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.

Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.

Виды графов:

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2. Неориентированный граф — это граф, в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Решение задач с помощью графов:

Задача 1.

Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Вершины графа — это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Ниже представлен разбор задач.

Источник

Графы. Применение графов к решению задач

1. Методические рекомендации к теме “Графы”.

Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.

Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).

2. Теоретический материал к теме “Графы”.

Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

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

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

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

Связность.

8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

Графы Эйлера.

9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

Источник