Исследовательская работа "Решение задач с помощью графов"

Введение.

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

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

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

Историческая справка.

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

Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы XX столетия.

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

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

Определение: Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек.

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

Примеры.

1. На рисунке 1.1 изображен граф с четырьмя вершинами и тремя ребрами.
2. На рисунке 1.2 изображен граф с пятью вершинами и пятью ребрами.
3. На рисунке 1.3 изображен граф с четырьмя вершинами и семью ребрами.
4. На рисунке 1.4 изображен граф с четырьмя вершинами и четырьмя ребрами.
5. На рисунке 1.5 изображен граф с четырьмя вершинами и тремя ребрами.

Примерами графов могут служить схема метрополитена, схемы железных дорог, структурные формулы молекул, планы выставок и т. д., словом, схемы и планы (или карты) без указания масштабов, показывающие лишь связи между принадлежащими им объектами.

1

Полные графы.

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

На рисунках 1.1, 1.2, 1.3, 1.5 граф не является полным, а на рисунке 1.4 граф полный.

Теорема: В полном графе с п вершинами п(п-1)/2 ребер.

Доказательство:

Поскольку граф полный, то каждая из его вершин соединена с каждой из (п-1) остальных вершин. Следовательно таких соединений будет п(п-1). Следует учесть, что каждому ребру принадлежат 2 точки, тогда общее число ребер п(п-1)/2.

Определение: Степенью вершины графа называется число ребер, которым принадлежит эта вершина.

На рисунке 1.1 степень вершины А1 равна 3, степень А2 равна 1. На рисунке 1.2 все вершины имеют степень равную 2. На рисунке 1.3 степень вершины А3 равна 5. На рисунке 1.5 степень вершины А4 равна 0 (такие вершины называют изолированными).

Определение: Вершина называется четной, если степень ее число четное и нечетной, если степень ее число нечетное.

На рисунках 1.1 и 1.4 все вершины нечетные, а на рисунках 1.2 и 1.5 все вершины четные.

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

2

Теорема: В графе сумма степеней вершин четное число, равное удвоенному числу ребер.

Доказательство:

Каждое ребро соединяет две вершины, следовательно, увеличивает степень двух вершин на 2 и тогда сумма степеней вершин равна удвоенному числу ребер.

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

Доказательство:

Сумма степеней вершин четное число, равное удвоенному числу ребер. Отсюда следует, что сумма степеней нечетных вершин будет четной, но это возможно, когда число таких вершин четное число.

Теорема: Во всяком графе с п вершинами, где п>2,всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

Доказательство:

Степень любой вершины меньше п. Если все вершины имеют разные степени, то они могут быть: 0, 1, 2, …, п-1. Учитывая, что вершина, степень которой равна 0, не соединена ни с какой другой, то ни у одной вершины степень п-1 не может быть. Тогда найдутся две вершины с одинаковыми степенями.

Путь в графе. Цикл.

Определение: Путем от А1 до Ап в графе называется такая последовательность ребер ведущая от А1 к Ап, в котором два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.

На рисунке 1.2 путь (А1; А3) выглядит так: А1 – А2, А2 – А3.

На рисунке 1.3 путь (А1; А2): А1 – А3, А3 – А2.

Определение: Циклом называется путь, в котором совпадают начальная и конечная вершины.

На рисунке 1.2 путь (А1; А1): А1 – А2. А2 – А3, А3 – А4, А4 – А5, А5 – А1 является циклом.

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

Определение: Длиной пути называется число ребер этого пути. Длиной цикла называется число ребер в этом цикле.

Теорема: Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Доказательство:

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

3

Связные графы.

Определение: Две вершины графа называются связными, если существует путь с концами в этих вершинах. Две вершины называются несвязными, если в графе не существует ни одного пути, связывающего их.

На рисунке 1.1 вершины А1 и А2 – связные, А2 и А4 – связные и т. д.

На рисунке 1.5 вершины А1 и А4 – несвязные.

Определение: Граф называется связным, если каждые две вершины его связные.

На рисунке 1.1 граф связный.

Определение: Граф называется несвязным, если хотя бы две его вершины несвязные.

На рисунке 1.5 граф несвязный.

Теорема: Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Прямая теорема: Если данный граф связный и степень каждой его вершины равна 2, то этот граф представляет собой простой цикл.

Доказательство: Из каждой вершины данного графа в любую другую ведет путь. Начнем путь,  например, с вершины А1, дальнейшее движение может быть выбрано двояко (в А7 или в А2). Выберем А7, тогда из этой вершины существует только один путь

в А6, из А6 в А5 и т. д. Поскольку граф связан, то действуя т.о. мы обойдем все его вершины и вернемся в А1, потому что степень А1 равна 2. Тогда получается, что граф является простым циклом.

Обратная теорема: Если граф – простой цикл, тогда степень каждой его вершины равна 2.

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

Эйлеровы графы.

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

Исторически топология и теория графов зародились при решении Эйлером задачи именно такого вида (задачи о Кенигсбергских мостах). Задачи на отыскание путей через лабиринты, близкие к задачам на Эйлеровы графы, находят применение в современной психологии, а также при конструировании вычислительных машин.

4

 Задание по обведению ребер удается выполнить для графов на рисунках 2.1, 2.2, 2.4, 2.5. Графы на рисунках 2.3 и 2.6  нарисовать без отрыва  карандаша от бумаги или, не проходя дважды по ребрам, не удается. В чем секрет? Какие свойства графа повлияли на это? Введем несколько определений.

Определение: Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

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

Из теории графов известно, что:

1.              Одним росчерком можно построить граф, все вершины которого четные, при этом движение можно начинать в любой вершине и завершить его в той же вершине.

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

Самой знаменитой в теории графов является задача о кенигсбергских мостах. Это, по сути, первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях Петербургской Академии наук.

5

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

Решение:

Обозначим различные части города буквами A, B, C, D, а мосты – буквами a, b, c, d, e, f, g. В этой задаче существенны лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадем в другую, и, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому изобразим план города в виде графа, вершины которого A, B, C и D изображают отдельные части города, а ребра  a, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый и непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами, этот граф можно было бы вычертить, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру. Но это невозможно – какую бы вершину мы не выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро (мост, которым мы воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, должно быть четным. Наш граф этому условию не удовлетворяет, и поэтому  требуемого маршрута не существует.

Граф – дерево. Лес.

Определение: Деревом называется всякий связный граф, не имеющий цикла. Лесом называется несвязный граф, представляющий объединение деревьев.

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

Задача: В школе  проводились соревнования по плаванию. Болельщики высказали следующие предположения о победителях:

1. Наташа будет первой, а Вера – второй;
2. Света – первой, а Люда – 3;
3. Света – 1, а Вера – 3.

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

Решение: Построим граф – дерево и проанализируем все возможные пути.

6

Н1 или В2

С1 или Л3

С2 или В3

Ответ: Наташа – 1, Света – 2, Люда – 3, Вера – 4.

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

Определение: Граф, все ребра которого ориентированы (т. е. указаны начало и конец), называется ориентированным.

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

Задача: Известно, что заяц тяжелее собаки, кролик легче поросенка, а собака тяжелее поросенка. Кто из них самый тяжелый, а кто легкий?

Решение: Зададим направление «Х тяжелее У» и построим ориентированный граф.

Ответ: Легче всех кролик, тяжелее заяц.

7

Двудольные графы.

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

Рассмотрим задачу, для решения которой применимы двудольные графы.

Задача: В школьном драм кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.

- Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.

- Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. – С раннего детства мечтал воплотить этот образ на сцене.

- Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- …А мне – Осипа, - не уступил ему в  великодушии Дима.

- Хочу быть Земляникой или Городничим, - сказал Вова.

- Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение: Попробуем построить граф для ситуации, описанной в задаче. Изобразим юных актеров точками верхнего ряда: А – Алик, Б – Боря, В – Вова, Г – Гена, Д – Дима, а роли. Которые они  собираются играть, точками второго ряда (1 – Ляпкин-Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 – Городничий). Затем от каждого участника проведем отрезки, т. е. ребра, к ролям, которые он хотел бы сыграть. У нас получился граф с десятью вершинами и десятью ребрами.

Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведет по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима, а Землянику – Вова. Вершина 1 – Ляпкин-Тяпкин – соединена с ребрами Г и Д. Ребро 1 – Д отпадает, так, как Дима уже занят, остается ребро 1 - Г, Ляпкина-Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребра А – 5 и Б – 2, либо ребра А – 2 и Б – 5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае наоборот. Как показывает граф, других решений задача не имеет.

8

Приложение.

Задачи, решаемые с помощью графа-дерево.

1.              Пять учеников – Алик, Витя, Степа, Дима и Леня – приехали из разных городов: Москвы, Риги, Нижнего Новгорода, Киева и Ярославля. О том, кто откуда приехал, получено четыре ответа, в каждом их которых одна половина ответа верна, а другая  - нет: Алик приехал из Риги, а Дима – из Нижнего Новгорода; Витя приехал из Риги, а Степа – из Киева; Степа приехал из Риги, а Дима – из Москвы; Леня приехал из Ярославля, а Алик – из Москвы. Назвать город, из которого приехал каждый из учеников.

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

1. АР или ДН;        
2. ВР или СК;
3. СР или ДМ;
4.  ЛЯ или АМ.

Проанализировав возможные пути, найдем верный.

Ответ: Алик из Риги, Витя из Нижнего Новгорода, Степа из Киева, Дима из Москвы, Леня из Ярославля. 

2.              Во время сбора металлолома Дима, Боря и Костя отправились на поиски в посадку, почти вплотную подступавшую к школьному двору. Там они нашли увесистую деталь, погрузили на тележку и повезли на школьный двор.

- Вот нам повезло, - сказал Дима по дороге в школу. - Эта штука из чистой меди, да и весит килограммов 30.

Все его действия выражали явную радость по поводу выпавшей удачи.

- Какая там медь, - возразил Боря. – Это обыкновенное заржавевшее железо. Но ты не унывай, Дима. Оно знаешь какое тяжелое. В нем 100 килограммов будет.

- Да, это явно не медь, - вмешался Костик, - а весу 50 килограммов, я думаю, наберется.

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

- Не расстраивайтесь, ребята. Каждый из вас оказался прав в одном из своих предположений.

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

Решение:

9

1. М или 30;       
2. Ж или 100;
3. Н или 50.

Ответ: Ребята нашли железную деталь весом 30 кг.

3.              Пяти ученикам – Андрееву, Блинову, Васильеву, Герасимову и Дмитриеву – поручили уборку в классных комнатах 5, 6, 7, 8 и 9 классов.

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

- Андреев убирал 5-й класс, а Блинов – 9-й, - сказал один.

- Нет, Блинов убирал 8-й класс, а Васильев – 7-й. – возразил другой.

- Блинов убирал 6-й класс, а Герасимов – 5-й, - вспомнил один из членов санитарной комиссии.

- Нет, Герасимов убирал 8-й класс, а Дмитриев – 7-й, - сказала уборщица тетя Даша.

- Ну, и напутали же вы, - вмешался в разговор сторож дедушка Максим. – Дмитриев убирал 9-й класс, а Васильев – 6-й.

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

Кто из учеников убирал седьмой класс?

Решение:

1. А5 или Б9;
2. Б8 или В7;
3. Б6 или Г5;
4. Г8 или Д7;
5. Д9 или В6.

.       

Ответ: Седьмой класс убирал Васильев.

4.              Пять ребят – Алик, Боря, Витя, Лена и Даша – приехали отдыхать в загородный лагерь из пяти разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска.

10

О том, кто из какого города  прибыл, были получены такие истинные высказывания:

1. Если Алик не из Умани, то Боря из Краматорска;

                  2. Или Боря, или Витя приехал из Харькова;

3. Если Витя не из Славянска, то Лена приехала из Харькова;

4. Или Даша приехала из Умани, или Лена – из Краматорска,

Установить, кто из ребят из какого города приехал.

Решение: Заменим истинные высказывания на  противоположные.

1.      Ау или Бк;    

2.      Бх или Вх;

3.      Вс или Лк;

4.      Ду или Лк.

Ответ: Алик из Умани, Боря из Харькова, Витя из Славянска, Лена из Краматорска, Даша из Полтавы.

5.              Максим, Эдик, Андрей и Дима играли во дворе в футбол. Случилось так, что неудачный пас одного из них угодил прямо в окно.

Расспросы виновников дали такую картину.

- Я в окно не ударял, Андрей тоже в этом не виновен, сказал Эдик.

- Окно разбил не я, это сделал Дима, - возразил Максим.

- Мячом в окно попал не я, это Андрей буцнул в окно, - заявил Дима.

- Мяч в окно попал не от меня, это Эдик разбил окно, - сказал Андрей.

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

Решение:

1.      Эн или Ан;        

2.      Мн или Дд;

3.      Дн или Ад;

4.      Ан или Эд.

Ответ: Окно разбил Эдик.

11

Задачи, решаемые с помощью ориентированных графов:

1.      Из лагеря вышли пять туристов: Валя, Галя, Таня, Лена и Марина. Таня впереди Марины, Лена впереди Вали, но позади Марины, Галя впереди Тани. Кто идет первым, кто последним?

Решение: Зададим направление: «Х впереди У». 

Ответ: Галя  - первая, последняя – Валя.

2.      В нашем лесу каждый занимается своим делом и обучает этому делу других:

Одни плетут корзины, другие ловят рыбу. Ремеслу мы научили друг друга. Кот учился у выдры, Еж у Зайца, Лиса у Волка, Мышь у Ежа, Бобер учил Волка и Выдру, Заяц Белку, а Барсук Зайца. Бобер был учеником Медведя, а Еж учителем Дятла. Лучше всех корзины плел Еж. Чем занимался Заяц, Дятел, Волк и Лиса? Кто из зверей раньше всех научился ловить рыбу и кто плести корзины?

Решение: Зададим направление «Х учил У» и построим ориентированный граф.

Ответ: Барсук раньше всех научился плести корзины и научил Зайца и Дятла.

Медведь раньше всех научился ловить рыбу и научил Волка и Лису.

3.      Дружные ребята живут в нашем дворе. Все они учатся в одной школе, но в разных классах, с четвертого по десятый.

Галя старше Володи на один класс, но моложе Ефима на два класса; Дима на два класса моложе Жени, но на два класса старше Володи.

Жене, девятикласснику и восьмикласснику была поручена подготовка математической викторины.

Боря подарил Алику свои прошлогодние учебники.

В каком классе учится каждый из ребят нашего двора?

Решение: Зададим направление «Х старше У» и составим ориентированный граф.  

Ответ: Володя в 4, Галя в 5, Дима в 6, Ефим в 7, Женя в 8, Алик в 9, а Боря в 10.

12

4.      В забеге шести спортсменов Адам отстал о Богдана и еще от двух спортсменов. Виктор  финишировал после Дмитрия, но ранее Геннадия. Дмитрий опередил Богдана, но все же пришел после Евгения. Какое место занял каждый спортсмен?

Решение: зададим направление «Х быстрее У» и составим ориентированный граф. 

Ответ: Евгений занял первое место, Дмитрий – второе, Богдан – третье, Адам – четвертое, Виктор – пятое, Геннадий – шестое.

Задачи, решаемые с помощью двудольных графов:

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

Решение: по условию задачи  составим двудольный граф.

Ответ: Чернов – блондин, Рыжов – брюнет, Белокуров – рыжий.

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

Коля: «Ни первое, ни последнее».

Боря: « Второе».

Вова: «Не был последним».

Кто какое место занял?

Решение: по условию задачи составим двудольный граф.

Ответ: Вова -1, Боря – 2, Коля – 3, Юра – 4.

13

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

Решение: по условию задачи составим двудольный граф.

Ответ: Рая – волейболистка, Майя – пловчиха, Галя – теннисистка.

4.      В загородном лагере встретились три мальчика, приехавшие из Минска, Киева и Екатеринбурга. При знакомстве оказалось, что они разного возраста и  увлекаются спортом. В теннис играют только Коля  и минчанин. В футбол – только Сережа и киевлянин. Олег играет в шахматы, и он старше киевлянина. Теннисисты в шахматы не играют. Шахматист не самый старший. В каком городе живет каждый из мальчиков, и каким видом спорта он увлекается? Каковы они по возрасту?

Решение: составим двудольный граф.

Ответ: Коля из Киева, Сережа из Минска, Олег из Екатеринбурга, в теннис играют Коля и Сережа, в футбол играют Коля и Сережа, Олег играет в шахматы. Сережа старше Олега, а Коля – самый молодой.

5.      Три ученицы – Аня, Валя и Катя – принимали участие в конкурсе. Их фамилии Морева, Розова и Наумова. О них известно следующее. Наумова участвовала в конкурсе впервые. Аня выступила хуже всех. Валя в прошлом году заняла второе место. Работы двух лучших участниц выполнены в тетрадях в  клетку. Морева писала на отдельных листках. Найти фамилии и имена двух лучших участниц конкурса.

14

Решение: составим двудольный граф.

Ответ: Валя Розова и Катя Наумова.

6. Директор, завуч и завхоз школы имеют фамилии Антонов, Борисов и Гриднев. Такие же фамилии и у учителей истории, физики и иностранного языка.

Учитель Гриднев живет на улице Докучаева. Завуч и учитель физики живут в новом доме на улице Победы. Учитель Борисов просил своего коллегу сделать перевод небольшой научной статьи. Однофамилец завуча – учитель иностранного языка – недавно получил квартиру в том же доме по улице Первомайской, в котором живет завхоз.

Оказалось так, что в каждом доме живут коллеги с разными сочетаниями фамилий.

Как фамилия директора школы?

Решение: составим двудольный граф.

Ответ: Фамилия директора школы – Борисов.

15

Уникурсальные фигуры.

Можно ли построить одним росчерком пера следующие фигуры?

Рис. 1. Эту фигуру нарисовать нельзя одним росчерком, так как она имеет четыре нечетных узла.

Рис. 2. Можно, если следовать по пути T-A-D-T-B-C-T.

Рис. 3. Нельзя, так как фигура имеет 4 нечетных узла.

Рис. 4. Можно. Путь B-E-T-Z-X-Y-C-K-O-M-P-H-K-D- B-A-A.

Рис. 5. Можно. Путь 1-2-3-4-5-6-7-8-9-10.

16

Содержание:

Введение                                                                                    1

Глава 1. Теория графов

1. Исторические сведения                                                        1

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

3. Полные графы                                                                       2

4. Путь, цикл в графе                                                                3

5. Связные графы                                                                      4

Глава 2. Применение графов

1. Эйлеровы графы                                                                   4

2. Граф дерево. Лес                                                                   6

3. Ориентированные графы                                                     7

4. Двудольные графы                                                               8

Приложение

Задачи, решенные с помощью графов                               9 - 16

Заключение                                                                              17

Литература                                                                               18

Заключение

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

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

17

Литература:

1.  Березина Л. Ю. Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 143 с. с ил.
2. Елисеев Е. М., Елисеев М. Е. Дискретная математика для информатиков. Учебное пособие. – Арзамас, АГПИ им. Гайдара, 2004 – 120 с.
3. Лекции по теории графов /Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. – М.: Наука, 1990
4. Мельников О. И. Занимательные задачи по теории графов – Минск: Тетрасистемс, 2001
5. Шевченко В. Е. Некоторые способы решения логических задач. – Киев: Вища школа, 1979. – 80 с.

18

Приложение 7

Муниципальное образовательное учреждение гимназия

Творческая работа по математике

«Решение логических задач с помощью графов»

                                                                            Пичугин Дмитрий

                                                                               Пушкарева Надежда

                                                                          ученики 8 класса

                                                                     Руководитель:

                                                                                                     учитель математики

                                                                                                     Бурзаева С. В.

2006 г.