Оглавление

1. Введение

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

Толчок к развитию теории графов получила на рубеже 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, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз?

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

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

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

По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD; перечеркнем DK. Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FNO; отметим жирной линией FH, HK и КО. Найдем единственно возможный при данном условии маршрут .

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка 1.3 остается только считать ответ: имение Е принадлежит Манилову, D - Коробочке, С - Ноздреву, А - Собакевичу, В - Плюшкину, М - Тентентникову, F - Бетрищеву, Н - Петуху, К - Констанжогло, О - Кошкареву.

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

Решение. Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, закрасим целиком; остальные кружки оставим незакрашенными.

Рисунок 5 помогает увидеть, что при разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано k листов, то образовалось 1+2k листов (рис.6).

На рис. 6 показано пять разрезаний.

Кстати, вам не кажется, что схемы на рисунках 5 и 6 напоминают ветку дерева с листочками? Математики, обратив внимание на это сходство, назвали такие схемы «деревьями».

Задача 7. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

Решение. Каждого из этой компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком. Оказывается, что такие ситуации не только возможны, но все их можно описать аналогичными схемами (рис. 7). Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник» , поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию, т.е. схема знакомства единственная. Всякую схему, напоминающую многоугольник, принято называть циклом. (Древние греки «цикл» называли «колесом»; и действительно, на рисунке 8 изображено нечто, напоминающее колесо и с успехом заменяющее в рассматриваемой ситуации многоугольник).

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

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

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

Все три фигуры на рисунке 9 изображает один и тот же граф.

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

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

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

ребер. Для задания полного графа достаточно знать число его вершин.

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

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

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

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

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

Обозначать степени вершин А, В, С будем соответственно так: степ. А, степ. В, степ. С и т.п.

У графа на рисунке 13 (а): степ. А = 1; степ. В = 2. У графа на рисунке 13 (в) степени всех вершин равно нулю.

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

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

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

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

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

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 0,1,2….7,8. Предположим, что существует граф Г, все вершины которого имеют одинаковую степень, т.е. каждое из чисел последовательности 0,1,2,…,7,8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А степени 0, то в нем н5 найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.

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

Решение этой задачи почти дословно повторяется в ходе доказательства следующей теоремы (только число 9 приходится заменить произвольным натуральным числом, где n больше или равно 2).

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

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

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

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

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

Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании(рис.14 и 15).

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

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

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

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

Задача 10. В Тридевятом царстве только один вид транспорта - ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний - одна, а из всех остальных городов, - по 20. Докажите, что из столицы можно долететь в город Дальний.

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

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

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

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

На рис.16 изображен граф Г; некоторые ребра его пересекаются. На рис.17 этот же граф Г изображен так, что его ребра не пересекаются .

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

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

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

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

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

На рис.21 плоское представление графа Г с четырьмя гранями: (1,7,4,1), (1,3,2,4,1), (1,2,3,1), (2,6,5,4,2). Часть плоскости, ограниченная простым циклом(1,2,4,1), гранью не является, так как содержит внутри себя цикл(1,2,3,1). А на рис.22 часть плоскости, ограниченная простым циклом (1,2,3,4,5,1), является гранью, так как ребро(4,5), расположенное внутри грани, не образуют цикла. Не является гранью и заштрихованная часть плоскости на рис.23, так как она содержит внутри себя цикл, да к тому же эта часть не ограничена циклом.

Ребро (А,В) на рис.23 является мостом, соединяющим циклы. Такие мосты будем называть перегородками.

Простой цикл, ограничивающий грань, назовем границей грани.

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

Ребро(А.В) в этом графе является перегородкой.

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

Для всякого плоского представления связного плоскости графа без перегородок число вершин(в), число ребер(р) и число граней с учетом бесконечной(г) связаны соотношением: в - р + г=2.

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

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

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

В полученном дереве обозначим число вершин - вд, число ребер - рд, число граней - ГД. Справедливо равенство р - г = рд - гд.

В дереве одна грань, т.е. р - г = рд - 1. Вспомним, что операция удаления ребер из графа не меняет число его вершин, т.е. в = вд. По теореме 1.7 в дереве вд-рд=1. Отсюда в - рд = 1,т.е. рд = в -1, а потому р - г = в- 2 или в -р +г=2.

Итак, доказано, что если в плоском представлении связного графа без перегородок в вершин, р ребер и г граней, то в - р + г = 2. Полученная формула называется Эйлера.

Задача 11. Каждый из четырех соседей соединил свой дом с тремя другими дорожками, которые пересекались лишь около домов (рис. 25). Докажите, что дом пятого соседа со всеми остальными домами соединить непересекающимися дорожками невозможно, т.е. он вынужден построить мост или рыть подземный ход.

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

Решение. Предположим, что граф Г плоский, т.е. существует его плоское представление. Граф Г - связный, он не имеет перегородок, так как не имеет ни одного места. Для плоского представления графа Г верна формула Эйлера. Подсчитаем число вершин и ребер: в =5, р = 10, тогда г = 2 - 5 + 10 = 7.

Оценим удвоенное число ребер 2р. Каждая грань ограничена не более чем тремя ребрами (граф полный), причем каждое ребро принадлежит границам двух граней, поэтому число 3г не может быть больше числа 2р, то есть 3г ≤ 2р. Но 2р = 20, а 3г = 21, т.е. 20 ≥ 21. Противоречие доказывает, что предположение было неверным, т.е. граф Г не плоский.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если остались непройденные ребра, то должна существовать вершина В, принадлежащая l и ребру, не вошедшему в l.

Так как В - четная, то число ребер, которым принадлежит В и которые не вошли в путь l, тоже четно. Начнем новый путь s из В и используем только ребра, не принадлежащие l. Этот путь кончится в В. (На рисунке 28 путь s обозначен сплошными стрелками.) Объединим теперь ба цикла: из А пройдем по пути l к В, затем по циклу s и, вернувшись в В, пройдем по оставшейся части пути l обратно в А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представляемые на социограммах данные нередко для получения более подробной информации о положении человека в системе внутригрупповых отношений дополняются числовыми показателями - индексами. Наиболее известный из них индекс групповой сплоченности, который характеризует систему новых отношений в целом. Изучив данный материал, я применила всё на практике и результаты исследуемых вывела на этой социограмме. Я провела опрос в своем классе. Мои одноклассники отвечали на вопрос: «С кем бы вы хотели сидеть?» Лидер определяется по количеству выборов. В этом опросе участвовали 20 человек:

1.Азымов Ернар

2.Алиева Акгуль

3.Андреев Алексей

4.Ахансериева Токжан

5.Данников Александр

6.Денисов Павел

7.Зинченко Виктор

8.Исаченко Алексей

9.Жарманова Айжан

10.Калинин Евгений

11.Ковалева Ирина

12.Крикун Олег

13.Кучеренко Никита

14.Левчук Дарья

14.Рощин Алексей

15.Болотина Татьяна

16.Мусаханова Шолпан

17.Багдасарян Анаида

18.Яковлюк Юлия

19.Свешникова Екатерина

Лидером стал Рощин Алексей, потому что у него наибольшее количество выборов. На социограмме лидера отметим в центре. Число окружностей

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

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

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

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

- Уровень государственно - общественного управления

- Административный уровень

- Методический уровень.

На этом рисунке хорошо видно, что Директор после Педагогического совета занимает важное место. Он через завуча на административном уровне узнает, контролирует и прослеживает за выполнением работы. Хотя Малый Педсовет не идёт на прямую с Бухгалтерией, но они могут поддерживать связь через Директора.

Для наглядности изобразим эту же схему с помощью графов.

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

Ещё один пример с участием графов - маркетинг. Существуют много различных сфер (именно в бизнесе), где не просто используется, а основой в бизнесе является сетевое планирование и управление. Для примера рассмотрим туристическую компанию, в которой можно показать схему работы этой компании с помощью графов; приведу сравнительные характеристики двух участников компании , чтобы вы увидели и прочувствовали, как эта схема работает. Если в этой компании один участник регистрирует двух партнеров, то эти партнеры должны повторить, т.е. точно так же набрать двух партнеров. Следовательно, за 3 месяца(для примера возьмем определенное время) у этого лидера, начавшего эту структуру, в конце наберет 32 людей. Другой участник компании произвел такие же действия, что и первый, но ещё к этому зарегистрировал 3 человек и получилось, что он начал свою структуру, состоящую из 5 человек. Эти люди должны повторить действия своего КУРАТОРА. Такой метод называется методом дупликации.

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

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

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

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

Пояснительная записка

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

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

Цель курса

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

Задачи курса

• Изучить историю графов.

• Раскрыть теоретические основы теории графов.

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

• Познакомиться с основными и нетрадиционными приёмами и методами решения задач.

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

• Повысить мотивацию обучения.

• .Сформировать устойчивый интерес учащихся к предмету.

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

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

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

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

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

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

• Формирование личностно-ценностного отношения к математическим знаниям, представления о математике как части общечеловеческой культуры, усиление практического аспекта в преподавании, развитие умения применять математику в реальной жизни;

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

В результате изучения курса учащиеся должны:

• знать элементарные основы теории графов;

• уметь применить теоретические знания при решении задач;

• получить навыки решения нестандартных задач;

• повысить математическую культуру и качество знаний;

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

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

Данный курс может являться основой для творческой и исследовательской деятельности школьников.

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

1. Старинные задачи.

2. Из истории арифметических действий.

3. Задачи с экономическим содержанием в 5 классе.

4. Графы в 5 классе.

5. Комбинаторика пятиклассника.

6. В стране рыцарей и лжецов.

7. Занимательная математика.

8. Математические головоломки.

9. Блез Паскаль.

10. Леонард Эйлер.

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

12. Эйлеровы циклы и пути в графах.

13. Факториал.

14. Дерево возможных вариантов.

15. Раскраска карты.

16. Задачи на "разрезание" и "раскрашивание".

17. Пять ключевых задач по теории графов.

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

Тематическое планирование элективного курса для 5 -6 классов по математике

"Элементы теории графов и использование граф- моделей к решению задач "

(1 час в неделю, всего 18 часов )

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

Задачи

Задача 1.

А) Поезд шел со скоростью 50 км/ч. Сколько км. прошел поезд за 4 часа?

Б) Толя с бабушкой ходили по грибы. Придя домой они сосчитали, сколько грибов собрал каждый. Оказалось, что бабушка собрала 69, а Толя 43 гриба. Сколько грибов они собрали вместе?

В) Длина ломаной, состоящей из шести звеньев,- 25,8 см. Какова длина одного звена?

Г) Человек прошел расстояние 100 м. Сколько шагов он сделал, если длина его шага ровна 0,8 м?

Задача 2

А) Туристы были в пути 3ч. утром и 4ч. вечером, причем скорость их была постоянной 5 км/ч. Каков путь, пройденный туристами за день?

Б) Совхоз отправил на завод 40 машин с яблоками. В каждой машине было 220 ящиков по 25кг. Сколько тонн яблок отправили на завод?

В) Папа Димы весит 86,5 кг. Дедушка Димы весит на 18,7 кг меньше, чем папа. Дима весит в 2,4 раза меньше, чем дедушка. Сколько весит Дима?

Граф- модель для задачи в два действия может быть такой:

Задача 3.

На одной ферме 847 коров, а на другой на 309 коров больше. Сколько коров на двух фермах?

Задача 4.

А) В двухкомнатной квартире ширина каждой комнаты 4 м, а их длина 7 м и 5 м. Сколько квадратных метров коврового покрытия потребуется, чтобы полностью застелить полы в комнатах?

Б) На лесосеке было 16 штабелей бревен по 55 штук в каждом и 12 штабелей по 42 штуки в каждом. Сколько штук бревен было на лесопилке?

Задача 4.

А) Один автомат в минуту закрывает 60 банок, а другой на 5 банок больше. За сколько минут оба автомата при их одновременном включении закроют 2500 банок?

Б) Из рулона ткани в первый день продали 12,52м, во второй день еще 26,7м, а в третий день 19м. Осталось непроданными 2,48м. Сколько метров ткани было в рулоне?

В) Из 35м ткани сшили 6 костюмов для мужчин и 5 костюмов для мальчиков. При этом 1,55м ткани остались неиспользованными. Сколько метров ткани требуется на один детский костюм и на один взрослый, если на костюмы для мужчин израсходовали 19,2м ткани?

Задача 5. Я задумал число. Если к нему прибавить 24, потом полученную сумму умножить на 9, затем из произведения вычесть 76 и, наконец, полученную разность разделить на 19, то получится число 23. Найти задуманное число.

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

Задача 7. Если задуманное число умножить на 5 и к результату прибавить 1, потом сумму увеличить в 6 раз и к результату прибавить 2, затем новую сумму умножить на 7 и полученное произведение увеличить на 4, то получим число, которое в 16 раз больше числа 135. Найдите это число.

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

Задача 9. Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II - половину остатка и еще 1 яблоко, III - половину нового остатка и еще 1 яблоко и т.д. Последнему - шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница?

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

Задача 11. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Задача 12. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

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

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

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

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

Задача 17. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Задача 18. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

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

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

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир - однофамилец кондуктора живет в Чикаго.

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

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

Как фамилия машиниста?

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

Литература

1.Литвинова С.А., Куликова Л.В., Шиловская С.В., Тараева Г.Ю. Издательство «Панорама» 2006 г.

2. Коннова Е.Г. Издательство «Легион-М» 2009 г.

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

4. Засенок В.П. Графы в математике и в жизни/программа интеллектуального развития учащихся /выпуск 6./ Инновационно-образовательный центр-М. 1997года.

5. . Е.В. Галкин. Нестандартные задачи по математике. Задачи логического характера . Книга для учащихся 5-11 классов. "Просвещение" - "Учебная литература" Москва 1996.

6. О.И.Мельников. Незнайка в стране графов. М.: КомКнига,2006.

4 Заключение

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

5 Литература

1.Литвинова С.А., Куликова Л.В., Шиловская С.В., Тараева Г.Ю. Издательство «Панорама» 2006 г.

2. Коннова Е.Г. Издательство «Легион-М» 2009 г.

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

4. Засенок В.П. Графы в математике и в жизни/программа интеллектуального развития учащихся /выпуск 6./ Инновационно-образовательный центр-М. 1997года.

5. Е.В. Галкин. Нестандартные задачи по математике. Задачи логического характера . Книга для учащихся 5-11 классов. "Просвещение" - "Учебная литература" Москва 1996.

6. О.И.Мельников. Незнайка в стране графов. М.: КомКнига,2006.

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