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

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

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

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

2010 г.

СОДЕРЖАНИЕ

Введение

Глава I. Графы и их применение

§ 1. Основные понятия теории графов

§ 2. Расстояния в графах. Диаметр, радиус, центр графа

§ 3. Нагруженные графы. Определение кратчайших маршрутов

§ 4. Раскраска графов. Применение раскраски графов в практической деятельности человека

§ 5. Эйлеровы и гамильтоновы графы

Глава II. Элементы теории графов на факультативных занятиях в школе

§ 1. Роль факультативных занятий

§ 2. Постановка факультатива «Элементы теории графов в средней школе

Заключение

Литература

ВВЕДЕНИЕ

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

 Рис. 1                                                                Рис. 2

Но для огромного (и все возрастающего) числа математиков слово «граф» означает нечто совсем иное.

Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако, эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен, главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это, благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развития формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач - проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

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

Настоящая работа состоит из двух глав.

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

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

Раздел теоретического изложения материала подкреплен практическими задачами и упражнениями.

Глава I. ГРАФЫ И ИХ ПРИМЕНЕНИЕ

§ 1. Основные понятия теории графов

Пусть дано множество V = {v1, v2,…,vn} и пусть на множестве V определено семейство U = {u1, u2, …, un} пар элементов Uk = {vi, vj}, (k=1, m) произвольной кратности и упорядочения. Пара {V, U} называется графом. Граф, как правило, обозначают прописными латинскими буквами, например G, H. Принято также писать G (V, U) для того, чтобы определить некоторый конкретный граф G.

Элементы v1, v2,…, vn называют вершинами графа, а пары Uк = {vi, vj},

(к = 1, m) - ребрами.

Определению графа можно дать такую интерпретацию. Пусть имеем описание графа:

(V, U) = {{v1, v2,…, v6}, {{v1, v3}, <v5, v1>, {v3, v4}, <v2, v3>, {v3, v3}}}.

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

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

Рис. 3

Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу, а конечная - в конце. Так, на рис.3 ребра <v5, v1> и <v2, v3> являются дугами. Они представлены упорядоченными парами вершин и в связи с этим обозначены также, как обозначаются упорядоченные множества.

Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi}. Ребро {vi, vi} называется петлей. На рис.3 имеем петлю {v3, v3}. Петли обычно неориентированы.

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

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

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

На рис.3 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.

Некоторые вершину графа G могут не войти в список пар. Такие вершины называются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто.

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

Как в случае ориентированного графа, так и в случае неориентированного, говорят, что ребро инцидентно паре определяющих его вершин.

Одной и той же паре вершин можно поставить в соответствии множество инцидентных ребер. Такие ребра называются кранными. Так, на рис.4 представлены различные пары вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два - нет.

Рис. 4

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

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

Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (G) графа G и все ребра U являются ребрами G. Частным, но важным типом частичных графов являются подграфы.

Пусть А - подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами - все ребра из G, оба конца которых лежат в А.

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

Например, граф G на рис.5 неполный. А проведенные недостающие ребра составляют граф дополнение G рис.6.

Рис. 5                                                                 Рис. 6

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

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

Обозначать степени вершин v1, v2, v3 будем так: δ (v1), δ (v2), δ (v3) и т.п.

У графа на рис.7 δ (v1) = 1; δ (v2) = 2. У графа на рис. 8 степени всех вершин равны нулю.

         Рис. 7                                                        Рис. 8

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

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

Пусть имеем граф G (V, U). Его матрицей смежности называется квадратная матрица (аi, j) порядка n2, где n - число вершин, а аi, j - число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то аi, j = 1, когда vi и vj смежные, и аi, j = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю.

Рассмотрим примеры. На рис. 9 изображены три неориентированных графа. В первом случае (рис.9а) имеем граф без петель и без кратных ребер. Во втором случае (рис.9б) имеем кратные ребра. В третьем случае (рис.9в) в вершинах v1 и v4 имеются петли.

 а                                            б                                    в

Рис. 9

Соответствующие этим трем случаям матрицы смежности представлены ниже:

а)                      б)                      в)

Для неориентированного графа матрица смежности является симметрической. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является.

Матрицей инциденций неориентированного графа, называется матрица (bi,j) размера n · m, где n - число вершин, а m - число ребер, построенная по правилу

Соответствующие рис.9б матрицы инциденций представлены ниже.

Примечание: для графа на рис. 9б приняты следующие обозначения ребер: Х1 = (v1, v2)1, Х2 = (v1, v2)2, Х3 = (v1, v4)1, Х4 = (v1, v4)2, Х5 = (v1, v4)3, Х6 = (v2, v4), Х7 = (v3, v2).

Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:

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

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

Матрицей инциденций ориентированного графа называется матрица (bi, j) размера n · m, где n - число вершин, а m - число ребер, построенная по правилу

Рассмотрим, например, граф, изображенный на рис.10.

Рис. 10

Построенная в соответствии с описанным правилом матрица инциденций этого графа имеет вид

Примечание: для графа на рис.10 приняты следующие обозначения дуг: Х1 = (v1, v2), Х2 = (v1, v3), Х3 = (v3, v2), Х4 = (v3, v4), Х5 = (v5, v4), Х6 = (v5, v6), Х7 = (v6, v5).

Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра.

Задачи, возникающие на практике, приводят к разного вида операциям над матрицами. Рассмотрим некоторые из них.

Пусть система авиалиний между городами Х1, Х2, Х3 одной страны и городами У1 и У2 другой страны задается подмножеством пар: (Х1, У1), (Х1, У2), (Х2, У1), (Х2, У2), (Х3, У2), т.е. множеством ребер соответствующего графа. Система связи между этими же городами водным транспортом задается другим подмножеством пар: (Х1, У1), (Х2, У1), (Х2, У2), (Х3, У1). Кроме этого, для каждой пары городов (Хi, Уj). Известно число различных водных и авиамаршрутов. Эти числа можно проставить над ребрами на рисунке графа или зафиксировать с помощью двух матриц одинакового порядка:

У1 У2                                     У1 У2

Х1 4 1                            Х1 2 0

А = Х2 2 6           В = Х2 1   3

Х3 0 4                            Х3 2 0

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

Естественно, что для этого достаточно сложить соответствующие элементы матриц А и В. Ответ можно записать с помощью новой матрицы того же порядка:

У1     У2

Х1 6  1

С = Х2 3 9

Х3 2 4

В общем случае операцию сложения двух матриц можно записать так: если А = (аi,j) и В = (bi,j) - матрицы одного порядка, то матрица С = А + В = (Сi,j), где Сi,j = аi,j + bi,j.

Рассмотрим еще одну задачу. Пусть в каких-то трех странах выделены некоторые города, связанные с транспортом четырех видов: воздушным, железнодорожным, водным и автобусным. Схема транспортных связей между городами Х1 и Х2, принадлежащими первой стране, и городами У1, У2, У3, принадлежащими второй стране, зафиксирована матрицей А, где аi,j показывает на число видов транспорта, соединяющих города Хi и Уi. Аналогичная схема транспортных связей между городами У1, У2, У3, принадлежащими второй стране, и городами Z1, Z2, принадлежащим третьей стране, представлена матрицей В. Какие конкретно виды транспорта связывают пары городов, нас не интересует. Города первой и третьей стран непосредственных связей не имеют.

У1 У2         У3                                Z1 Z2

А = Х1 4 0 2                           У1 2 1

Х2 2 3         1               В = У2 0   3

У3 3  0

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

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

Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С:

1        Z2

C = Х1 С11 С12

Х2 С21 С22

Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно

Z1                                           Z2

C = Х1 (а11в11 + а12в21 + а13в31            а11в12 + а12в22 + а13в32

Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32

Z1     Z2

C = Х1 14 4

Х2 7 11

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

Если С = АВ, то элементы матрицы С определяются следующей формулой:

сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj

Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В.

Следует обратить внимание на следующие два факта:

) операция умножения матрицы А на матрицу В определена только в том случае, если число столбцов в матрице А равно числу строк в матрице В.

) если матрица А имеет порядок (m x n), а матрица В - порядок (n x r), то матрица - произведение С = АВ имеет порядок (n x m).

Рассмотрим некоторые основные операции, производимые над графами.

Операцией добавления к графу G = <V, U> вершины а образуется граф <V u {a}, U>.

Операцией добавления дуги (а, в) к графу G состоит в образовании графа <V u {a, в), U u {(а, в)}>. При операции удаления дуги, получаем <V, U \ {(а, в)}>. Операции удаления вершины заключается в удалении вершины Vi вместе с инцидентными ей дугами: <V\{Vi}, U \ {(Vj Vk) Vj = Vi или Vk = Vi}>. Операция отождествления вершин (в случае, когда Vi и Vj соединены дугой, операцию называют стягиванием дуги (ViVj).

Пример:

Рис. 11

Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) - G2, удалением дуги (3, 2) - G3, удалением вершины 2 - G4, отождествлением вершин 1 и 4 - G5 , стягиванием дуги (2, 3) - G6.

Добавлением графа без петель G = <V, U> называется граф = <V, V2 \ (U u i av)>.

Рис. 12

Объединением G1 u G2 называется граф <V1 u V2, U1 u U2>.

Если V1 ∩ V2 ≠ Ø, то пересечением G1 ∩ G2 называется граф <V1 ∩ V2, U1 ∩ U2 >.

Кольцевой суммой G1 + G2, называется граф <V1 u V2, (U1 \ U2) u (U2 \ U2).

Соединением G1 + G2 называется <V1 u V2, U1 u U2 u {[Vi, Vj] | Vi є V2, Vi ≠ Vj}>.

Произведением G1 x G2 называется граф <V1 x V2, U>.

Композицией G1 [G2] называется граф <V1 x V2, U>, в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2.

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

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

                   Рис. 14                                             Рис. 15

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

Пример леса показан на рис.15.

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

Теорема: дерево с n вершинами имеет n-1 ребро.

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

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

Рис. 16

Ответ: 8 способами

Рис. 17

§ 2. Расстояния в графах. Диаметр, радиус, центр графа

Пусть G = <V, U> - связный неорграф, Vi, Vj - две его несовпадающие вершины.

Длина кратчайшего (Vi, Vj)-маршрута называется расстоянием между вершинами Vi и Vj и обозначается через ρ (Vi, Vj).

Положим ρ (Vi, Vj) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1) ρ (Vi, Vj) ≥ 0;

2) ρ (Vi, Vj) = 0 ↔ Vi = Vj

3) ρ (Vi, Vj) = ρ (Vi, Vj) - симметричность

4) ρ (Vi, Vj) ≤ ρ (Vi, Vj) + ρ (Vj, Vк) - неравенство треугольника.

Если V = {V1, V2,…, Vn}, то матрица Р = (рi,j) = ρ (Vi, Vj), называется матрицей расстояний (где матрица Р симметрична).

Для фиксированной вершины V величина Е (v) = мах { ρ (Vi, Vj) | Vj є V} называется эксцентриситетом вершины V. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.

Если Р-матрица расстояний, то эксцентриситет Е (Vi) равен наибольшему из числе, стоящих в i-й строке.

Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d (G) : d (G) = vf[ {E(v) | v є V}. Вершина V называется периферийной, если Е (v) = d (G).

Рассмотрим пример. Найдем диаметр графа G, изображенный на рис.18. Матрица расстояний Р имеет вид:

Рис. 18

Отсюда Е (1) = 3, Е (2) = 2, Е (3) = 3, Е (4) = 2, Е (5) = 2 и, следовательно, d (G) = 3. Вершины 1 и 3 являются периферийными.

Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r (G) : r (G) = min {E (vi) | vi є V}.

Вершина V называется центральной, если Е (v) = r (G).

Множество всех центральных вершин графа называется его центром.

Рассмотрим соответствующий пример. Радиус графа, показанного на рис.18, равен 2, а его центром является множество {2, 4, 5}.

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

Дерево - одно из наиболее часто встречающихся в теории графов понятий (рис.19).

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

Корневую вершину нетрудно также выделить у деревьев на рисунках 20, 21, 22.

В первом случае корневой вершиной является единственная вершина графа А, во втором - вершина С, в третьем (такое дерево, все вершины которого, кроме одной, висячие, называют «звездой») - вершина А. Но какие вершины считать корневыми в графах, которые изображены на рисунках 23, 24 и 25?

Естественно считать, что все эти три дерева имеют по две корневые вершины. У дерева на рисунке 23 - это А и В, у дерева на рисунке 24 - это С и Д, у дерева на рисунке 25 - это А и В.

Расстоянием d (Vi, Vj) между вершинами Vi и Vj графа G называют длину кратчайшего пути, их соединяющего. (Если граф G-дерево, то путь соединяющий вершины Vi и Vj, единственный).

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

Наибольшее из таких чисел называют диаметром графа (в данном случае дерева), наименьшее - радиусом графа.

Вершины дерева, для которых максимальное из расстояний до других вершин равно радиусу, называются корневыми. Для дерева, изображенного на рисунке 26, диаметр равен 5, а радиус равен 3; корневые вершины - А и В.

Задача. Подсчитайте диаметр и радиус графа, изображенного на рисунке:

а) 18;          б) 24;          в) 25.

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

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

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

В построенном графе можно перейти по ребрам от любой вершины к любой другой, и в нем нет циклов. Такой граф называется деревом. Пусть молекула содержит n атомов углерода и m атомов водорода, тогда граф будет содержать n + m вершин. Далее, при решении задачи воспользуемся легко доказываемым соотношением: в дереве число ребер на единицу меньше числа вершин. Следовательно, в графе n + m - 1 ребер. Из вершин графа, обозначающих атомы углерода, выходит по 4 ребра, а из вершин, обозначающих атомы водорода, - одно. Используя простой факт, что сумма степеней вершин, т.е. сумма числа ребер, можно написать соотношение: 4n + m = 2 (n + m - 1). Отсюда получаем, что m = 2n + 2. Следовательно, формула насыщенного углеводорода, имеющего n атомов углерода: Сn H2n+n.

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

К числу предельных (не имеющих цикла) углеводородов относится, например пентан С5Н12. Его структурная формула изображена на рисунке 28. Этой формуле можно поставить во взаимно однозначное соответствие однокорневое дерево (рис. 29), показывающее взаимное расположение только атомов углерода в молекуле пентана. Но тем самым определяется однозначно и расположение атомов водорода в этой молекуле. На рисунке 30 представлена структурная формула молекулы одного из изопентанов, а на рисунке 31 соответствующее ей двукорневое дерево.

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

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

§3. Нагруженные графы. Определение кратчайших маршрутов

Пусть G = <V,U>- взвешенный граф, имеющий n вершин и матрицу весов W = (wij), wij € R, где вес каждой дуги (Vi, Vj) есть некоторое вещественное число μ(Vi, Vj).

Весом маршрута V1, V2, Vn, Vn+1 называется число μ.

Взвешенным расстоянием (w-расстоянием) ρω(Vi,Vj) между вершинами Vi и Vj называется минимальный из весов Vi,Vj маршрутов.

(Vi,Vj) - маршрут, вес которого равен расстоянию ρω(Vi,Vj) , называется кратчайшим (Vi,Vj) - маршрутом во взвешенном графе G.

Взвешенным эксцентриситетом Eω(Vi) вершины Vi называется число max{ ρω(Vi,Vj)│Vj €V}

Взвешенной центральной вершиной графа G, называется вершина Vj , для которой Eω(Vi)=min{ Eω(Vi)│Vj €V}

Взвешенным эксцентриситет центральной вершины называется радиусом графа G и обозначается через rw(G).

Опишем некоторые методы нахождения взвешенного расстояния от фиксированной вершины Vj €V (называемой источником) до всех вершин графа G.

Т.е. G = <V,U>, μ(Vi, Vj) - вес дуги, Vi=Vj, μ(Vi, Vj)= 0. μ - вес маршрута. W = (wij) - матрица весов, (wij)= μ(Vi, Vj), если Vi, Vj€ U; (wij)=00, если (Vi, Vj ) U

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

Определим алгоритм Форда-Белмиана.

Зададим строку  полагая  В этой строке  есть вес дуги , если  существует, и  если

Определим строку  полагая dj(2) = min {dj(1), dk(1) + ωkj}k=1,…n

Нетрудно заметить, что dj(2) - минимальный из весов (Vi, Vj) - маршрутов, состоящий не более, чем из двух дуг (рис. 35).

Продолжая процесс, на шаге S определим строку Д(s) = (d1(s), d2(s),…, dn(s)), полагая dj(s)= min { dj(s-1), dk(s-1) + ωkj}k=1,…n

Искомая строка ω-расстояний получается при s = n - 1 : dj(n-1)= ρω (Vi, Vj). Действительно, на этом шаге из всех весов (Vi, Vj) -маршрутов, содержащих не более (n-1) дуг, выбирается наименьший, а каждый маршрут более чем с (n-1) дугами содержит контур, добавление которого к маршруту не уменьшает ω-расстояния, т.к. было предположение отсутствия контуров отрицательного веса.

Работу алгоритма можно завершить на шаге к, если Д(к) = Д(к+1).

Пример: Продемонстрируем работу алгоритма Форда-Беллмана. На примере взвешенного графа, показанного на рис.36 с матрицей весов.

В качестве источника выберем Т - {1}, тогда

Д(1) = (0, 1, ∞ , ∞, 3),                      min маршрут сост. 1 дуги

Д(2) = (0, 1, 4, 4, 3),                         не более 2 дуг

Д(3) = (0, 1, 4, 4, -1),                        3 дуг

Д(4) = (0, 1, 4, 3, -1).                        4 дуг

Таким образом, ρω (1, 1) = 0, ρω (1, 2) = 1, ρω (1, 3) = 4, ρω (1, 4) = 3, ρω (1, 5) = -1.

Зная расстояние от источника Vi до всех остальных вершин графа, можно найти и сами кратчайшие (Vi, Vj) -маршруты. Действительно, пусть Vi, b1, b2, …, br, Vj - кратчайший (Vi, Vj) -маршрут. Тогда по строке Д(n-1) вершина br = Vk2 находится из соотношения

ρω (Vi, Vj) = ρω (Vi, Vк1) + ωк1j, вершина br-1 = Vк2 из

ρω (Vi, Vк1) = ρω (Vi, Vк2) + ωк2к1 и т.д.

В предыдущем примере кратчайший (1, 4)-маршрут определяется следующим образом: ρω (1, 4) = 3 = -1 + 4 = ρω (1, 5) + ω54, тогда br = 5; ρω (1, 5) = -1 = 4 - 5 = ρω (1, 3) + ω3,5, откуда br-2 = b2 = 3, br-3 = b1 = 2. Таким образом, кратчайший (1,4)-маршрут задается последовательностью вершин (1, 2, 3, 5, 4).

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

Алгоритм Дейкстры:

-источник

Т1 = {2, 3, 4, 5, 6}

Д(1) = {0, 1, ∞, ∞, ∞, ∞}

-источник

Т2 = {3, 4, 5, 6}

Д(2) = {0, 1, 6, 3, ∞, ∞}

Д(1) = {d1(1), d2(1), d3(1), d4(1), d5(1), d6(1)}

d1(1) = 0, dj(1) = ωij.

Д(2) = {d1(2), d2(2), d3(2), d4(2), d5(2), d6(2)}

dj(2) = min {dj(1), dk(1) + ωkj}, k = 1, 2, …, n

d2(2) = min {d2(1), dk(1) + ωk2} = min {1, 0 + 1} = 1

d3(2) = min {d3(1), dk(1) + ωk3} = min {∞, 1 +5} = 6

d4(2) = min {d4(1), d2(1) + ω24} = min {∞, 1 + 2} = 3

d5(2) = min {∞, d6(1) + ω65} = {∞, ∞} = ∞

d6(2) = min {∞, ∞ + ω36} = ∞

_______________________________

Д(3) = {d1(3), d2(3), d3(3), d4(3), d5(3), d6(3)}

T3 = {3, 5, 6} 4 - источник

Д(3) = {0, 1, 4, 3, 7, 8}

d3(3) = min {d3(2), d4(2) + ω43} = min {6, 3 + 1} = min {6, 4} = 4

d4(3) = min {3, d2(2) + ω24} = min {3, 1 + 2} = 3

d5(3) = min {∞, d6(2) + ω65} = {∞, d4(2) + ω45} = min {∞, 3 + 4} = 7

d6(3) = min {∞, d2(2) + ω36} = min {∞, 1 + 7} = 8

Д(4) = {d1(4), d2(4), d3(4), d4(4), d5(4), d6(4)}

T4 = {5, 6}

Д(4) = {0, 1, 4, 3, 7, 5}

d4(4) = min {d4(3), d2(3) + ω23} = min {3, 1 + 5} = 3

d5(4) = min {d5(3), d6(3) + ω65} = 3

d6(4) = min {d6(3), d3(3) + ω36} = min {8, 4 + 1} = 5

T5 = {5}

Д(5) = {d1(5), d2(5), d3(5), d4(5), d5(5), d6(5)}

Д(5) = {0, 1, 4, 3, 6, 5}

d4(5) = min {d4(4), d2(4) + ω24} = min {3, 1 + 2} = 3

d5(5) = min {d5(4), d6(4) + ω65} = min {7, 5 + 1} = 6

d6(5) = min {d6(4), d3(4) + ω36} = min {5, 4 + 1} = 5

ρω (1, 1) = 0

ρω (1, 2) = 1

ρω (1, 3) = 4

ρω (1, 4) = 3

ρω (1, 5) = 6

ρω (1, 6) = 5

Минимальный путь из V1 до V7

-источник Т1 = {2, 3, 4, 5, 6, 7}

Д(1) = {0, ∞, 5, 4, 2, 2, 9}

-источник  Т2 = {2, 3, 4, 6, 7}

Д(2) = {0, ∞, 4, 4, 2, 2, 8}

d2(2) = min {d2(1), d5(1) + ω52} = min {∞, 2 + ∞} = ∞

d3(2) = min {d3(1), d5(1) + ω53} = min {5, 2 +2} = 4

d4(2) = min {d4(1), d5(1) + ω54} = min {4, 2 + 2} = 4

d5(2) = min {d5(1), d5(1) + ω56} = min {2, 2 + 0} = 2

d6(2) = min { d6(1), d5(1) + ω56} = min {2, 2 + 1} = 2

d7(2) = min { d7(1), d5(1) + ω57} = min {9, 2 + 6} = 8

-источник Т3 = {2, 3, 4, 7}

Д(3) = {0, 7, 4, 3, 2, 2, 8}

d2(3) = min {d2(2), d6(2) + ω62} = min {∞, 2 + 5} = 7

d3(3) = min {d3(2), d6(2) + ω63} = min {4, 2 + ∞} = 4

d4(3) = min {d4(2), d6(2) + ω64} = min {4, 2 + 1} = 3

d5(3) = min {d5(2), d6(2) + ω65} = min {2, 2 + 1} = 2

d6(3) = min {d6(2), d6(2) + ω66} = min {2, 2 + 0} = 2

d7(3) = min {d7(2), d6(2) + ω67} = min {8, 2 + ∞} = 8

-источник Т4 = {2, 3, 7}

Д(4) = {0, 5, 4, 3, 2, 2, 8}

d2(4) = min {d2(3), d4(3) + ω42} = min {7, 3 + 2} = 5

d3(4) = min {d3(3), d4(3) + ω43} = min {4, 3 + 1} = 4

d4(4) = min {d4(3), d4(3) + ω44} = min {3, 3 + 0} = 3

d5(4) = min {d5(3), d4(3) + ω45} = min {2, 3 + 1} = 2

d6(4) = min {d6(3), d4(3) + ω46} = min {2, 3 + ∞} = 2

d7(4) = min {d7(3), d4(3) + ω47} = min {8, 3 + ∞} = 8

-источник Т5 = {2, 7}

Д(5) = {0, 5, 4, 3, 2, 2, 7}

d2(5) = min {d2(4), d3(4) + ω32} = min {5, 4 + ∞} = 5

d3(5) = min {d3(4), d3(4) + ω33} = min {4, 4 + 0} = 4

d4(5) = min {d4(4), d3(4) + ω34} = min {3, 4 + 1} = 3

d5(5) = min {d5(4), d3(4) + ω35} = min {2, 4 + 1} = 2

d6(5) = min {d6(4), d3(4) + ω36} = min {2, 4 + 1} = 2

d7(5) = min {d7(4), d3(4) + ω37} = min {8, 4 + 3} = 7

-источник Т6 = {7}

Д(6) = {0, 5, 4, 3, 2, 2, 6}

d2(6) = min {d2(5), d2(5) + ω22} = min {5, 5 + 0} = 5

d3(6) = min {d3(5), d2(5) + ω23} = min {4, 5 + 1} = 4

d4(6) = min {d4(5), d2(5) + ω24} = min {3, 5 + 1} = 3

d5(6) = min {d5(5), d2(5) + ω25} = min {2, 5 + ∞} = 2

d6(6) = min {d6(5), d2(5) + ω26} = min {2, 5 + 1} = 2

d7(6) = min {d7(5), d2(5) + ω27} = min {7, 5 + 1} = 6

ρω (1, 1) = 0

ρω (1, 2) = 5

ρω (1, 3) = 4

ρω (1, 4) = 3

ρω (1, 5) = 2

ρω (1, 6) = 2

ρω (1, 7) = 6

§ 4. Раскраска графов

Пусть G = <V, U> - нефграф без петель.

Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если (Vi, Vj)-дуга, то вершины Vi, Vj имеют различные цвета. Хроматическим числом Х (G) графа G называется минимальное число цветов, требующиеся для раскраски G (рис. )

Пример. Так как в полном графе Gn любые две различные вершины связаны ребром, то Х (Gn) = n.

Многие практические задачи сводятся к построению раскрасок графов.

Пример 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. Построим граф G, вершины которого биективно соответствуют лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно Х (G).

Пример 2. Рассмотрим граф G, вершины которого - страны, а ребра соединяют страны, имеющие общую границу. Число Х (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.

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

Неорграф G называется бихроматическим, если Х (G) = 2. Неорграф G = <V, U> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {V1, V2} концы любого ребра принадлежат разным частям разбиения.

Примером служит задача «Три дома, три колодца».

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

. Произвольная вершина V1 графа G принимает цвет 1.

. Если вершины V1, …, Vi раскрашены l цветами е, 2, … е, е ≤ i, то новой произвольно взятой вершине Vi+1 припишем минимальный цвет, не использованный при раскраске вершин из множества {Vj | ρ (Vi+1, Vj) = 1, j < i}.

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

Все двудольные графы бихроматические, Х (G) = 2.

Пример:

бихроматический                                               двудольный

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

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

Дано: G - бихромат. граф

Док-ть: связный и не содержит циклов нечетной длины

Док-во (от противного)

Х = 3, но G - бихромат - противоречие.

Обратная теорема:

Дано: G - связный, не содержит циклов нечет. длины

Док-ть: Х (G) = 2

Док-во:

) рассм. связный граф, который не имеет циклов

) граф, содержит циклы четной длины

§ 5. Эйлеровы и гамильтоновы графы

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

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

Очевидно, не существует циклических обходов, проходящих по всем ребрам по одному разу.

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

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

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

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

Рис. 41

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

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

Верно и обратное утверждение.

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

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

Говоря коротко, лабиринт состоит из коридоров и их перекрестков. Таким образом, он может быть представлен графом, в котором ребра соответствуют коридорам, а вершины перекресткам. На рис.42 изображен план известного лабиринта в саду в Хемптон Корт, а на рис.43 - соответствующий граф.

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

В 1857 году ирландский математик Гамильтон предложил игру, названную «Путешествием по додекаэдру». Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра, при условии, что ни в одну из вершин нельзя заходить более одного раза.

(Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников)

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

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

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

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

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

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

                   56      41      58      35      50      39      60      33

                   47      44      55      40      59      34      51      38

                   42      57      46      49      36      53      32      61

                   45      48      43      54      31      62      37      52

                   20      5      30      63      22      11      16      13

                   29      64      21      4      17      14      25      10

                    6      19      2      27      8      23      12      15

                    1      28      7      18      3      26      9      24

Рис. 44

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

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

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

Рассмотрим решение задачи о коммивояжере на примере графа G (рис.45).

Имеем пять пунктов V = {1, 2, 3, 4, 5}. Стоимость доставки информации из пункта I в пункт j показана числами над ребрами графа. Требуется, используя компьютерную сеть, моделируемую данным графом, обеспечить перекличку пунктов, начиная с пункта 1. Для решения поставленной задачи построим гамильтонов цикл минимальной стоимости передачи информации, либо несколько таких циклов в случае их одинаковой стоимости.

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

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

Всего имеем четыре гамильтоновых цикла:

а) {1, 2, 3, 5, 4, 1},

b) {1, 2, 5, 3, 4, 1},

c) {1, 4, 3, 5, 2, 1}

d) {1, 4, 5, 3, 2, 1}

Стоимости передачи информации каждым из этих циклов вычисляются ниже:

а) 9 + 10 + 2 + 2 + 6 = 29,

b) 9 + 8 + 2 + 5 + 6 = 30,

с) 6 + 5 + 2 + 8 + 9 = 30,

d) 6 + 2 + 2 + 10 + 9 = 29.

Решению поставленной задачи отвечают гамильтоновы циклы а) и d).

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

Глава II. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ

§ 1. Роль факультативных занятий

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

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

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

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

«Влиятельность, воспитательность общеобразовательной школы, - писал в 1901 г. видный русский педагог Петр Федорович Каптерев, - ее значение в народной жизни и развитии культуры будут очень много зависеть от того, как будут поставлены факультативные занятия… на единообразной обязательности далеко не уедешь».

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

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

Важной вехой в истории советской школы был 1966 г., когда постановление ЦК КПСС и Совета Министров СССР «О мерах дальнейшего улучшения работы средней общеобразовательной школы» рекомендовало всем школам проведение в VII-Х классах факультативных занятий «для углубления знаний учащихся, для развития их интересов, способностей». Впервые все работники просвещения осознали, что такие занятия столь же важны, как и уроки по обязательной программе.

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

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

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

Значение факультативных занятий состоит в том, что они позволяют:

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

удовлетворять интересы учащихся;

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

развивать творческие способности учащихся, их самостоятельность;

знакомить учащихся с современными достижениями науки и техники;

формировать у учащихся общеучебные умения: готовить доклады и представлять их, выполнять рефераты, работать в группе, умение работать с информацией;

способствовать профессиональной ориентации учащихся.

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

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

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

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

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

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

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

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

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

Рассмотрим формы обучения учащихся на факультативных занятиях.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§ 2. Постановка факультатива «Элементы теории графов в средней школе»

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

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

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

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

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

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

Факультатив «Знакомьтесь, графы».

На изучение темы программой отведено 32 часа.

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

Задачи факультатива:

сформировать представление о графе как совокупности двух множеств, его составных элементов;

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

- сформировать интерес к изучению графов, через исторический аспект;

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

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

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

граф маршрут теория

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

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

Я о графах сейчас расскажу,

Расскажу, а ты тут же и вспомнишь,

Лабиринты тебе покажу,

Разгадать ты их точно уж сможешь.

Как любил ты игру про коня

Вечерами одни разговоры.

Ты гонял его и гонял

О победе мне вторил с задором…

Помнишь, маленьким ты рисовал

Мне открытый конверт на листочке,

Безотрывно карандашик порхал,

Рисовал ты от точки до точки…

Кто-то умный все это создал

Для развития сына и дочки,

Пусть ребенок в игре создавал

Не игру, а теорию точно…

Знакомы ли вам действия, описанные в стихотворении, что общего они имеют с темой нашего семинара?

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

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

Хочется задать всем вопрос, а для чего или зачем возникла данная теория? Дает ли она результаты в современном, быстро меняющим свой ритм времени?

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

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

Подведем итоги, думаю многим из присутствующих было интересно, а ребята, занимающиеся на факультативе, воочию убедились о многосторонней значимости данной теории. Ни для кого не секрет, что наряду с решенными задачами и проблемами существуют переменные задачи. Некоторые из них имеют элементарную занимательную форму, выглядят как головоломки или олимпиадные задачи. Например, известно, что на бумаге в клетку можно нарисовать 5 фигур из 4 клеток так, чтобы в каждую клетку можно было пройти из соседней через сторону (рис.46). Известно, далее, что таких фигур из пяти клеток 12, из 6 - 35, …, из 10 - 4271. А сколько таких фигур из 11 клеток и вообще из n клеток - неизвестно.

Прошу еще раз в конце семинара задуматься о вопросах, прозвучавших в начале…

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Литература

1. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. - Ростов н/Д: «Феникс», Харьков: «Торсинг», 2009. - 144 с.

. Балк М.Б., Балк Г.Д. Математический факультатив - вчера, сегодня, завтра // Математика в школе. - 2007. - №3. - с.14.

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

. Журбенко И.Г. О материалах для факультативных занятий // Математика в школе. - 2009. - №2. - с.53.

. Мельников О.И., Куприянович В.В. Обучение элементам теории графов в IV - VI классах // Математика в школе. - 2008. - №4. - с.63.

. Мельников О.И. Графы в обучении математике // Математика в школе. - 2003. - №8.

. Методика факультативных занятий в 7-8 классах: Избр. вопросы математики. Пособие для учителей / Сост. И.Л.Никольская, В.В.Фирсов. - М.: Просвещение, 1981.

. Оре О. Теория графов. М., Наука, 1968.

. Педагогика: Учеб. пособие для студентов пед.ин-тов. Под ред. Ю.К.Бабанского. М.: Просвещение, 1983.

. Рогачев С.В. Граф на службе у географии // География в школе. - 2005. - №29 (91).

. Судоплатов С.В., Овчинниова Е.В. Элементы дискретной математики: Учебник. - М.: ИНФРА-М, Новосибирск. Изд-во НГТУ, 2002.

. Теория и методика обучения физике в школе: общие вопросы: Учеб. пособие для студ. высш.пед.учеб. заведений / С.Е.Каменецкий, Н.С.Пурышева, Н.Е.Вашеевская и др. Под ред. С.Е.Каменецкого, Н.С.Пурышевой. - М.: Издательский центр «Академия», 2009.

. Фирсов В.В. и др. Состояние и перспективы факультативных занятий по математике. Пособие для учителей. Под ред. и с предисл. М.П.Кашина. М., Просвещение, 1977.

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

. Якунина М.С. Больше внимания факультативам // Математика в школе. - 2010. - №3. - с.51.