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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

Основные сферы применения теории графов:

В химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия - сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений;

В информатике и программировании (граф-схема алгоритма);

В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете;

В экономике;

В логистике;

В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).

Выделяют особый вид графа, дерево. Дерево - это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность - отсутствие циклов и то, что между парами вершин имеется только по одному пути. На Рис 1.3 представлено двоичное дерево .

Двоичное дерево - древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом , а дети называются левым и правым наследниками .

Матричное представление графов. Матрица инциденций.

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

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

Для ориентированного графа элементы матрицы задаются так:

Матрицу типа, определенную указанным образом, называютматрицей инциденций.

Пример получения матрицы инциденций. Для изображенного ниже графа (Рис. 2.1 а Рис 2.1 б).

Рис 2.1 а Рис. 2.1 б

Матрица смежности.

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

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

Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером до появления ненулевого элемента (+1 или –1). В случае если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число –1. Номер строки, в которой стоит это число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена –1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина. Для получения всего "окружения" надо проделать указанный поиск для всех ненулевых элементов k-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины. Будем в этом случае говорить, что сложность алгоритма анализа окружения вершинысоставляет(порядка).

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

Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин , или булева матрица графа. Это квадратная матрица В порядка n , элементы которой определяют следующим образом:

для неориентированного графа:

для ориентированного графа:

Для изображенного ниже графа (Рис. 2.2 а ) матрицей инциденций будет матрица, представленная на (Рис 2.2 б).

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

Родившись при решении головоломок и занимательных игр (задачи о шахматном коне, о ферзях, « кругосветное путешествие », задачи о свадьбах и гаремах и т. п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. В виде графов можно, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. За последние четыре десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. Применяется при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок- схем программ, в экономике и статистике, химии и биологии, в теории расписаний. В значительной степени через теорию графов происходит ныне проникновение математических методов в науку и технику.

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

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

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

Объект – процесс обучения геометрии.

Предмет –классная и внеклассная работа

Задачи: 1) определить сущность и содержание применения графов в школьном курсе геометрии;

2) разработать ПМК для проведения уроков геометрии в 7-9 классах.

Ведущая тема – построение графовой модели для доказательства геометрических теорем.

Теоретическая основа:

1. Теория графов возникшая в 1736 году (Леонард Эйлер (1708-1783) получила бурное развитие, остаётся актуальной и сейчас, т. к. в повседневной жизни всё большее применение находят графические иллюстрации, геометрические представления и другие приёмы и методы наглядности.

1. Теория графов находит применение в различных областях современной математики и её многочисленных приложений (Липатов Е. П.)

2. Теория графов применяется в таких областях математики, как математическая логика, комбинаторика и др.

Теоретическая значимость работы заключается в:

Выявление областей применения теории графов;

Использование теории графов к изучению геометрических теорем и задач;

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

В результате выполнения данной работы создан:

Программно-методический комплекс для проведения уроков геометрии в 7-9 классах.

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

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

Для этого используется граф-дерево.

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

Исследовательская часть.

Раздел 1. Изучение истории возникновения теории графов.

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

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

История с мостами города Кенигсберга имеет современное продолжение.

Задача На озере находится семь островов, которые соединены между собой так, как показано на рисунке 2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?

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

В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

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

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

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

Раздел 2. Основные виды, понятия и структура графов.

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

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

№ Название графа Определение Рисунок Пример применения этого вида графов

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

Граф, состоящий только из изолированных вершин, называется нуль-графом.

Обозначение: O" – граф с вершинами, не имеющий ребер

2 Полные графы Граф, в котором каждая пара вершин Заметим, что если полный граф имеет n вершин, то количество ребер будет Совершены все рукопожатия.

Обозначение: U" – граф, состоящий из n 10.

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

3 Неполные графы Графы, в которых не построены все Ситуация, когда совершены еще не все рукопожатия,пожали руки А и Б, А и Г, Д и возможные ребра, называются неполными Г, В и Д.

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

вершинами.

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

началом пути, вершина в конце маршрута -

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

циклом называется цикл, не проходящий Например, из пункта A (вершина графа) в пункт H можно добраться различными ни маршрутами: ADGH, AEH, AEFCEH, ABCEH.

через одну из вершин графа более одного Чем отличается маршрут AEH от маршрута AEFCEH?

раза. Тем, что во втором маршруте на «перекрестке» в точке E мы побывали дважды.

Этот маршрут длиннее, чем AEH. Маршрут AEH можно получить из маршрута

Если же цикл включает в себя все ребра AEFCEH «вычеркнув» из последнего маршрут FCE.

графа по одному разу, то такой цикл Маршрут AEH является путем в графе, а маршрут AEFCEH путем не является.

называется Эйлеровой линией.

Связные и несвязные графы. Определение 1: Можно ли из проволоки длиной 12 дм изготовить каркас куба с ребром длины

Две вершины графа называются связными, 1 дм, не ломая проволоку на части?

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

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

1) когда степень каждой вершины четная(путь замкнут)

2)когда только две вершины с нечетной степенью.

Определение 2:

Граф называется связным, если любая пара его вершин - связная.

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

6 Деревья Деревом называется любой связный граф, Приложение №1. Генеалогическое древо Жолмурзаевой Томирис.

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

7 Изоморфные графы. Графы, изображенные на рисунке, дают одну и ту же информацию. Такие графы называют изоморфными (одинаковыми).

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

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

Построим граф, вершины которого

А, Б, В, 1, 2, 3

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

Проведенные в графе на рисунке ребра

А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам).

Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины

Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3

(один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Ответ на вопрос задачи будет: «Нельзя!»

Ориентированные графы Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую - концом этого ребра.

Граф, у которого все ребра ориентированные, называется ориентированным графом.

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

Вывод по проделанной работе:

Я научилась структурировать в таблицу весь информационный материал;

Скомпонованность теоретического материала способствуют наглядному представлению о видах графов и их применению;

Отработала примеры применения теории графов в составлении своего генеалогического древа.

Приложение №1.

ГЕНЕОЛОГИЧЕСКОЕ ДРЕВО

Построить генеалогическое дерево Жолмурзаевой Томирис.

Метод решения.

Графический способ решения задачи.

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

В качестве примера я взяла свое генеалогическое древо.

Раздел 3. Применение теории графов.

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

3. 1. Применение графов в геометрических задачах и теоремах.

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

Докажите, что у равнобедренного треугольника биссектрисы, проведенные из вершин при основании, равны.

Методы решений.

Доказательство задачи с помощью рассуждений.

Пусть АВС – равнобедренный треугольник с

В1 А1 основанием АВ и биссектрисами АА1 и ВВ1.

Рассмотрим ∆АВВ1 и ∆ВАА1. У них ∟В1АВ=

∟А1ВА как углы при основании равнобедрен – ного треугольника ∆АВС. ∟АВВ1= ∟А1АВ

А В так как АА1 и ВВ1 – биссектрисы углов при основании равнобедренного треугольника. АВ- общая сторона. Значит

∆АВВ1 = ∆ВАВ1 по стороне и двум прилежащим к ней углам. Из равенства треугольников следует равенство их сторон АА1 и ВВ1.

Доказательство задачи с помощью графа.

Доказать: АА=ВВ

Используем для рассуждений граф. Вершины графа- условия теоремы или задачи и этапы доказательства.

Ребра графа – логические следования. Конец граф-схемы – доказываемое утверждение.

Дя выделения составных частей использован цвет. Условие теоремы и задачи – синий. Доказываемое утверждение – красный. Этапы доказательства – черный.

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

3. 2. Программно- методический комплекс.

а) Пособие для учителя.

Предлагаемое пособие составлено в соответствии с учебником геометрии 7-9 классов А. В. Погорелова. Основное ее назначение обеспечить процесс изучения геометрии необходимыми средствами наглядностей, оказать помощь учителю в преподавании геометрии: облегчить процесс доказательства теорем, усвоение теоретического материала в процессе решения задач. Граф-схемы носят многоплановый характер и в зависимости от целей и форм занятий можно использовать по-разному: как иллюстративные, направленные на усиление наглядности при объяснении нового теоретического материала, при обобщении и систематизации нового материала (граф-схемы с теоремами); как карточки, используемые при проведении индивидуальных и фронтальных опросов (граф-схемы с задачами). К этому пособию предлагается рабочая тетрадь для учащихся. Рабочую тетрадь можно использовать для организации самостоятельной работы учащихся в урочное и внеурочное время.

б) Рабочая тетрадь для учащихся.

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

Для выделения составных частей использован цвет. Условие теоремы и задачи – синий, доказываемое утверждение – красный, этапы доказательства – черный.

Пособие полезно для учащихся 7-9 классов.

в) Электронное пособие.

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

Создание программно – методического комплекса и ее внедрение осуществлялись в ходе:

Проведения занятий клуба «Аристотель» по теме «Решение логических задач с помощью графов».

Применения графов в доказательствах геометрических теорем и задач

На уроках геометрии в 8,9 классе.

Выступления с проектом на школьной научно- практической конференций.

ЗАКЛЮЧЕНИЕ.

Подводя итоги исследования применения графов в школьном курсе геометрии, я пришла к следующему заключению:

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

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

3. Разработанный программно-методический комплекс для изучения геометрии в 7-9 классах: а) пособие для учителя; б) рабочая тетрадь для учащихся; в) электронное пособие полезен учащимся 7-9 классов.

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

«Средняя общеобразовательная школа № 6»

Реферат на тему:

«Теория графов»

Подготовила: Майорова Екатерина, 8Г класс

Учитель: Малова Татьяна Алексеевна

I. Введение

II. Основная часть.

1.История возникновения теории графов.

2.Некоторые задачи теории графов.

2.1 Логические задачи

2.2 Задачи на связность.

2.3 Задачи по теореме Эйлера о нечетных вершинах

3.Применение теории графов в различных сферах деятельности.

3.1.Графы и информация

3.2.Графы и химия.

3.3.Графы и биология

3.4.Графы и физика

III. Заключение.

IV. Список литературы.

I. Введение.

Я выбрала эту тему, потому что она была и остается актуальной в наше время.

Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике - при построении электрических схем, в химии и биологии

При изучении молекул и их цепочек, в географии – при составлении карт, в истории – при составлении родословной,

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

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

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

II. 1. История возникновения теории графов

Изучив информацию Интернет-ресурсов, я для себя открыла следующие интересные факты об истории теории графов.

Историю возникновения этой теории можно проследить по переписке великого ученого. В ней он сообщал, что ему была предложена задача о семи мостах Кенигсберга. Спрашивалось, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И ему сразу же было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот показался ему достойным внимания тем, что «…Для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство...». После долгих размышлений он нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на рисунке, на котором А обозначает остров, а В, С и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами а, b, с, d, е, f, g.

http://www.cba.upc.edu/projects/logos/Euler_logo.png Кенигсбергские мосты.

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

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

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

Я поняла, что в ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Я, изучив эти выводы, решила проверить их на примерах других задач из раздела теории графов.

В заключение отмечу, что первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

2. Некоторые задачи теории графов

Задач по теории графов не так много. Я рассмотрела материалы

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

^ 2.1 Логические задачи

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

Нулевой граф с пятью вершинами

Неполный граф с пятью вершинами

http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm

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

Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.
1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке 2. Такая схема, состоящая из «изолированных» вершин, называется нулевым графом.
2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д.
Графы, в которых не построены все возможные ребра, называются неполными графами.
3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.

Полный граф с пятью вершинами

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

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

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

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

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

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

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

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

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

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

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

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

^ 2.2 Задачи на связность.

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

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

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

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

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

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

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

^ 2.3 Задачи по теореме Эйлера о нечетных вершинах

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

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

Задача 2. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

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

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

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

3.1.Графы и информация

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

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

3.2.Графы и химия.

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

3.3.Графы и биология

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

процессов – размножение бактерий. Предположим, что через определенный

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

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

Нас будет интересовать лишь один вопрос: в скольких случаях n-е

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

3.4.Графы и физика

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

Печатной схемой называют пластинку из какого-либо диэлектрика

(изолирующего материала), на которой в виде металлических полосок

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

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

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

III. Заключение

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

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

IV. Список литературы и Интернет-ресурсов.

1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

2. Касаткин В. Н. "Необычные задачи математики", Киев, "Радяньска школа"

1987(часть 2);

3. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

4. "В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов теории графов");

5. Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные

Задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;

7. Оре О. "Графы и их применения", М. "Мир", 1965;

8. Зыков А. А. "Теория конечных графов", Новосибирск, "Наука", 1969;

9. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

10. Реньи А., "Трилогия о математике", М., "Мир", 1980.

11. http://ru.wikipedia.org

12. http://www.xumuk.ru

13. http://www.seznaika.ru

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

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

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

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

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

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

Задачи исследования:

рассмотреть решение задач при помощи графов;

научиться переводить задачи на язык графов;

сравнить традиционные методы решения задач с методами теории графов.

В 1736 году великий математик Леонард Эйлер нашел решение головоломки, носящей название «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом) омывает два острова (рис. Рисунок 1Рисунок 1). Берега реки с островами были во времена Эйлера связаны мостами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать.

Рисунок 1

Л. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок. Владея материалом вводной части курса «Знакомство с графами», нетрудно воспроизвести идею рассуждения Л. Эйлера. Для этого нужно предварительно заменить Рисунок 1 схемой, приведенной на рисунке 2, где острова и берега изображаются точками.

Рисунок 2

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

Спустя сто с лишним лет, в 1874 году немецкий ученый Г. Кирхгоф разработал эффективную методику определения значения силы тока в электрической цепи, используя методы и понятия, получившие позднее права гражданства в теории графов. Еще 10 лет спустя английский математик А. Кели (мать его была русской, он владел русским языком и следил за русской математической литературой; он оказался среди тех немногих математиков, которые с самого начала поняли и поддержали идеи Н.И. Лобачевского) разработал теорию деревьев для подсчета числа изомеров насыщенных углеводородов с данным числом n атомов углерода.

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

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

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

Рисунок 3

Граф на рис.Рисунок 3 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф, на котором легко увидеть возможные маршруты. Вершина М вверху- начало маршрутов. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4321  24 способа.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G 1 (рис.Рисунок 4).

Рисунок 4

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

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

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

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

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

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

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

Рисунок 5

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

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

Рисунок 7

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров - рыжий, Чернов - белокурый, Рыжов – брюнет. Таким же приемом решаются, например, задачи 2 и 3.

Задача 2. Для Вани, Коли и Миши испечены пироги: один с капустой, другой с рисом, третий – с яблоками. Миша не любит пирог с яблоками и не ест с капустой. Ваня не любит пирог с капустой. Кто какой пирог ест?

Задача 3. На одном заводе работают три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Иванов и Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назовите фамилии слесаря, токаря и сварщика.

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

Задача 4. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

Решение. Выделим три множества: множество имен, множество предметов и множество городов. Элемент каждого из множеств на рисунке 4 задан своей точкой (буквы на этом рисунке - первые буквы соответствующих слов). Если две точки из разных множеств характеризуют признаки разных людей, то будем соединять такие точки штриховой линией. Если же две точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попарно сплошными линиями. Существенно, что по условию задачи для каждой точки любого множества в каждом из остальных множеств найдется одна и только одна точка, ей соответствующая.

Рисунок 8

Таким образом, граф на рисунке 8 содержит все заданные в условии элементы множеств и отношения между ними. Задача на языке графов сводится к нахождению трех «сплошных» треугольников с вершинами в разных множествах.

Рассмотрим граф на рисунке 8. Напрашивается штриховой отрезок ХД, Действительно, Л соответствует X и, одновременно, Л не соответствует Д, т. е. X не может соответствовать Д. Итак, используется типичная для такого рода задач операция на графе: если у треугольника с вершинами в трех разных множествах одна сторона сплошная, вторая - штриховая, то третья должна быть штриховой. Из условия задачи следует равномерность еще одной операции на графе: если какая-то точка соединена штриховыми отрезками с двумя точками во втором множестве, то ее следует соединить с третьей точкой этого множества сплошным отрезком. Так проводится сплошной отрезок ДФ. Далее проводится штриховой отрезок ДМ (в треугольнике ДФМ сторона ДФ сплошная, а ФМ - штриховая), ДК сплошным (ДМ и ДЛ штриховые), Теперь соединим точки Ф и К сплошным отрезком. Если в треугольнике с вершинами в разных множествах две стороны сплошные, то третья тоже будет сплошной. Найден первый «сплошной» треугольник ДФК. Так, не возвращаясь к тексту задачи, руководствуясь лишь естественными операциями на графе, описанными выше, мы находим решение (рис. 9).

Рисунок 9

Отметим последовательность, в которой проводились отрезки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподает химию в Ленинграде, Дмитрий - физику в Киеве и Степан - биологию в Москве.

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

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 10

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 11

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

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

Задача 6. В шахматном турнире принимали участие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер. Известно:

1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;

2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;

3. в третьем туре Евдокимов играл с инженером;

4. по окончании турнира места распределились так - Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.

Какие профессии имели Григорьев, Дмитриев и Евдокимов?

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 2

Подготовил

Легкоконец Владислав, ученик 10А класса

Практическое применение Теории Графов

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

Л.И. Носкова, учитель математики

ст.Брюховецкая

2011 г.

1.Введение………………………………………………………………………….………….3

2.История возникновения теории графов………………………………………….………..4

3.Основные определения и теоремы теории графов……………………………….………6

4.Задачи,решаемые при помощи графов……………………………..……………………..8

4.1 Знаменитые задачи………………………………….………………………...8

4.2 Несколько интересных задач………………………………….……………..9

5.Применение графов в различных областях жизни людей……………………………...11

6.Решение задач……………………………………………………………………………...12

7. Заключение………………….…………………………………………………………….13

8. Список литературы………….……………………………………………………………14

9.Приложение…………………………………………………………………….…………15

Введение

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

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

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

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

Задачи исследования:

1.Изучить литературу и ресурсы сети Интернет по данной проблеме.

2.Проверить эффективность метода графов при решении практических задач.

3. Сделать вывод.

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

В работе используются следующие методы: наблюдение, поиск, отбор, анализ.

История возникновения теории графов

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

[Приложение рис.1] Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [Приложение рис.2] , на котором A обозначает остров, а B ,C иD – части континента, отделенные друг от друга рукавами реки

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Основные определения и теоремы теории графов

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

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

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

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B , C , D . Иногда граф в целом будем обозначать одной заглавной буквой.

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

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

Обозначение: O "– граф с вершинами, не имеющий ребер

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

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

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

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

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

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

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

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

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

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

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

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

Определение 14. Две вершины A и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из A в B .

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

Определение 16. Деревомназывается связный граф, не содержащий циклов.

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

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

Определение 18. Дерево, все n вершин которого имеют номера от 1 до n , называют деревом с перенумерованными вершинами.

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

Задачи решаемые при помощи графов

Знаменитые задачи

Задача коммивояжера

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

Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Метод решения задачи коммивояжера

Жадный алгоритм “иди в ближайший (в который еще не входил) город”.
“Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Рассмотрим для примера сеть на рисунке [приложение рис.3] , представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Задача о Кенигсбергских мостах.

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

Рассмотрим граф, соответствующий схеме мостов [приложение рис.2].

Чтобы ответить на вопрос задачи, достаточно выяснить, является ли граф эйлеровым. (Хотя бы из одной вершины должно выходить четное число мостов). Нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно.

Несколько интересных задач

1. "Маршруты".

Задача 1

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза [приложение рис.4].

Решение :

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF ; перечеркнем FO ; отметим жирной линией FH , НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D - Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву [приложение рис.5] .

Задача 2

На рисунке изображена схема местности [приложение рис.6].

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой - самый длинный.

Решение :

Последовательно "расслаиваем" схему в дерево, начиная с вершины 1[приложение рис.7] . Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

2 "Группы, знакомства"

Задача 1

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

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Решение: Пусть участники фестиваля А 1 , А 2 , А 3 . . . , А n – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами [Приложение рис.8]

Решение:

а) степень каждой вершины А i показывает число конвертов, которое передал участник А i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n , N =2p , где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.

Задача 2

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д. Это первые буквы имён. Соединим те точки, которые соответствуют именам созвонившихся ребят.

[ приложение рис.9]

Из рисунка видно, что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Применение графов в различных областях жизни людей

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

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

Молекулярные графы , применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул [приложение рис.10] . Вершины и ребра этих графов отвечают соответственным атомам и химическим связям между ними.

Молекулярные графы и деревья: [приложение рис.10] а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

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

Белковые сети

Белковые сети - группы физически взаимодействующих белков, которые функционируют в клетке совместно и скоординированно, контролируя взаимосвязанные процессы, происходящие в организме [приложение рис. 11].

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

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка – обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков – вершин, соответствующих классам нижнего уровня.

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

Пример генеалогического дерева моей семьи [приложение рис.12].

Еще один пример. На рисунке показано библейское генеалогическое дерево [приложение рис.13].

Решение задач

1.Транспортная задача . Пусть в городе Краснодаре находится база с сырьём, которое нужно развести по городам Крымск, Темрюк, Славянск-на-Кубани и Тимашевск одним заездом, затратив при этом как можно меньше времени и топлива и вернувшись обратно в Краснодар.

Решение:

Для начала составим граф всех возможных путей проезда [приложение рис.14] , учитывая реальные дороги между данными населенными пунктами и расстояние между ними. Для решения этой задачи нам потребуется составить еще один граф, древовидный [приложение рис.15] .

Для удобства решения обозначаем города цифрами: Краснодар – 1, Крымск – 2, Темрюк – 3, Славянск – 4, Тимашевск – 5.

В результате вышло 24 решения, но нам нужны только кратчайшие пути. Из всех решений удовлетворяют только два, это 350 км.

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

Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами [приложение рис.16].

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Заключение

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

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

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

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

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

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

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

Литература

Берж К. Теория графов и ее применения. -M.: ИИЛ, 1962.

Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. -M.: ИИЛ, 1963.

Оре О. Графы и их применение. -M.: Мир, 1965.

Харари Ф. Теория графов. -M.: Мир, 1973.

Зыков А.А. Теория конечных графов. -Новосибирск: Наука, 1969.

Березина Л.Ю. Графы и их применение. -M.: Просвещение, 1979. -144 c.

"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

Приложение