Занятие № 1 (стр. 1 )

Занятие № 1.

Есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя. Она делится на два рукава и огибает остров. В XYIII веке в городе было семь мостов, расположенных так, как показано на рисунке 1.

рис. 1

Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решения никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось известному математику Леонарду Эйлеру (1707 – 1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академий наук) в 1736 году. Причем, он не только решил эту конкретную задачу, но и придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получился граф.

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

. .

. .

а) б) в) г) д)

рис. 2

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

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

1 1

2 3 3

рис. 3

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

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

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

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

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

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

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

Алгоритм составления графа.

1. О каком процессе идет речь?

2. Какие величины характеризуют данный процесс?

3. Каким соотношением связаны эти величины?

4. Сколько процессов описывается в задаче?

5. Есть ли связь между элементами?

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

Рассмотрим это более подробно на конкретных примерах.

Задача 1.

Машина ехала 3 часа со скоростью 65 км/ч и 2 часа со скоростью 60 км/ч. Какой путь пройдет машина за эти 5 часов?

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

1. О каком процессе идет речь? (о движении)

2. Какими величинами он характеризуется? (скорость, время, расстояние) Каждую величину обозначим кружком.

 

3. Каким соотношением связаны эти три величины?

4. Сколько различных процессов описывается? (движение со скоростью

65 км/ч и движение со скоростью 60 км/ч.

1 1 1

2 2 2

5. Есть ли связь между одноименными элементами?

S1 v1= 65 км/ч t1= 3ч

S2 v2 = 60 км/ч t2 =2ч

S1 + S2

Элементами являются S1 и S2, V1 и V2, t1 и t2. Закрашиваем кружок величина, которого неизвестна, а кружок с известной величиной оставляем не закрашенным и подписываем его. ( три часа со скоростью 65 км/ч, два часа со скоростью 60 км/ч).

Как узнать, какое расстояние проехала машина за 5 часов? (для этого нужно найти весь путь, который проехала машина; через S1 и S2 проводим линию и завершаем её кружком S1+ S2).

В итоге рассуждений в тетрадях у учащихся должен получиться сетевой граф. Чтобы решить задачу, надо найти значение закрашенных кружков. Каждую линию, в нашем случае их три, будем называть ребром графа. По – какому же принципу мы будем заполнять кружки: имея (зная) два не закрашенных кружка на одном ребре, найти третий, закрашенный. Рассмотрим первое горизонтальное ребро графа. По условию задачи мы знаем: v1= 65 км/ч, t1= 3ч, следовательно, можем найти S1. По какой формуле? (S = v × t). Чему будет равно S1? (S1= 65×3 = 195 км)

S1 = 195 км v1= 65 км/ч t1= 3ч

Рассмотрим второе горизонтальное ребро графа. По условию задачи мы знаем: v2 = 60 км/ч, t2 = 2 ч, следовательно, можем найти S2. По какой формуле? (S = v × t). Чему будет равно S2? (S2 = 60×2 = 120 км)

S2 = 120 км v2 = 60 км/ч t2 = 2 ч

Рассмотрим вертикальное ребро, в котором уже найдены два кружка S1 и S2. Зная два закрашенных кружка на одном ребре, закрасить (найти) третий, т. е. можно найти S1+ S2.

S1 = 195 км

S2 = 120 км

S1+ S2 = 315 км

Находим S1+ S2 = 120 + 195 = 315 км.

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

S1 = 195 км v1= 65 км/ч t1= 3ч

S2 = 120 км v2 = 60 км/ч t2 =2ч