Теория графов: теория и задачи
методическая разработка (алгебра, 9 класс) по теме

МКОУ СОШ №1 имени А.М.горького

городского округа город Фролово

Волгоградской области

Разработка для дополнительных занятий по математике

по теме: «Графы»

                                                                    Подготовила: учитель математики

                                                                    Клочкова Нина Ивановна

Фролово, 2013

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

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

 Задачи:

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

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

3. Познакомиться с применением графов в железнодорожной отрасли.

Разработка включает:

1. История графов.
2. Основные определения теории графов
3. Создание банка задач на применение графов.
4. Знакомство с программами построения графов, применяемые в информатике.
5. Внеклассное мероприятие по теме: «Добро пожаловать в страну Графов».
6.  Обобщение полученных данных и выводы

История графов

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

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

Среди них знаменитая задача о Кенигсбергских мостах (см.«Приложение 1», рис. 1). Эта задача была решена в 1736 году. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку.

Развитие этой задачи привело к циклу задач об обходах графов; задачи о перевозках, решение которых привело к созданию эффективных методов решения транспортных задач. Попытки решить сформулированную в середине 19 века задачу четырех красок, привели к появлению некоторых исследований графов имеющих теоритическое прикладное значение. Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся деревьев в графах. Другой подход к графам, связанный с рассмотрением головоломок был предложен Гамильтоном. А. Кэли исходя из задач подсчета числа изомеров предельных углеводородов,  пришел к задачам перечисления и подсчета деревьев, обладающих заданными свойствами, и решил некоторые из них. Учение о цепях Маркова в теории вероятностей связано с ориентированными графами в том смысле, что события представляются вершинами, а ориентированное ребро (дуга), идущее из одной вершины в другую, указывает на то, что вероятность прямого перехода от одного события к другому положительна.

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

Внутри чистой математики теория графов впервые изучалась Вебленом в его классической книге по топологии, где он определяет понятие графа по-другому. Именно поэтому первая книга по теории графов (Кениг) имела подзаголовок «Комбинаторная топология линейных комплексов». Физики-теоретики для «внутренних» нужд своей науки «открывали» теорию графов не один раз. Занимаясь статистической механикой, Уленбек обозначал точками (вершинами) молекулы, а смежность вершин толковал как взаимодействие наибольшей близости (соседства) некоторого физического типа, например, магнитное притяжение или отталкивание. Другой аспект использования теории графов в физике – как изобразительное средство. Фейнманн предложил диаграмму, в которой вершины представляются физические частицы, а ребра – пути частиц после столкновений.

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

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

Основные определения теории графов

Граф G состоит из конечного непустого множества V, содержащего p вершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V.

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

Пример: Если множество V состоит из 4 элементов, то, к примеру, можно получить 11 различных графов. (см. рис.2, «Приложение 1»)

Каждую пару x={u,v} вершин в X называют ребром графа G и говорят, что x соединяет u и v. Тогда если дана запись x=uv  - это означает, что u и v – смежные вершины, а вершина v и ребро х инцидентны, так же как u и x.

Если два различных ребра x и y инцидентны одной и той же вершине, то они называются смежными.(см. «Приложение 1», Рис.3.)

Пример: У графа G на рис.3. вершины u и v смежные, а вершины u и w нет; ребра x и y смежные, а x и z нет. Хотя на рисунке ребра x и z пересекаются, их точка пересечения не является вершиной графа.

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

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

Пример: На рис.4 в «Приложении 1»  приведены мультиграф и псевдограф, в основе которых «лежит» один и тот же граф – треугольник.

Ориентированный граф (или орграф) D состоит из конечного непустого множества V вершин и заданного набора X, упорядоченных пар различных вершин. Элементы X называются ориентированными ребрами (или дугами).

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

Направленный граф – это орграф, не имеющий симметрических пар ориентированных ребер, т.е. ребер вида (u,v) и (v,u).

Пример: На рис. 5 в «Приложении 1»  приведены орграфы с тремя вершинами и тремя дугами, два последних из них – направленные графы.

Если граф состоит из одних изолированных вершин, т.е. из вершин, не соединенных никакими ребрами, то такой граф называется нуль-графом (см. «Приложение 1»,рис. 6).

Если у графа каждая пара вершин соединена ребрами, такой граф называется полным графом (см. «Приложение 1»,рис. 7).

Два графа G и H называются изоморфными ( или G=H), если между их множествами вершин существует взаимно обнозначное соответствие, сохраняющее смежность. Т.е. если графы G и H изоморфны, то они имеют одно и то же число вершин и для любых двух вершин графа G u и v соединенных ребром, соответствующие им вершины u’ и v’ графа Н тоже соединены ребром, и обратно. Пример: Графы на рис. 8 в «Приложении 1»  изоморфны, т.к. можно указать взаимно однозначное соотетствие , переводящее граф G в граф G’.

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G (см. « Приложение 1», рис. 9).

Маршрутом в графе G назыается чередующаяся последовательность вершин и ребер v0, x1, v1, … , vn-1, xn, vn; эта последовательность начинается и заканчивается вершиной, и каждое ребро последовательности инцидентно двум вершинам одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v0 и vn и его можно обозначить v0, v1, … , vn (наличие ребер подразумевается).

Маршрут замкнут, если v0=vn, и открыт в противоположном случае.

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

Пример: В графе G на рис. 10 в «Приложении 1» v1v2v5v2v3 – маршрут, который не является цепью, а v1v2v5v4v2v3 – цепь, но не простая цепь, v1v2v5v4 – простая цепь и v2v4v5v2 – простой цикл.

Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент; ребро с такими же свойствами называется мостом. Т.о. если v – точка сочленения связного графа G, то граф G-v не связен. Неразделимым графом называется связный, непустой, не имеющий точк сочленения граф. Блок графа – это его максимальный неразделимый подграф. Если G – неразделимый граф, то часто он сам называется блоком.

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

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

На одном участке земли были построены три дома и вырыты три колодца для их обитателей. Природа страны и ее климат таковы, что колодцы часто пересыхают, поэтому важно, чтобы от каждого из домов имелся доступ к каждому из трех колодцев (См. «Приложение 1», рис. 11).

Спустя некоторое время обитатели домов А, В и С серьезно поссорились друг с другом и решили проложить дорожки к трем колодцам X, Y, Z так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга. Задача состоит в том, что могут ли жители этих трех домов проложить дорожки к колодцам указанным образом.

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

На рис. 12 в «Приложении 1» изображен граф, отвечающий естественному расположению дорожек. Эти дорожки, или ребра графа, пересекаются во многих точках, отличных от точек расположения домов А, В, С и колодцев X, Y, Z.

Вопрос, который необходимо поставить, состоит в следующем: является ли соответствующий граф плоским, т. е. можно ли провести его ребра так, чтобы они не пересекались нигде, кроме вершин графа A, B, C, X, Y, Z.

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

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

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

В этом определении пересечение понимается так: (*) жордановы кривые, соответствующие двум ребрам, пересекаются в точке, не соответствующей никакой вершине, или (**) жорданова кривая, соответствующая ребру, проходит через точку, соответствующую вершине, не инцидентной этому ребру. (Случай (**) показан на рис. 13 в «Приложении 1»; здесь вершина v не инцидентна ребрам e1 и е2.)

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

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

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

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

Пример: Все три графа на рис. 14 в «Приложении 1» планарны, но только второй и третий из них плоские

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

В курсе школьной геометрии изучается теорема Эйлера о многогранниках .

Переведем ее на язык графов.

Теорема Эйлера (1752 г.). Пусть G – связный плоский граф, пусть n, m и f обозначают соответственно число вершин, ребер и граней графа G. Тогда

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

Применение графов к решению задач

1. Выяснить, планарны ли графы, изображенные на рисунке

Решение.

а) Граф G, изображенный на рис. а), может быть уложен на плоскости следующим образом. (см. рис. 15, «Приложение 1»)

Ответ: Граф G является планарным.

б) Граф Н не планарен

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

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

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

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

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

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

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

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

Графы в информатике

Способы представления графов в компьютере:        

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

Требования к представлению графов

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.

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

Матрица смежности имеет m – строк и n – столбцов, где m – количество вершин графа. Элементами матрицы смежности являются 0 и 1, Если вершины соединены, то ставится 1 и если не соединены то 0.

Выводы

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

Начальные сведения о графах как геометрических схемах, состоящих из точек(вершин) и соединяющих их стрелок(ребер), достаточно просты, а работа с ними вызывает у детей большой интерес. Граф –  удобная наглядная и доступная модель. Уже в первом классе Вы использовали графы при высказываниях типа « Петя моложе Оли», «Платье дороже юбки, а юбка дороже блузки», «5 меньше 7 и 7 меньше 10».При изображении графов удобно рисовать цветные стрелки: синяя стрелка заменяла слово «меньше», а красная – слово «больше». При обучении шестилетних детей геометрический язык графов оказывается им гораздо приятнее, чем любой другой (например, язык обозначений, использующий знаки < и >.

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

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

Используемая литература

1.    Харари, Френк Теория графов. – Пер. с англ. Козырева В. П. / Под ред. Гаврилова Г. П. – М.: Мир, 1973.
2.    Уилсон, Р. Дж. Введение в теорию графов / Р. Уилсон. – Пер. с англ. Никитиной И. Г. / Под ред. Гаврилова Г. П. – М.: Мир, 1977.
3.    Оре, Ойстин Графы и их применение. – Пер. с англ. Головиной Л. И./ под ред. Яглома И. М. – М.: Мир, 1965.
4.    Кристофидес, Никос Теория графов: Алгоритм. подход. – Пер. с англ. Вершкова Э. В., Коновальцева И. В. / Под ред. Гаврилова Г. П. – М.: Мир, 1978.
5.    Зыков А. А. Основы теории графов. – М.: Наука. Гл. ред. физ.-мат. лит., 1987.
6.       Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по курсу дискретной математики – 2-е изд., переработ. и доп. – М.: Наука, 1992.

Приложение 1. Рисунки и схемы

Приложение 2. Банк задач

1. В железнодорожной сети 15 станций, где каждая станция соединена железной дорогой не менее, чем с семью другими. Докажите, что из любой станции можно проехать до любой другой либо напрямую, либо через одну промежуточную станцию.

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

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

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

5. На карте выбраны пять городов. Среди них из любых трех найдутся два, соединенные железной дорогой, а два- несоединенные. Доказать:1)Каждый город соединен железной дорогой непосредственно только с двумя другими.2)Выехав, из любого города, можно объехать остальные, побывав в каждом по разу и вернуться назад.

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

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

8. Имеется группа островов, соединенных железнодорожными мостами так, что от каждого острова можно добраться до любого другого. Турист объехал все острова, проехав по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного,  если турист:

 1) Не с него начал и не на нем закончил?

 2) С него начал, но не нем закончил?

  3)С него начал и на нем закончил?

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

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

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

12. На банкет, посвященному дню рождения ОАО «РЖД», приехало множество людей из различных уголков страны. Один из гостей сказал: « Здесь не найдется девяти человек таких, чтобы каждый был знаком ровно с тремя другими». Прав ли он?

13. Один из ребят, ученик железнодорожной школы, сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!»

«Не может быть этого», - ответил ученик этой же школы, победитель олимпиады.

Почему он так ответил?

14. В олимпиаде по математике, организованной ОАО «РЖД», была задача: Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятерок подряд стоящих цифр встречаются все 32 возможные комбинации. Найдите пять последних цифр последовательности.

15. В Артеке за круглым столом оказалось пятеро ребят-железнодорожников из Москвы, Волгограда, Новгорода, Перми, Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между Томичем и Витей, житель Волгограда- между Юрой и Толей, а напротив него сидел пермяк и Алеша. Коля никогда не был в Волгограде, Юра не бывал в Москве и Томске, а Томич с Толей регулярно переписываются. Определите, кто в каком городе живет.

16. В железнодорожном детском саду в одной из групп 28 детей. Каждая девочка дружит с четырьмя мальчиками, а каждый мальчик- с тремя девочками. Сколько в группе девочек и сколько мальчиков?

Приложение 3. Внеклассное мероприятие

«Добро пожаловать в страну Графов!»

План проведения

I этап – Орг. момент 

II этап – Новая тема. Понятие  графа

Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.

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

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

Теперь вернемся к основному термину «Граф» и познакомимся с его основными понятиями.

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

Точки называются вершинами графа, а линиями рёбрами.

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

У графа обязательно есть вершины.

Граф без рёбер называется пустым.

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

Дерево (граф) – это способ организации информации об отношениях между объектами.

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

Первая работа по теории графов принадлежит Леонардо Эйлеру (1736г).

Показ презентации «Город – мечта»

Термин граф впервые ввёл 1936г Венгерский математик Денеш Кениг. Графами были названы схемы состоящие из точек и соединяющие эти точки отрезков прямых или кривых.

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

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

Показ презентации «Золушка».

III этап. Представление информации в виде дерева.

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

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

IV этап. Применение знаний и закрепление изученного. 

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

Задача2. В поезде ехали три друга: Коля, Андрей и Саша. Известно, что в купе №1 и 2 ехал не Коля. Андрей ехал не в купе №1. В каком купе ехал каждый из друзей.

Задача3. Из города А в город Б ведут две железные дороги, из города Б в городок В -тоже две железные дороги и из города А в город В – тоже две дороги. Нарисуй схему и сосчитай все возможные пути из города А в город В.

V этап. Знакомство с компьютерной игрой «Паучки»  

Игра «Паучки» помогает детям более полно представить новую тему и вносит в урок атмосферу игры.

Рис. 15

H

4