Элективный курс "Теория графов".
рабочая программа по математике (9 класс) на тему

ЛЕКЦИЯ

«ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ТЕОРИЯ.

    Сегодня наша задача – выяснить, что такое граф.

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

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

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

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

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

III. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.

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

    Задача про контуры.

    Построить в тетрадях фигуры без отрыва карандаша:

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

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

Решение:

В                                     С

                                                                  М

П    

                                                  К              

Ответ: Петя знаком с Максимом и Сережей, Коля – с Витей и Максимом, Сережа – с Петей и Витей.

    Задача про жителей пяти домов.

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

Удастся ли им это сделать?

Решение: да.

    Задача про завтрак.

    В кафе завтракали трое. Двое ели сосиски, двое – винегрет, а двое – виноград. Тот, кто не ел сосисок, не ел и винегрет. Тот, кто не ел виноград, не ел и винегрет. Что ел на завтрак каждый?

Ответ: один не ел ничего, а двое других – все три блюда.

    Задача про трех внуков.

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

Ответ: Миша ест пирог с рисом, Коля с капустой, а Ваня – с яблоками.                

    Задача Сэма Ллойда  про калитки трех цветов. Во дворе, который окружен высоким забором, находятся три домика: красный, желтый и синий. В заборе есть три калитки: красная, желтая и синяя. От красного домика проведите дорожку к красной калитке, от желтого домика — к желтой калитке, от синего — к синей так, чтобы эти дорожки не пересекались.

Решение:

    Задача про игрушки.

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

Ответ: пистолет – в синей, сумочка – в красной, кукла – в зеленой, машинка – в желтой коробках.

IV. ДОМАШНЕЕ ЗАДАНИЕ.

    Проектное задание: придумайте задачу, которую можно решить построением графа.

V. ИТОГИ ЗАНЯТИЯ.

Анкетирование учащихся.

АНКЕТА 1

Что такое теория графов? (Выскажите свое понимание).

Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?

Какие задачи теории графов Вам известны?

Какие имена, связанные с теорией графов, Вы знаете?

Назовите известные Вам математические теории.

Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?

Как Вы считаете, оказала ли теория графов влияние на другие математические теории ХХ века?

Почему Вы выбрали именно этот элективный курс?

ЛЕКЦИЯ

«ТЕРМИНОЛОГИЯ ТЕОРИИ ГРАФОВ».

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

Цели: ввести терминологию предмета; проверить понимание определений учащимися.

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

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

II. ЛЕКЦИЯ.

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

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

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

Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.  На данном рисунке упорядоченные пары вершин А1 и А2, А1 и А4, а неупорядоченные - А2 и А3, А3 и А4.

Пара вершин может быть соединена двумя или более ребрами (или, соответственно, дугами).

Вершину, не принадлежащую ни одному ребру, называют отдельной.

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

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

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

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

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

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

Ребра, имеющие общую вершину, тоже называются смежными.

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

Ребро, соединяющее вершину с самой собой, называют петлей.

Ребро (или дуга) и любая из его вершин называются инцидентными.

Принято говорить, что ребро (А, В) соединяет вершины А и В, а дуга (А, В) начинается в вершине А и кончается в вершине В.  

Плоский граф можно изобразить на плоскости.

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

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

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

III. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.

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

1. Чем отличаются дуга и ребро графа?

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

2. Какие способы задания графов вы знаете?

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

3. Всегда ли можно попасть из конца ориентированного графа в его начало?

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

4. Верно ли, что ребро (а,в) инцидентно вершинам в и а?

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

5. Что означают слова «упорядоченная пара вершин»?

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

6. Любой ли граф называется плоским?

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

7. Являются ли ребра (а,в), (а,м), (а,а) и (а,с) на рисунке смежными? Верно ли, что смежных между собой ребер может быть в графе сколь угодно много?

    Да, если эти ребра имеют общую вершину.

8. Могут ли быть смежными три вершины?

    Нет, понятие смежности подразумевает, что речь идет о паре вершин.

9. Могут ли смежные вершины быть соединены с какими-либо другими вершинами?

    Да, могут. На данном рисунке вершины а и в смежны, но при этом они соединены ребром с другими вершинами.

10. Могут ли кратные ребра соединять смежные вершины?

    Да, могут.

11. Как можно изобразить ребро графа?

    В виде ненаправленной кривой  или в виде кривой, направленной в две стороны.

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

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

IV. ДОМАШНЕЕ ЗАДАНИЕ.

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

V. ИТОГИ ЗАНЯТИЯ.

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

ЛЕКЦИЯ

«СВЯЗНОСТЬ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ.

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

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

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

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

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

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

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

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

Например, на втором рисунке вершины 1 и 2 - связные, а вершины 1 и 6 - несвязные.

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

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

    При удалении ребра (А,В) из графа G получается граф с теми же вершинами, что и граф G, и всеми ребрами, кроме ребра (А,В).

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

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

III. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.

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

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

Решение: необходимо добавить ребра (5, 6) и (8, 9).

Создайте произвольный граф и найдите, если есть, мосты.

5. Решим вместе  с поэтом Погореловским шуточную задачу о спортсменах.

«Высшая математика»

В столярке работает четверо нас:

Беляев, Гуляев, Анютка, Тарас.

Вот как-то профорг заглянул на минутку:

— Кто ходит на лыжах?

— Тарас и Анютка.

— Кто плавать умеет?

— Анютка, Тарас.

— Кто в теннис играет?

— Они же как раз.

Есть шахматисты?

— Беляев, Гуляев.

— Мотоциклисты?

— Беляев, Гуляев.

— Бывал ли в походе кто-либо из вас?

— Беляев, Гуляев, Анютка, Тарас.

Устроили наши ответы профорга,

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

А вскоре весьма и весьма озадачены,

Читали в стенновке мы рапорт такой:

«Шестью видами спорта охвачены

Четырнадцать рабочих у нас в мастерской!»

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

    Является ли данный граф связным и есть ли в нем мосты?

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

    Графы использовать на практике в спортивных соревнованиях. Решим задачу о первенстве класса по теннису. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе — каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис - с Андреем, Галиной; Виктор - с Галиной, Дмитрием, Еленой; Галина - с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение:

    Сыграно 7 игр.

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

    Следующая задача социального содержания также решается при помощи графов. Это задача про драматический кружок. В школьном драматическом кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.

- Ляпкиным-Тяпкиным буду я! - решительно заявил Дима. - С раннего детства я мечтал воплотить этот образ на сцене.

- Ну хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- А мне — Осипа, — не уступил ему в великодушии Дима.

- Хочу быть Земляникой или Городничим, — сказал Вова.

- Нет, Городничим буду я, - хором закричали Алик и Боря. - Или Хлестаковым, -добавили они одновременно.

    Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение:

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

    Это граф с 10 вершинами и 10 ребрами. Надо выбрать из десяти пять ребер, не имеющих общих вершин: Дима - Осип, Вова - Земляника, Гена - Ляпкин-Тяпкин. Остается два случая: Алик - Хлестаков, Боря - Городничий или Алик - Городничий, Боря - Хлестаков. Как показывает граф, других решений нет.

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

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

IV. ДОМАШНЕЕ ЗАДАНИЕ.

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

V. ИТОГИ ЗАНЯТИЯ.

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

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

ПРАКТИКУМ  

«ТЕРМИНОЛОГИЯ ТЕОРИИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ. Предположим, что футбольная команда вашей школы участвует в соревнованиях и играет с командами других школ. Пусть общее число команд равно шести. Вашу команду обозначим буквой А, а другие команды - буквами B, C, D, E и F. Через несколько недель после начала соревнований окажется, что некоторые из команд уже сыграли друг с другом, например

A c C, D, F,

B c C, E, F,

C c A, B,
D c A, E, F,
E c B, D, F,
F c A, B, D, E.

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

Схема такого вида называется графом. Она состоит из нескольких точек A, B, C, D, E, F, называемых вершинами, и нескольких соединяющих эти точки отрезков, таких, как АС или ЕВ, называемых ребрами графа.

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

III. ЗАКРЕПЛЕНИЕ.

1. Дайте полный список проведенных игр, соответствующий графу на рис.3.

2. Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5 ? 18.

3. Сколько рёбер в полном графе с 20 вершинами? 190.

4. Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным? 15.

5. В деревне Вишкиль 9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне? 36.

6. Чему равна сумма степеней входа всех вершин графа, если сумма степеней выхода всех вершин равна 45? 25.

7. В доме отдыха Вишкиль 57 корпусов. Электрик решил соединить телефонными проводами каждый корпус ровно с пятью другими. Сможет ли он это сделать?

8. В москитной сетке ровно 100 узелков, любые два узелка соединены отдельной ниточкой. Сколько всего ниточек? 5000.

9. В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта — в корзинах А, Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д — третьего. Пронумеруйте каждую корзину так, чтобы в корзине 1 были яблоки первого сорта (хотя бы одно); в корзине 2 — второго и т.д.

10. В походе, который длился 12 дней, участвовали 9 человек. Каждый день дежурили З человека. При этом дежурные ссорились друг с другом, и никакие двое из них не хотели больше ни разу дежурить вместе. Тем не менее участники похода утверждают, что все 12 дней им удавалось назначать тройки дежурных с учетом этого требования. Могло ли так быть?

Решение:

Составим граф. Можно изобразить тройки дежурных графом: участники похода обозначены точками, каждое дежурство обозначено линией одного стиля. У каждого из М ребер графа два конца и каждая из Н вершин служит концом трех ребер. 2М = ЗН, отсюда М=ЗН/2. М=3*9/2=13,5. Таким образом, в течении 13 дней можно было составлять тройки дежурных указанным способом, а поход длился 12 дней.

12. У предприятия имеется 4 завода и 9 торговых точек. Каждый завод должен поставлять свою продукцию во все торговые точки. Сколько всего дорог необходимо проложить, чтобы осуществить задуманное? Определите вид полученного графа. (Двудольный).

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

А) Володя и член культсектора живут в одном доме, и они вместе с Олей втроем ездят в школу на автобусе.

Б) На классном собрании было решено в спортсектор избрать мальчика.

В) Член учебного сектора и Сережа вместе ходят на теннисный корт.

Г)Член спортсектора и Володя – большие друзья.

Д) Оля сидит за одной партой с членом учебного сектора.

Решение:

Составим граф из множества ребят и множества секторов.

Ответ: Оля — шефский сектор, Володя — учебный сектор, Толя — культмассовый, Сережа — спортивный сектор.

III. ИТОГИ ЗАНЯТИЯ.

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

а) если известно, что сыграли следующие команды:

A c D, F
B c C, F
C c B, D, E, F
D c A, C
E c C, F
F c A, B, C, E

b) если соревнования закончились;

c) до начала соревнований.

ЛЕКЦИЯ

«РАЗЛИЧНЫЕ ФОРМЫ ЗАПИСИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОБЪЯСНЕНИЕ.

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

    Граф (от греческого графо - пишу) - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

    Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.

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

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

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

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

     Ребра, имеющие общую вершину, тоже называются смежными.

     Ребро (или дуга) и любая из его вершин называются инцидентными.

     Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.  

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

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

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

Также граф можно задать посредством списков. Например, для рассмотренного графа

вариант 1: списком пар вершин, соединенных ребрами (или дугами);

(А1,А2), (А1,А4), (А2,А1), (А2,А3), (А3,А2 ), (А3,А4), (А4,А3).

вариант 2: списком списков для каждой вершины множества смежных с ней вершин.

А1: А2, А4;

А2: А1, А3;

А3: А2, А4;

А4: А3.

III. ЗАКРЕПЛЕНИЕ.

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

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

Рисунок:

 Список дуг:

AC, АD, АF, BC, ВE, ВF, DE, DF, ЕF.

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

IV. ДОМАШНЕЕ ЗАДАНИЕ.

    Придумать граф, задать его рисунком, списком дуг и матрицей смежностей вершин.

V. ИТОГИ ЗАНЯТИЯ.

Ответьте, верны ли предложенные ниже утверждения:

Любой граф можно задать списком вершин. (Нет)

Любой граф можно задать списком дуг. (Да)

Для нулевого графа (графа с нулевым количеством дуг) матрица смежностей состоит только из нулей. (Да)

Для любого плоского графа список дуг содержит не менее одной дуги.

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

Для графа с единственной вершиной список дуг будет пуст. (Да)

Существуют графы, которые нельзя изобразить на плоскости. (Нет)

Любой граф можно изобразить в форме графика на координатной плоскости. (Нет)

ПРАКТИКУМ

«СПОСОБЫ ЗАДАНИЯ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ТРЕНИРОВОЧНЫЕ УПРАЖНЕНИЯ.

1. Создайте матрицы смежностей и списки дуг графов, данных на рисунке, пронумеровав их вершины.

2. Задайте матрицей смежности нулевой граф.

3. Создать граф по его матрице смежности.

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

а) если дан список дуг графа: AD, АF, BC, ВF, CD, СE, СF, EF;

b) если соревнования закончились;

c) до начала соревнований.

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

III. ИТОГИ ЗАНЯТИЯ.

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

ЛЕКЦИЯ

«ЭЙЛЕРОВЫ ПУТИ В ГРАФЕ».

Оборудование: мультимедийный проектор, диск «Большая энциклопедия Кирилла и Мефодия 2003» - материалы для проектного домашнего задания.

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

Ход занятия:

I. ОБЪЯСНЕНИЕ: Теория графов — наука сравнительно молодая. Первая работа по теории графов принадлежит Леонарду Эйлеру.

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

    Рассмотрим знаменитую задачу о кенигсбергских мостах.

    Вы, наверное, знаете, что есть такой город – Калининград. Это красивый город, в котором сохранилось много старинных зданий.

    Раньше он назывался Кенигсберг.

    Через город протекает река Преголя.

    Она делится на два рукава и огибает острова.

    В восемнадцатом веке в городе было семь мостов. До нынешнего времени ни один из них не сохранился, можно только догадываться, как они выглядели…

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

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

    Чтобы решить эту задачу, Леонид Эйлер «сжал» сушу в точки, а мосты «вытянул» в линии. Вершины, из которых выходит 2, 4, 6 и т.д. ребер, он назвал четными, а те, из которых выходит 1, 3, 5 и т.д. ребер – нечетными.

    Рассмотрим граф, соответствующий схеме мостов.

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

Теорема: Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечетной степени. Доказательство; Доказательство достаточности условия теоремы будет следствием анализа алгоритма нахождения эйлерова пути, который будет описан ниже. Необходимость условия очевидна, так как если вершина v, отличная от вершины v1 и vm+1, появляется в эйлеровом пути k раз, то это означает, что степень этой вершины в графе составляет 2k. Отсюда следует, что вершины нечетной степени, если они существуют, являются концами эйлерова пути. Здесь следует отметить, что не существует графов с одной только вершиной нечетной степени. Действительно, обозначая степень вершины v через d(v), имеем

ибо в указанной сумме каждое ребро {u, v} считается дважды: один раз в d(u) и один раз в d(v). Отсюда следует, что число вершин всегда четно.
Если в связном графе нет вершин нечетной степени, то каждый эйлеров путь является циклом, так как концы эйлерова пути, не являющегося циклом, всегда вершины нечетной степени.
   Мы выяснили, что все четыре вершины полученного графа нечетные, поэтому нельзя обойти его, пройдя по всем ребрам один раз, так, чтобы прийти в исходную вершину.

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

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

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

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

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

    Эйлер установил, в частности, следующие свойства графа.    

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

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

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

      Разность В-Р, где В - число вершин, а Р - число ребер графа G, называется эйлеровой характеристикой графа и обозначается (G)=B-P.

    Граф G имеет два цикла, причем один цикл содержит внутри себя другой цикл. Ребро {5,6} в этом случае называют перегородкой, т.к. оно соединяет эти циклы.

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

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

В-Р+Г=2
    Полученную формулу называют формулой Эйлера.

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

    Формула Эйлера не верна для графа, не являющегося связным.

II. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.

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

Какие буквы русского алфавита можно нарисовать одним росчерком? Ответ: Б, В, Г, З, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я.

III. ДОМАШНЕЕ ЗАДАНИЕ

    Подготовить при помощи статьи в Большой энциклопедии Кирилла и Мефодия рассказ о Леонарде Эйлере (учитель показывает диск «Большая энциклопедия Кирилла и Мефодия 2003», демонстрирует его возможности).

IV. ИТОГИ ЗАНЯТИЯ.

    Вспомните формулу, которую называют эйлеровой характеристикой графа    ( В-Р+Г) и вычислите с ее помощью сколько получится листков бумаги, если первоначально было m листов, некоторые листы разрезали на 5 частей, а всего было разрезано k листов?

ПРАКТИКУМ

«ЭЙЛЕРОВЫ ПУТИ В ГРАФЕ».

Оборудование: мультимедийный проектор.

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

Ход занятия:  

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ТРЕНИРОВОЧНЫК УПРАЖНЕНИЯ.

    Задача о четырех островах и четырнадцати мостах.

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

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

Ответ:

    Задача о тропинках в садах. В саду у Александра Ивановича тропинки проложены так, как на рисунке 1, а у Ивана Александровича – так, как показано на рисунке 2. Кто из них может обойти все свои тропинки, проходя по каждой из них только один раз? (Александр Иванович).

Задача про рукопожатия.

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

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

Решение:

   Задача про компанию, в которой у каждого трое друзей.

В компании из Н человек у каждого ровно трое друзей. Доказать, что Н — четное число.

Решение:

Подсчитаем число пар друзей. Поскольку каждый имеет трех друзей, т.е. входит в три такие пары, то общее число пар равно 3Н /2. Отсюда Н — четное число.

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

    Следующая задача о мухе в банке.

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение:

Ребра и вершины куба образуют граф, все 8 вершин которого имеют кратность 3, и, следовательно требуемый обход невозможен.

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

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

    Задача про реку Волошиху.

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

    Задача про людоеда.

Людоед захватил маленькую принцессу. Он нарисовал на земле k квадратов в ряд. Людоед обещал отпустить принцессу, если она сможет пропрыгать по всем квадратам по разу и снова вернуться на первый, при этом прыгать с любого квадратика на соседний нельзя, можно прыгать только через один или через два квадратика (например, с 5 можно прыгнуть только на 2, 3, 7 или 8). Если принцесса не выполнит задание, людоед её съест. Как принцессе спастись при а) k=5 ; б) k=10.

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

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

    Задача про царя Гороха.

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

    Задача про сто дорог.

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

    Задача про муху в банке.

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение:

Ребра и вершины куба образуют граф, все 8 вершин которого имеют кратность 3, и, следовательно требуемый обход невозможен.

    Задача про поселок.

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

    Наши знатоки теории таких головоломок отмети ли буквами А, В, С, Д  участки поселка, разъединенные речкой (участки — это узлы графа, мосты — отрезки графа), и установили, что маршрут, начинающийся в А (нечетном узле), возможен, но закончиться он должен непременно в В - втором нечетном узле, остальные два узла С и О — четные Но ведь Павлик говорит правду: его маршрут из А в Е) действительно пролегал по всем восьми мостикам и был одним маршрутом. В чем здесь дело? Как вы полагаете?

Решение:

    Маршрут мальчика обозначен линией на рисунке. Друзья Павлика упусти одну деталь его сообщения: вблизи поселка небольшое озерцо — исток реки Оя. Павлик его не отметил на плане (В и Д - одна зона - один узел на плане).

Следующая задача о цирковой арене.

    На цирковой арене выступал канатоходец. На высоте 3 метров от земли на 5 столбах были натянуты канаты, по которым он должен был проходить. Канатоходец должен был пройти по 8 канатам так, чтобы по каждому из них он прошел только один раз. И это ему всегда удавалось, хотя он и не возвращался в то место, откуда выходил. Но как-то во время выступлений канат под номером 8 оборвался. Сможет ли теперь канатоходец пройти по всем канатам, обходя каждый из них один раз?

    Решение: Когда все канаты были целы, канатоходец шел маршрутом АДЕСДВСАВ. После того, как оборвался восьмой канат, канатоходец не сможет пройти по каждому из них один раз, согласно теореме Эйлера.  

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

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

III. ДОМАШНЕЕ ЗАДАНИЕ.

   Придумайте задачу на нахождение в графе эйлерова пути или цикла.

IV. ИТОГИ ЗАНЯТИЯ.

    Дайте определение эйлерова пути и цикла.

ЛЕКЦИЯ

«КРАТЧАЙШИЕ ПУТИ В ГРАФЕ». 

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II.ОБЪЯСНЕНИЕ.

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

Если последовательность вершин определяет путь в графе, то его длина определяется как сумма весов дуг между этими вершинами.

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

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

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

    Далее мы можем найти вершину u, для которой расстояние между s и v равно сумме расстояния от s до u  и веса дуги от u  до v, и т.д.

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

    Очевидно, что она определяет кратчайший путь из s в t.

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

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

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

Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.

    Алгоритм нахождения расстояния от источника до всех вершин -

метод Форда – Беллмана проиллюстрирован на следующем рисунке, где веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).

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

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

Рис.1.

Получим граф G1 из графа G.

Рис.2.

    G1 - дерево, полученное в результате работы алгоритма Дейкстры. Очевидно, что из вершины 2 в вершину 1 быстрее всего можно попасть по ребру {2,1}.

    Теперь изменим исходный граф G: ребру, которое соединяет вершины 2 и 3 присвоим вес, равный 100. Мы удалим ребро {2,3} (вес которого по умолчанию равен 1) и восстановим его с весом 100:

Рис.3.

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

    Присвоим длины кратчайших путей весам вершин. Воспользуемся этим и получим информацию о расстояниях от вершины 2 до вершин 1, 2, 3, 4.

    Видно, что для того, чтобы попасть из вершины 2 в вершину 3, требуется пройти расстояние равное двум (т.е. два ребра с единичными весами).

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

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

    Пример такой нумерации приведен на рисунке.

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

III. ДОМАШНЕЕ ЗАДАНИЕ.

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

1. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974.
2. Белов В.В., Воробьев Е.М., Шаталов В.Е., Теория графов, М., Наука,1976.
3. Берж К., Теория графов и ее применения, М., ИЛ,1962.
4. Березина Л.Ю., Графы и их применение, М., Просвещение, 1976.
5. Болтянский В.Г., Наглядная топология, М., Просвещение, 1982.
6. Домодряд А. П., Математические игры и развлечения, М., Физматгиз, 1961.
7. Дынкин Е.Б., Успенский В.А., Математические беседы , М., Физматгиз, 1961.
8. Зыков А.А., Теория конечных графов, Новосибирск, Наука, 1968.
9. Кордемский Б.А., Математическая смекалка, М., Физматгиз, 1954.
10. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.
11. Оре О., Теория графов, М., Наука, 1968.

12. Чистяков В.Д., Рассказы о математике. –Киев: «Наукова думка», 1960.
13. Татт У., Теория графов, М., Наука, 1977.
   Исследуйте дополнительную литературу и представьте материалы исследования в форме доклада своим коллегам.

IV. ИТОГИ ЗАНЯТИЯ.

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

ПРАКТИКУМ

«КРАТЧАЙШИЕ ПУТИ В ГРАФЕ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ

II. ОБЪЯСНЕНИЕ.

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

    Пользователи Интернета, сами не подозревая об этом, также используют алгоритм нахождения кратчайшего пути - они ищут самый дешевый (или самый скорый) путь передачи информации. В задаче о стоимости и времени передачи информации вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. Еще одну ситуацию получаем, когда вес дуги а(u, v) равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути можно свести к задаче о кратчайшем пути.    

    Алгоритм нахождения кратчайшего пути в графе часто применяется не только в теории графов, но и в прикладных науках. Например, на уроке информатики вам могут предложить решить задачу о морском бое. На клетчатом листе бумаги размера MxN нарисованы корабли - различные прямоугольники. Каждый прямоугольник состоит из целых клеток, разные прямоугольники не соприкасаются по сторонам или углам и не накладываются друг на друга. Каждый корабль представляет собой вертикальный или горизонтальный набор подряд идущих закрашенных клеток. Разные корабли не соприкасаются по сторонам или углам и не накладываются друг на друга. В отличие от обычного "Морского боя" могут быть корабли более чем из четырех клеток. Необходимо найти число кораблей - число прямоугольников. Исходная информация - размеры листа бумаги N и M, в первой строке и далее матрица размером NxM, состоящая из 0 и 1 (0 - если клетка пустая и 1 - если она принадлежит какому-то прямоугольнику). Результат работы программы - число прямоугольников на листе.

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

III. ТРЕНИРОВОЧНЫЕ УПРАЖНЕНИЯ.

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

Решение: Нельзя, так как вершины Земля и Марс не связные, значит, не выполняется условие существования кратчайшего пути.

    Решим задачу о транспортных перевозках. Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Найти: а) все кратчайшие пути из Санкт-Петербурга до Омска; б) все кратчайшие пути из Санкт-Петербурга до Магнитогорска.

IV. ИТОГИ ЗАНЯТИЯ.

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

V. ДОМАШНЕЕ ЗАДАНИЕ.

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

ЛЕКЦИЯ

«КЛАССИЧЕСКИЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ.

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

-задача о кенигсбергских мостах (задача Эйлера), развитие которой привело к циклу задач об обходах графов;

-задачи о перевозках, решение которых привело к созданию эффективных методов решения транспортных задач и др.

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

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

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

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

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

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

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

    Примером результата о существовании графа с фиксированными свойствами может служить критерий существования графа с заданными степенями вершин (степень вершины v есть число ребер, инцидентных v): набор целых чисел 0 < d1< d2 <... < dn, сумма которых четна, является набором степеней вершин графа без петель и кратных ребер тогда и только тогда, когда для любого числа r, 1 < r < n - 1, выполняется условие

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

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

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

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

    Как одна из математических моделей теории вероятностей изучаются случайные графы. Это понятие возникает, например, в результате задания для каждой пары вершин vi и vj вероятности pij существования ребра между ними (с вероятностью qij = 1 - pij этого ребра нет).

III. ДОМАШНЕЕ ЗАДАНИЕ.

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

IV. ИТОГИ ЗАНЯТИЯ.

    Составить план лекции совместно с учителем.

ЛЕКЦИЯ

«РЕШЕНИЕ ЛАБИРИНТОВ ПРИ ПОМОЩИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I.ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ.

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

    Теория лабиринтов занимается поиском выхода из лабиринтов и используется в самых разных отраслях науки – от медицины до информатики. Само слово «лабиринт» греческого происхождения. Оно означает «подземный ход». Лабиринты бывают самые разные, они могут быть и пещерами, могут быть сделаны из живых изгородей. Во Франции в 12 столетии лабиринты выкладывали мозаикой на полу соборов. Иногда лабиринты использовались для наказания. Приговоренного приводили в лабиринт и оставляли там. Не зная устройства лабиринта, узник не мог найти выхода. В реальном лабиринте, не зная плана, отыскать реальный маршрут совсем нелегко. Но что же можно предпринять? Один из возможных вариантов – воспользоваться правилом одной руки. Двигаясь вглубь лабиринта, стены все время надо касаться одной рукой, а выходя наружу, надо идти, касаясь той же стены другой рукой. Некоторые лабиринты можно пройти только при помощи правила правой руки, другие – пользуясь правилом левой руки, а некоторые – любым из этих двух правил. А есть ли безвыходные лабиринты? Нет.  

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

Если же попали в тупик – идем обратно.

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

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

Если же таких коридоров нет, идем по любому, пройденному один раз.

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

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

Построим соответствующий ему граф.

Найдем в данном графе путь от входа в лабиринт (вершина 1) в центр лабиринта (вершина 13).

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

1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.

И, соответственно, выйти из центра лабиринта по маршруту:

13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

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

III. ДОМАШНЕЕ ЗАДАНИЕ.

    Спроектировать задачу на решение лабиринта и решить ее при помощи графа.

IV. ИТОГИ ЗАНЯТИЯ.

    Учащиеся составляют план лекции и записывают его в тетради; план проверяется и корректируется учителем.

ПРАКТИКУМ

«РЕШЕНИЕ ЛАБИРИНТОВ ПРИ ПОМОЩИ ГРАФОВ».

Оборудование: мультимедийный проектор.

Цели: приобрести навык решения лабиринтов при помощи графов.

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ТРЕНИРОВОЧНЫЕ УПРАЖНЕНИЯ.

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

Решение: Самый короткий путь:1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 16, 15, 14, 13. Самый длинный путь: 5, 9, 13, 10, 7, 4, 3, 2, 1, 6, 11, 16, 12, 8, 15, 14.

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

    Задача создания выхода из лабиринта.

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

   Задача про числа.

Можно ли на окружности расположить числа от 1 до 10 так, чтобы соседние числа отличались на 2 или на 3?

III. ИТОГИ ЗАНЯТИЯ.

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

ЛЕКЦИЯ

«ИСПОЛЬЗОВАНИЕ ГРАФОВ В МАТЕМАТИКЕ И НЕ ТОЛЬКО В НЕЙ…»

Оборудование: мультимедийный проектор.

Цели: рассмотреть на примерах использование графов в экологии, политике, экономике.

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ.

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

 1) Рассмотрим несколько простейших экосистем и соответствующие им знаковые орграфы

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

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

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

    3) Пусть [1] - число рабочих мест для научных работников; [2] - число слабо подготовленных исследователей; [3] - доля "плохой" научной продукции или вредные последствия использования результатов научно-технических исследований; [4] - внешние и внутренние угрозы обществу, для преодоления которых требуется применение достижений науки и техники; [5] - общественное мнение в пользу развития научных исследований; [6] - бюджетные ограничения; [7] - государственный бюджет научных исследований; [8] - число хорошо подготовленных исследователей; [9] - доля "добротной" научной продукции или положительные последствия использования достижений науки и техники. Данный граф иллюстрирует столь актуальной сейчас проблему науки и общества – политическую задачу. 

Он использован при разработке новых методов принятия решений при финансировании научных и технических исследований, см.: Roberts F.S. Discrete Mathematical Models with Application to Social, Biological and Environmental Problems. - Rutgers University, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1976.

    4) Для анализа проблем потребления электроэнергии также можно использовать графы:

На картинке изображен граф, описанный в статье Roberts F.S. Signed Diagraphs and the Growing Demand for Energy, Environment and Planning, 3, 1971, p. 395-410.

III. ЗАКРЕПЛЕНИЕ.

Задача про Читинскую область.

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

а) из Красного Чикоя (номер 1) до Чары (номер 28), следуя только по Читинской области;

б) из Красного Чикоя до Сретенска (номер 22).

IV. ДОМАШНЕЕ ЗАДАНИЕ.

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

V. ИТОГИ ЗАНЯТИЯ.

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

ЛЕКЦИЯ-ПРАКТИКУМ

«ДЕРЕВЬЯ И ГРАФЫ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ОБЪЯСНЕНИЕ. 

    Решим следующую задачу:

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

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

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

    Дадим определение дерева.

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

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

    Как решить рассмотренную выше задачу, если мы возьмем два листочка?

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

1+2k+1+2t=2(1+k+t)

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

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

    Интересные факты:
-В любом лесу с n вершинами и k компонентами n-k ребер.

III. ЗАКРЕПЛЕНИЕ.

1. В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а все остальные - висячие. Сколько висячих вершин в этом дереве?

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

3. Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем ребер?

4. Создайте дерево с 20 вершинами.

5. Создайте лес, состоящий из 3 деревьев с 10 вершинами каждое.

IV. ИТОГИ ЗАНЯТИЯ.

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

ЗАЩИТА ПРОЕКТОВ.

Оборудование: мультимедийный проектор.

Цели: дать учащимся возможность самореализоваться и выступить со своими проектными исследованиями перед товарищами.

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ

II. ЗАЩИТА ПРОЕКТОВ. 

    Возможные темы для проектных исследований:

1. «Биография Л. Эйлера».

2. «Операции на множестве графов».

3. «Графы и ориентированные графы – аналогии и отличия».
4. «Подграфы, ориентированные подграфы и связность – аналогии и отличия».

5. «Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе».

6. «Гамильтоновы пути в графе».

7. «Программа для решения задачи о транспортных перевозках».

8. «Задачи на связность графов».

9. «Рисунок, список дуг и матрица смежностей вершин – способы задания графа».

10. «Нахождение в графе эйлерова пути или цикла».

11. «Нахождение кратчайшего пути в графе».

12. «Решение лабиринта при помощи графа».

III. ИТОГИ ЗАНЯТИЯ.

    Повторное анкетирование учащихся.

АНКЕТА 2

Что такое теория графов? (Выскажите свое понимание).

Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?

Какие задачи теории графов Вам известны?

Какие имена, связанные с теорией графов, Вы знаете?

Назовите известные Вам математические теории.

Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?

Как Вы считаете, оказала ли теория графов влияние на другие математические теории ХХ века?

Почему Вы выбрали именно этот элективный курс?

КАФЕДРАЛЬНЫЙ СОБОР ПОСЛЕ РЕСТАВРАЦИИ , 14 ВЕК, У ОДНОЙ ИЗ СТЕН МОГИЛА И. КАНТА.

КАФЕДРАЛЬНЫЙ СОБОР КЕНИГСБЕРГА ДО РЕСТАВРАЦИИ, ПОСТРОЕН В 1332 ГОДУ, В 18 ВЕКЕ ДОСТРАИВАЛСЯ, В 1945 ГОДУ БЫЛ СИЛЬНО РАЗРУШЕН, ВОССТАНОВЛЕН.

ПАМЯТНИК И. КАНТУ ВБЛИЗИ УНИВЕРСИТЕТА, ГДЕ ОН ПРЕПОДАВАЛ.

КАКИЕ МОСТЫ СОЕДИНЯЛИ БЕРЕГА РЕКИ ПРЕГОЛИ, ТЕПЕРЬ МОЖНО ТОЛЬКО ДОГАДЫВАТЬСЯ…

Программа элективного курса для девятого класса «НАЧАЛЬНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ»

                                                       Учитель второй категории

                                                       МОУ СОШ № 1

                                                       Папкова М. Ю.

                  Мичуринск 2006 – 2007 учебный год

           ПРОГРАММА ЭЛЕКТИВНОГО КУРСА ДЛЯ  ДЕВЯТОГО КЛАССА «НАЧАЛЬНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ».

                       ПОЯСНИТЕЛЬНАЯ ЗАПИСКА:

    Элективный курс «Начальные понятия теории графов» рассчитан на 16 часов (проводится 1 занятие в неделю в течение полугодия).    

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

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

    Элективный курс «Начальные понятия теории графов» решает следующие задачи:

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

2. Формировать осознанное отношение к математике.

3. Развивать межпредметные связи математики и политики, экономики, информатики.

4. Расширить математический кругозор учащихся.

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

    Программа курса включает девять разделов:

I раздел – «Исторический экскурс» - включает в себя изучение истории возникновения теории графов, биографий основоположников теории графов.

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

II раздел - «Терминология теории графов». В этом разделе вводится терминология предмета, проверяется понимание определений учащимися, ведется работа со словарем теории графов.

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

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

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

VI раздел - «Классические задачи теории графов» - рассматривает на примерах применение теории графов в других областях математики при решении задач.

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

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

IХ раздел - «Обобщение материала». В рамках этого раздела проводится повторное анкетирование учащихся «Что такое графы», отражающее динамику интереса к элективному курсу, и защита ими проектов.

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

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

    Критериями успешного освоения элективного курса можно считать

- степень развития интереса к теории графов;

- степень развития интереса к областям математики, связанным  с теорией графов;

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

    Курс рассчитан на 1 полугодие из расчета 1 час в неделю.

                          Учебно-тематический план курса: 

                                                                        Итого –16 часов.

    Наименование разделов и тем:

I. «Исторический экскурс».

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

II. «Терминология теории графов».

    1. Терминология теории графов.

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

    3. Практикум.

III. «Различные формы записи графов».

    1. Различные формы записи графов.

    2. Практикум.

IV. «Эйлеровы пути в графе».

    1. Эйлеровы пути в графе.

    2. Практикум.  

V. «Кратчайшие пути в графе».

    1. Кратчайшие пути в графе.

    2. Практикум.

VI. «Классические задачи теории графов».

    1. Классические задачи теории графов.

VII. «Решение лабиринтов при помощи графов».

    1. Решение лабиринтов при помощи графов.

    2. Практикум.

VIII. «Использование графов в математике и не только в ней…».

    1. Решение экологических, психологических и политических задач при

     помощи графов.

    2. Деревья и графы.

IХ. «Обобщение материала».

    1. Защита проектов учащимися.

                       Программное содержание курса:

Раздел I. «Исторический экскурс».

Тема 1. История возникновения теории графов. (1 час)

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

Раздел II. «Терминология теории графов».

Тема 1. Терминология теории графов. (1 час)

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

Тема 2. Связность графов. (1 час)

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

Тема 3. Практикум. (1 час)

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

Раздел III. «Различные формы записи графов».

Тема 1. Различные формы записи графов. (1 час)

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

Тема 2. Практикум. (1 час)

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

Раздел IV. «Эйлеровы пути в графе».

Тема 1. Эйлеровы пути в графе. (1 час)

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

Тема 2. Практикум. (1 час)

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

Раздел V. «Кратчайшие пути в графе».

Тема 1. Кратчайшие пути в графе. (1 час)

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

Тема 2. Практикум. (1 час)

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

Раздел VI. «Классические задачи теории графов».

Тема 1. Классические задачи теории графов. (1 час)

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

Раздел VII. «Решение лабиринтов при помощи графов».

Тема 1. Решение лабиринтов при помощи графов. (1 час)

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

Тема 2. Практикум. (1 час)

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

Раздел VIII. «Использование графов в математике и не только в ней…».

Тема 1. Решение экологических, психологических и политических задач при

помощи графов. (1 час) 

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

Тема 2. Деревья и графы. (1 час)

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

Раздел IХ. «Обобщение материала».

Тема 1. Защита проектов учащимися. (1 час)

    Защита проектов дает учащимся возможность самореализоваться и выступить со своими проектными исследованиями перед товарищами. В конце занятия проводится повторное анкетирование учащихся (см. Приложение, Анкета 2).

                                                   Литература. 

1. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974.
2. Белов В.В., Воробьев Е.М., Шаталов В.Е., Теория графов, М., Наука,1976.
3. Берж К., Теория графов и ее применения, М., ИЛ,1962.
4. Березина Л.Ю., Графы и их применение, М., Просвещение, 1976.
5. Болтянский В.Г., Наглядная топология, М., Просвещение, 1982.
6. Домодряд А. П., Математические игры и развлечения, М., Физматгиз, 1961.
7. Дынкин Е.Б., Успенский В.А., Математические беседы , М., Физматгиз, 1961.
8. Зыков А.А., Теория конечных графов, Новосибирск, Наука, 1968.
9. Кордемский Б.А., Математическая смекалка, М., Физматгиз, 1954.
10. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.
11. Оре О., Теория графов, М., Наука, 1968.

12. Чистяков В.Д., Рассказы о математике. –Киев: «Наукова думка», 1960.
13. Татт У., Теория графов, М., Наука, 1977.
14. Уилсон Р., Введение в теорию графов, М., Мир, 1977.
15. Харрари Ф., Теория графов, М., Мир, 1973.

16.Яковлев А.Я., Леонард Эйлер. М.: Просвещение. 1983.

17. Большая энциклопедия Кирилла и Мефодия 2003 на CD, Леонард Эйлер (статья Д. Бобылева из энциклопедического словаря Брокгауза и Эфрона).

Приложение:

АНКЕТА 1

Что такое теория графов? (Выскажите свое понимание).

Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?

Какие задачи теории графов Вам известны?

Какие имена, связанные с теорией графов, Вы знаете?

Назовите известные Вам математические теории.

Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?

Как Вы считаете, оказала ли теория графов влияние на другие математические теории ХХ века?

Почему Вы выбрали именно этот элективный курс?

АНКЕТА 2

Что такое теория графов? (Выскажите свое понимание).

Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?

Какие задачи теории графов Вам известны?

Какие имена, связанные с теорией графов, Вы знаете?

Назовите известные Вам математические теории.

Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?

Как Вы считаете, оказала ли теория графов влияние на другие математические теории ХХ века?

Почему Вы выбрали именно этот элективный курс?