Исследовательская работа по теме графы. Исследовательская работа по математике "графы и их применение"

страница 1

Научное общество учащихся

«Поиск»

Секция информатика

Научная работа по теме:

«Его величество Граф»

Выполнила : Сапожникова Светлана,

ученица 7 класса

МОУ «Сергеевская СОШ»

Оконешниковского МР

Руководитель : Гармс Елена Анатольевна,

учитель информатики

МОУ «Сергеевская СОШ»

Омск - 2010
Содержание

Научное общество учащихся 1

«Поиск» 1

Научная работа по теме: 1

Введение 3

ТЕОРИЯ ГРАФОВ 4

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

1.3. Задача о мостах, Леонард Эйлер и теория графов 8

2.1. Решение задач с помощью графов «Один день из жизни Графа» 11

Библиографический список 16

Введение

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

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

Объект исследования : понятие граф
Предмет исследования : степень распространенности применения графов
Цель исследования : Исследовать роль графов в нашей жизни.
Задачи исследования :

1.познакомиться с историей возникновения графов;

2.познакомиться с основными понятиями графа, видами, элементами;

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

4.составить своё родословное дерево.
Методы исследования : частично - поисковый, аналитический.

Глава 1

ТЕОРИЯ ГРАФОВ

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

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

В математике определение графа дается так: «графом называется конечное множество точек, некоторые из которых соединены линиями».

В информатике под графом понимают средство для наглядного представления состава и структуры системы.

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

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

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

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

хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг .

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

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

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

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

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

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

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

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

Закономерность 2.

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

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

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

ТЕОРЕМА.

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

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

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как

K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

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

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

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.

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

Закономерность 5.

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

Закономерность 6.

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

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

рис.6 (эйлеровы графы)

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

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

Граф называется несвязным, если это условие не выполняется.

рис.7рис.8
На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)

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

1.3. Задача о мостах, Леонард Эйлер и теория графов

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

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

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

Рисунок 9

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

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

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

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

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

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

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

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

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.10а). В графе на рис.10б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро. (рис.12)

рис.10 а;б
Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

Свойство 2.

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

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

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

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

Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.

ЛЕММА (о висячей вершине)

В каждом дереве есть висячая вершина.

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

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

Что можно описать с помощью графов? Обозначим области применения данного описания.

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

Например:

Схему линий метрополитена можно рассматривать как граф;

В химии граф можно рассматривать как способ отображения структуры молекулы;

В медицине – вопрос о группе крови;

В виде графа можно представить генеалогическое дерево;

Системы классификаций в науке.

Иерархическую структуру административного управления предприятия, ВУЗа и т.д.

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

Глава 2

2.1. Решение задач с помощью графов «Один день из жизни Графа»

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

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

Маршрут движения автобуса – это граф.

Задача 2. При встрече каждый из моих одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо; 3)пятеро?

Решение.

Задача решается с помощью полных графов.

1)Встретились трое:

Количество рукопожатий равно количеству рёбер, т.е.3.

2)Встретились четверо:

Количество рёбер 6; возможно 6 рукопожатий.

3)Встретились пятеро:

В графе 10 рёбер; возможно 10 рукопожатий.

Ответ: 1)3; 2)6; 3)10.
По расписанию у нас шесть уроков: геометрия, история, информатика, география, русский язык и физика.
Задача 3. На уроке геометрии было предложено построить граф классификации геометрических объектов. Это оказалось легко сделать с помощью понятия граф.

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

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

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

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

Задача 7 . На уроке русского языка тема «Числительные» и учитель предложила нам составить опорный конспект.

Числительные в русском языке классифицируются по составу и по значению. По составу они делятся на простые, сложные и составные. Пример простых числительных: четыре, пять. Пример сложных числительных: шестьдесят, пятьсот. Пример составных числительных: 35, 154. По значению числительные делятся на порядковые и количественные. Пример порядковых числительных: второй, девятый. Пример количественных числительных: шесть, два.

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

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

Решение.

Чтобы указать все обеды из двух блюд, будем рассуждать так.

Выберем одно первое блюдо (борщ) и будем добавлять к нему поочерёдно разные вторые

Ответ: 8 разных обедов из двух блюд.

Замечание. В задаче осуществляются два выбора, но каждый выбор - из своего множества вариантов.

Ответ: 6 сочетаний.

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

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

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

Так графы стали мои лучшими друзьями. Одноклассники и учителя заметили, что у меня улучшилась успеваемость по предметам. Но я то знаю, что это благодаря «Его величеству Графу»!

Вывод

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

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

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

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

Библиографический список

1. Генкин, С. А, Итенберг И. В. Ленинградские математические кружки: пособие для

внеклассной работы.-Киров, 1994г.

2.Горбачев, В.Г. Сборник олимпиадных задач по математике.- М., 2004г.

3. Игнатьев Е.И. Математическая смекалка. - Москва, 1994 г.

4.Оре, О. Графы и их применение.- Москва, 1979 г.

5.Перельман, Я.И. Весёлые задачи.- Москва, 2003г

6. Физико-математический журнал «Квант», А. Савин, №6, 1994г.

страница 1

МОУ СОШ №6

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

«Графы»

Выполнил: Макаров Дмитрий

ученик 8 класса МОУ СОШ№6

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

Кривцова С.А

Учитель математики и информатики

МОУ СОШ № 6

Г. Абдулино, 2007 г.

СОДЕРЖАНИЕ:
I.ВВЕДЕНИЕ

Актуальность и новизна
Цель и задачи

II. ОСНОВНАЯ ЧАСТЬ
1.Понятие о графах

2.Свойства графов

3.Применение графов
III.Практическая часть
IV.Заключение
V.Литература

VI.Приложение

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

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

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

2. Цель и задачи.
Цель: рассмотреть решение задач с использованием «Граф», проверить выполнение
«Графов» на родословных.
Задачи:

Изучить научно- популярную литературу по данному вопросу.

Исследовать выполнение ”Графов’’ для выяснения родственных отношений

Проанализировать результаты проведенных экспериментов

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

1.ПОНЯТИЕ О ГРАФАХ
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины , - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

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

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

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

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

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

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

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

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

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

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

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

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

Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0),если наполним водой большую кастрюлю, или (5, 0, 3), если наполним меньшую кастрюлю.

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

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

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

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

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

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

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

III. Практическая часть.

Методы работы:
Сравнение и анализ результатов эксперимента.
Методика работы:

Для проведения исследований были выбраны:

А) Родословная моей семьи , архивы данных, свидетельства о рождении.

Б) Родословная князей Голицыных, архивы данных.
Я провел исследование, результаты исследования поместил в схемы и проанализировал их.
Методика 1.
Цель: проверить выполнение ’’Графов” на своей родословной.
Результаты: схема 1

Методика 2.
Цель: проверить выполнение ’’Графов’’ на родословной князей Голицыных.
Результат: схема 2
Вывод: я заметил, что родословная – типичный граф.

IV.ЗАКЛЮЧЕНИЕ

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

V.Литература.

1.Энциклопедический словарь юного математика / Сост.А.П.Савин.- М.: Педагогика, 1989

2. Квант № 6 1994Г.

3. М. Гарднер «Математические досуги» М.: Мир,1972

4.В.А.Гусев, А. И.Орлов, А.А.Розенталь ’’Внеклассная работа по математике’’
5. И.Семакин’’ Информатика’’

Кучин Анатолий Николаевич

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

Куклина Татьяна Ивановна

Учреждение:

МБОУ "Основная общеобразовательная школа" п. Троицко-Печорск Респ. Коми

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

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

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

Введение
Глава 1. Знакомимся с графами
1.1. История графов.
1.2. Виды графов
Глава 2. Возможности применения теории графов в различных областях повседневной жизни
2.1. Применение графов в различных областях жизни людей
2.2. Применение графов при решении задач
2.3. Генеалогическое древо – один из способов применения теории графов
2.4. Описание исследования и составление генеалогического древа моей семьи
Заключение
Использованная литература
Приложения

«В математике следует помнить не формулы,
а процесс мышления».
Е.И. Игнатьева

Введение

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

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

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

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

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

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

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

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

Для реализации поставленной цели, мною были выдвинуты следующие задачи:

1. познакомиться с историей теории графов;
2. изучить основные понятия теории графов и виды графов;
3. рассмотреть способы решения задач с помощью графов;
4. показать применение теории графов в различных областях жизни человека;
5. создать генеалогическое древо моей семьи.

Методы: наблюдение, поиск, отбор, анализ, исследование.

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

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

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

Результаты решения задач таковы:
Всего 15 учащихся (5 класс – 3 ученика, 6 класс - 2 ученика, 7 класс – 3 ученика, 8 класс - 3 ученика, 9 класс - 4 ученика) применили теорию графов в 1 задаче – 1, во 2 задаче – 0, в 3 задаче – 6, в 4 задаче – 4 учащихся.

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

Цель исследования :

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

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

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

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

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

Актуальность исследования:

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

Гипотеза:

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

Содержание:

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

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

Основные понятия теории графов и их доказательства.

Избранные задачи.

Хроматическое число графа.

Литература.

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

Любой из нас, конечно, прав,

Найдя без проволочек,

Что он…обыкновенный граф

Из палочек и точек.

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

В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами. Один из графов хорошо знаком москвичам и гостям столицы – это схема московского метрополитена: вершины – конечные станции и станции пересадок, рёбра – пути, соединяющие эти станции. Генеалогическое древо графа Л. Н. Толстого – ещё один граф. Здесь вершины – предки писателя, а рёбра показывают родственные связи между ними.

рис.1 рис. 2

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями.При изображении графа не имеет значения расположение вершин на плоскости, кривизна и длина рёбер (рис.3).Вершины графов обозначаются буквами или натуральными числами. Ребра графа – пары чисел.

рис. 3

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

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

Но кто придумал эти графы? Где они применяются? Все ли они одинаковые или есть разновидности?

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

Основы теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кёнигсбергских мостах. «Мне была предложена задача об острове, расположенном в городе Кёнигсберге и окружённом рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто – нибудь непрерывно обойти их, проходя только однажды через каждый мост…» (Из письма Л. Эйлера итальянскому математику и инженеру Маринони от 13 марта 1736 года)

Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены (рис.4). Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз. Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход, он начертил упрощённую схему мостов. Получился граф, вершины которого – части города, разделённые рекой, а рёбра – мосты (рис.5).

рис. 4 рис. 5

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

из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (графы, удовлетворяющие этому требованию, называются связными);

из каждой вершины должно выходить чётное количество рёбер.

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

рис. 6

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

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

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

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

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

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

Понятие эйлерова и гамильтонова циклов.

Замкнутый путь, проходящий по одному разу по всем рёбрам, до сих пор называют эйлеровым циклом.

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

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

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

рис. 7 а) б)

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

В 1859 г. сэр Вильям Гамильтон, знаменитый ирландский математик, давший миру теорию комплексного числа и кватерниона, предложил необычную детскую головоломку, в которой предлагалось совершить «кругосветное путешествие» по 20 городам, расположенным в различных частях земного шара (рис. 8). В каждую вершину деревянного додекаэдра, помеченную названием одного из известных городов (Брюссель, Дели, Франкфурт и т. д.), был вбит гвоздик и к одному из них была привязана нить.Требовалось соединить вершины додекаэдра этой нитью так, чтобы она проходила вдоль его ребер, обвивая каждый гвоздик ровно один раз, и чтобы полученный в результате ниточный маршрут был замкнутым (циклом).Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b ... t. Обязательным условием было требование посетить каждый город, за исключением первого, лишь один раз.

рис. 8 рис. 9

Если путешествие начать из города a, то последними должны быть города b, e или h, иначе мы не сможем вернуться в первоначальный пункт a. Непосредственное исчисление показывает, что число таких замкнутых маршрутов равно 60.Можно потребовать посещения всех городов строго по одному разу, включая и первый, т.е. допускается окончание путешествия в любом городе (например, предполагается, что в начальный пункт можно будет вернуться самолетом). Тогда общее число цепных маршрутов увеличится до 162 (рис.9).

В этом же, 1859 году Гамильтон предложил владельцу фабрики игрушек в Дублине запустить её в производство. Владелец фабрики принял предложение Гамильтона и выплатил ему 25 гиней. Игрушка напоминала «кубик Рубик», ещё не так давно пользующегося огромной популярностью, и оставила заметный след в математике. Замкнутый путь по рёбрам графа, проходящий по одному разу через все вершины, называется гамильтоновым циклом. В отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.

Понятие полного графа. Свойства плоских графов.

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

рис. 10 рис. 11

На рисунке 10 изображён граф с пятью вершинами, который не укладывается на плоскость без пересечения рёбер. Каждые две вершины этого графа соединены ребром. Это полный граф. На рисунке 11 – граф с шестью вершинами и девятью рёбрами. Он носит название «домики – колодцы». Оно произошло от старинной задачи – головоломки. В трёх избушках жили трое друзей. Около их домиков находились три колодца: один с солёной водой, второй – со сладкой, третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по- новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать? На рисунке 12 проведено восемь из девяти тропинок, но провести девятую уже не удаётся.

рис.12

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

Льюис Кэрролл, автор книги «Алиса в стране чудес», любил давать своим знакомым следующую головоломку. Он просил обвести фигуру, изображённую на рисунке, не отрывая карандаша от бумаги и не проводя дважды по одной линии. Подсчитав чётность вершин, убеждаемся, что эта задача легко решается, причём начинать обход можно с любой вершины, так как они все чётные. Однако, он усложнял задачу тем, что требовал, чтобы при обводке линии не пересекались. Справиться с этой проблемой можно следующим способом. Раскрасим фигуру так, чтобы её граничащие части оказались разного цвета. Затем разъединим пересекающиеся линии таким образом, чтобы закрашенная часть представляла из себя единый кусок. Теперь остаётся обвести по краю одним росчерком закрашенную область – это и будет искомая линия (рис. 13).

рис. 13

Основные понятия теории графов и их доказательства .

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

В – P + Г = 2.

1. Определение . Число рёбер, выходящих из одной вершины, называют степенью этой вершины.

Лемма1. Число рёбер в графе ровно в 2 раза меньше, чем сумма степеней вершин.

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

Лемма2 . Сумма степеней вершин графа чётна .

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

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

Лемма3 . Число нечётных вершин графа чётно.

Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.

Лемма 4. Если полный граф имеет n вершин, то количество ребер будет равно

Доказательство. В полном графе с n вершинами из каждой вершины выходит по n -1 рёбер. Значит, сумма степеней вершин равна n ( n -1). Число рёбер в 2 раза меньше, то есть .

Избранные задачи.

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

Задача 1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

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

Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.

Задача 2. В 10-значном числе каждые две подряд идущие цифры образуют двузначное число, которое делится на 13. Докажите, что среди этих цифр нет цифры 8.

Решение. Существует 7 двузначных чисел, которые делятся на 13. Обозначим эти числа точками и применим определение графа. По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так, чтобы цифры, входящие в этот граф повторялись.

13 65

91 39 52

Из построенных графов видно, что среди цифр 10-значного числа цифры 8 быть не может.

Задача 3. В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

Решение. Пусть дома - вершины графа, тропинки - рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70: 2= 35. Таким образом между домами проходит 35 тропинок.

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

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

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

Классическая «задача коммивояжёра». «Жадные» алгоритмы.

Одна из классических задач теории графов называется «задачей коммивояжёра» или «задачей о бродячем торговце». Представим себе торгового агента, который должен побывать в нескольких городах и вернуться обратно. Известно, какие дороги соединяют эти города и каковы расстояния между этими городами по данным дорогам. Нужно выбрать самый короткий маршрут. Это же не «игрушечная» задача. Например, водитель почтового автомобиля, вынимающий письма из почтовых ящиков, очень хотел бы знать кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам. А решить эту задачу довольно – таки сложно, потому что число вершин графа очень велико. А вот другая задача, в некотором смысле противоположная задаче коммивояжёра. Предполагается проложить железную дорогу, которая соединит несколько крупных городов. Для любой пары городов известна стоимость прокладки пути между ними. Требуется найти наиболее дешёвый вариант строительства. На самом деле алгоритм нахождения оптимального варианта строительства довольно прост. Продемонстрируем его на примере дороги, соединяющей пять городов А, В, С, D и Е. Стоимость прокладки пути между каждой парой городов указана в таблице (рис.14), а расположение городов на карте (рис.15)

1,5

2,5

1,5

1,2

0,8

1,2

1,1

0,9

1,1

2,7

2,5 5

ис.е, а расположеие городов аждой паройдов А, В С тагрузовика, разво

0,8

0,9

2,7

А А

D D

рис.14 рис. 15

Сначала строим ту дорогу, которая имеет наименьшую стоимость. Это маршрут В →Е. Теперь найдём самую дешёвую линию, соединяющую В или Е с каким-нибудь из городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично – ищем самый дешёвый из путей, соединяющих один из городов В, С, Е с одним из оставшихся – А или D . Это дорога между С и А. Осталось подключить к железнодорожной сети город D .

Дешевле всего соединить его с С. Получим сеть железнодорожных путей (рис. 16).

рис. 16

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

Итак, для решения некоторых задач можно использовать метод или алгоритм, который называется «жадным». «Жадный» алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. Посмотрим, как поведет себя при решении задачи о коммивояжёре «жадный» алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рисунке 17, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых ситуациях «жадный» алгоритм определяет-таки кратчайший путь.

4 3

рис. 17

Есть ещё один метод для решения подобных задач - метод полного перебора (иногда говорят Метод перебора, подразумевая при этом полный перебор - это не совсем правильно, так как перебор может быть и не полным), который заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной. Существуют и другие алгоритмы для решения задачи коммивояжера, которые значительно точнее «жадного» алгоритма и значительно быстрее метода полного перебора. Однако мы рассматриваем графы, а эти методы не связаны с теорией графов.

Хроматическое число графа.

Задача о раскраске географической карты

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

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

Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить такую проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную географическую карту так, чтобы любые две страны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат (рис.18), то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ.

рис. 18

Игра «четыре краски»

Стивен Барр предложил логическую игру на бумаге для двух игроков, названную «Четыре краски». По словам Мартина Гарднера - «Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру»

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

Комбинаторные и логические задачи.

В 1936 году немецкий математик Д. Кёниг впервые провёл исследование подобных схем и предложил называть такие схемы «графами» и систематически изучать их свойства. Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д. Наиболее близки к графам – топология и комбинаторика.

Комбинато́рика (Комбинаторный анализ) - раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики - алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике). Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Широкое развитие теория графов получила с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники. И з современных математиков над графами работали - К. Берж, О. Оре, А. Зыков.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю. Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0),если наполним водой большую кастрюлю, или (5,0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

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

Задача №1. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

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

Ответ: 6 партий.

Задача №2. Андрей, Борис, Виктор и Григорий подарили на память друг другу свои фотографии. Причём каждый мальчик подарил каждому из своих друзей по одной фотографии. Сколько всего фотографий было подарено?

Решение найдётся легко, если начертить граф:

1 способ. С помощью стрелок на рёбрах полного графа показан процесс обмена фотографиями. Очевидно, что стрелок в 2 раза больше, чем рёбер, т.е. 12.

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

Ответ: 12 фотографий.

Задача № 3. Известно, что у каждой из трех девочек фамилия начинается с той же буквы, что и имя. У Ани фамилия Анисимова. У Кати фамилия не Карева, а у Киры – не Краснова. Какая фамилия у каждой из девочек?

Решение:По условию задачи составим граф, у которого вершины – имена и фамилии девочек. Сплошная линия будет обозначать, что девочке соответствует данная фамилия, а пунктирная – что не соответствует. Из условия задачи видно, что у Ани фамилия Анисимова (соединяем сплошной линией две соответствующие точки). Из этого следует, что у Кати и у Киры фамилия не Анисимова. Так как Катя – не Анисимова и не Карева, значит она Краснова. Остается, что у Киры фамилия Карева. Ответ: Аня Анисимова, Катя Краснова, Кира Карева.

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

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

Задача № 4.Поступающий на физмат должен сдать три вступительных экзамена по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов?

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

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

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

Задача № 5. На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?

Решение:

нет

да

нет

да

Ответ: первый ответ - "да", второй ответ - "нет" - мудрец встретил двух плутов.

Заключение. Приложение теории графов в различных областях науки и техники.

Инженер чертит схемы электрических цепей.

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

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

Что общего во всех этих примерах? В каждом из них фигурирует граф.

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

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

Литература.

«Энциклопедия для детей. Т.11. Математика» /Глав.ред. М.Д.Аксёнова/ Издательский центр «Аванта+», 1998.

«За страницами учебника математики» Сост. С. А. Литвинова. -2-е изд., дополненное. – М.:Глобус, Волгоград: Панорама, 2008.

Графы // Квант. -1994.- № 6.

Математические головоломки и развлечения. М. Гарднер. – М.: «Мир», 1971.

Зыков А.А. Основы теории графов М.: Вузовская книга, 2004.

Мельников О.И. Занимательные задачи по теории графов Издательство: ТетраСистемс, 2001.

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

Материалы из Википедии - свободной энциклопедии.