Графы – замечательные математические объекты, с их помощью можно
решать очень много различных, внешне не похожих друг на друга задач. В
математике существует целый раздел – теория графов, который изучает графы, их
свойства и применение.
Нашего сегодняшнее занятие я хочу начать со следующего задания:
Попробуйте, не отрывая карандаша от бумаги и не проводя по одной
линии дважды, начертить «открытый конверт».
У кого-нибудь из Вас получилось это
сделать?
Давайте пронумеруем вершины графа и
запишем, последовательно соединяя, какие вершины мы сможем обойти весь граф,
не отрывая карандаша:
Молодцы! А теперь попробуйте проделать
ту же «операцию» с «закрытым конвертом».
У кого-нибудь получилось это сделать? К
этой задаче мы вернемся чуть позже. А сейчас давайте определим тему занятия.
Итак, как Вы думаете, какова тема нашего занятия? Записываем
тему урока: «Фигуры одним росчерком».
Фигуры, которые можно вычертить одним росчерком пера называют
«эйлеровым графом».
Основы теории графов как математической науки заложил в 1736
г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Позднее город
Кенигсберг был переименован в какой город? Калининград.
Бывший
Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города
река омывает два острова. С берегов на острова были перекинуты мосты. Старые
мосты не сохранились, но осталась карта города, где они изображены.
Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и
вернуться в начальный пункт, причём на каждом мосту следовало побывать только
один раз.
В 1736 году задача о семи мостах заинтересовала выдающегося
математика, члена Петербургской
академии наук Леонарда Эйлера, о чём он написал в письме
итальянскому математику и инженеру
Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том,
что он смог найти правило,
пользуясь которым, легко определить, можно ли пройти по всем
мостам, не проходя дважды ни по
одному из них.
Попробуйте Вы составить маршрут, который бы удовлетворял
условиям задачи.
У кого-нибудь получилось? Очевидно, что нет. Именно к такому
выводу пришел Леонард Эйлер.
Решая эту задачу, он пришел к следующим фактам:
1. Число нечётных вершин (вершин, к которым ведёт нечётное число
рёбер) графа должно быть чётно. Не может существовать граф, который имел бы
нечётное число нечётных вершин.
2.
Если все вершины графа чётные, то можно, не отрывая карандаша от
бумаги, начертить граф, при этом можно начинать с любой вершины графа и
завершить его в той же вершине.
3.
Граф с более чем двумя нечётными вершинами невозможно начертить
одним росчерком.
4. Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть
все), следовательно, невозможно пройти по всем мостам, не проходя ни по
одному из них дважды
В 1905 году был построен Императорский мост, который был
впоследствии разрушен в ходе
бомбардировки во время Второй мировой войны. Существует легенда
о том, что этот мост был
построен по приказу самого кайзера, который не смог решить
задачу мостов Кёнигсберга и стал
жертвой шутки, которую сыграли с ним учёные умы,
присутствовавшие на светском приёме (если
добавить восьмой мост, то задача становится разрешимой). На
опорах Императорского моста в 2005 году был построен Юбилейный мост. На
данный момент в Калининграде семь мостов, и граф, построенный на основе
островов и мостов Калининграда, по-прежнему не имеет эйлерова пути.
Какие вершины называют четными, а какие нечетными?
Сегодня мы с Вами будем учиться
определять, можно ли начертить фигуру одним росчерком пера.
Для решения этой задачи, существуют
признаки, по которым заранее несложно установить, можно ли данную фигуру
начертить одним росчерком или нет.
Давайте внимательно посмотрим на наши
конверты. Мы установили, что открытый конверт мы можем нарисовать, не отрывая
карандаша от бумаги. А вот с закрытым конвертом у нас этого сделать не
удалось. И не удастся. Закрытый конверт невозможно расчертить одним росчерком
пера.
Зная это, подумайте, что же различного в
двух этих фигурах и как же можно определить, можно ли нарисовать данную
фигуру одним росчерком.
Очевидно, что свое внимание нужно
обратить на вершины наших графов. Сколько четных и нечетных вершин в открытом
конверте? А в закрытом?
А теперь давайте подумаем о том, что
такое четная и нечетная вершина в графе. Четная вершина означает, что мы
может «прийти» в вершину и «выйти» из нее. Тогда получается, что в нечетную
вершину мы можем только «войти», т.е. начать расчерчивать фигуру из этой
вершины либо же только «выйти», т.е. завершить в этой вершине рисунок. А
сколько точек начала и конца может быть в одной линии? Две.
Выходит, что граф, в котором есть только
две нечетные вершины можно обойти одним росчерком пера.
Вернемся к нашим конвертам.
Удовлетворяют они этим условиям?
А как Вы думаете, можно ли обойти одним
росчерком пера граф, в котором все вершины четные?
Получаем следующие признаки
вычерчивания фигур одним росчерком:
а) если нечетных точек в фигуре нет, то ее можно начертить
одним росчерком, начиная вычерчивать с любого места;
б) если в фигуре две нечетные точки (если фигура имеет нечетную
точку, то она всегда имеет и вторую нечетную точку), то ее можно начертить одним
росчерком, начав вычерчивание в одной из нечетных точек и закончив в другой;
в) если в фигуре более двух нечетных точек, то ее нельзя
вычертить одним росчерком.
А сейчас давайте вспомним задачу о кенигсбергских мостах. Так
выглядит граф для данной задачи:
Давайте убедимся, что нельзя пройти по всем мостам, побывать на
каждом мосту ровно по одному разу и вернуться в исходную точку. Если бы мы
смогли начертить этот граф одним росчерком, не проводя одну линию дважды, то
мы бы решили эту задачу? А мы уже знаем метод определения возможности
сделать это. Давайте подсчитаем количество нечетных вершин графа. 4, т. е
все вершины нечетные.
Существует легенда, связанная со следующим графом.
Говорят, что Магомет вместо подписи (Магомет или Мухаммед -
основатель мусульманской религии) расписывался фигурой состоящий из двух
рогов Луны знак. Проверьте, возможно, ли такое?
Что для начала нам нужно сделать?
Выполняется ли условие?
Пронумеруем вершины графа и запишем последовательность
соединяемых вершин.
Существует история, что некто давал миллион рублей каждому, кто
начертит следующую фигуру.
Проверьте, пожалуйста, кто-либо мог получить заветные деньги?
Очевидно, что нет, так как 4 вершины данного графа не четные.
Сейчас я предлагаю Вам самостоятельно поработать со следующими
фигурами. После мы их обсудим все вместе, посмотрим, у кого получились какие
фигуры.
Решение:
а) 5 – 6 – 1 – 2 – 3 – 4 – 2 – 6 – 4 – 5
б) 1 – 7 – 8 – 3 – 9 – 10 – 5 – 6 – 7 – 2 – 8 – 9 – 4 – 10 – 6 –
1 – 2 – 3 –4 – 5 - 1
в) 2 – 3 – 4 – 5 – 6 - 7 – 8 – 9 – 1 – 2 – 3 – 5 – 6 – 8 – 9
г) 1 – 2 – 3 – 4 – 2 – 7 – 4 – 5 – 6 – 1 – 5 – 7 - 1
д) нельзя, т.к. 2, 5, 7 – нечетные вершины
Дома я предлагаю Вам начертить следующие фигуры:
|
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.