Оглавление (стр. 1 )

Оглавление

1.        Введение        2

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

2.1 Введение        2

2.2 Полный граф. Дополнение графа.        7

2.3 Степень вершины.        8

2.4 Связность графа        10

2.5 Представление о плоском графе        11

2.6 Формула Эйлера        12

2.7 Эйлеровы графы        13

2.8  Сетевое планирование и управление        15

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

(Авторские задачи)        15

3.1 Графы в психологии        15

3.2 Графы в структуре управления        18

3.3. Графы в маркетинге        19

3.4  Графы в школьной программе        20

Программа элективного курса “Элементы теории графов и использование граф - моделей к решению задач ”        20

3.5 Практическая часть курса        23

4 Заключение        28

5 Литература        28

Введение

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

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

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

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

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

2.1 Введение

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

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

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

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

  Что общего во всех этих примерах? В каждом из них фигурирует схема, состоящая из точек(они обозначают разветвления  электрической цепи, атомы, людей, города и т. д.), соединённых между собой линиями. 

  Для общего представления рассмотрим несколько простейших примеров:

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

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

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

Задача 2. В одном городе шесть станций метро: Алмазная, Золотая, Лесная, Парковая, Садовая, Серебряная. Поезда следуют по маршрутам Алмазная – Золотая, Золотая – Серебряная, Лесная – Садовая, Садовая – Парковая, Парковая – Лесная, Серебряная – Алмазная. Можно ли с помощью этих поездов добраться до станции Парковая до станции Алмазная?

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

Задача 3. В государстве 24 города. Может ли быть так, что 8 из них соединены с тремя городами, 11 – с пятью городами, а 5 – с четырьмя городами?

Решение: В этой задаче идет речь о том, что можно ли построить  граф, имеющий 24 вершины, причем 8 из них соединены с тремя вершинами, 11 – с пятью вершинами, а 5 – с четырьмя вершинами. Сосчитаем, сколько ребер должно быть у такого графа. Для этого найдем  сумму: 8*3+11*5+5*4=24+55+20=99 (по три ребра выходит из каждой вершины первого сорта, по пять из каждой вершины второго сорта и по четыре – из каждой вершины третьего сорта). Очевидно, что мы считали каждое ребро дважды –ведь оно соединяет две вершины. Поэтому ребер должно быть  99:2 = 49,5. Но число ребер не может быть не целым. Получено противоречие. Такой граф построить невозможно.

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

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

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

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

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