Построение фигур без отрыва карандаша от бумаги

МО РБ

Средняя школа № 1.

Построение фигур без отрыва карандаша от бумаги

Выполнила ученица 7 «А» класса Козел Анна Руководитель Скроцкая Светлана Павловна.

2007;2008 учебный год г. Каменец.

Введение

О фигурах, вычерчиваемых одним росчерком.

Теория графов Эйлера.

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

Применение графов.

Приложение 1.

О ФИГУРАХ, ВЫЧЕРЧИВАЕМЫХ ОДНИМ РОСЧЕРКОМ

Известен анекдот: некто давал миллион рублей каждому, кто начертит следующую фигуру (рис. 1).

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

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

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

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

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

Теория графов Эйлера

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

А вот «распечатанный конверт», изображённый на рисунке 2, совсем нетрудно изобразить, выполнив указанные условия. В чём дело?

Впервые над задачами такого типа задумался Леонард Эйлер после посещения города Кенинсберга (теперь Калининград). В городе было семь мостов через реку Прегель. Их расположение указано на рисунке 3.

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

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

Рис. 4.

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

А всегда ли можно изобразить граф на плоскости, чтобы его рёбра не пересекались? Впервые этот вопрос возник при решении старой головоломки: «в трёх домиках жили три человека, неподалёку находилось три колодца: первый колодец с водой, второй — с маслом, а третий — с повидлом (рисунок 5).

Рис. 5.

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

Рис. 6.

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

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

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

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

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

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

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

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

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

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

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

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

Применение графов.

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

Задача:Три брата — Ваня, Саша и Коля разного возраста. Ваня не старше Коли, а Саша не старше Вани. Назовите имена старшего, среднего и младшего братьев.

Так как дети разного возраста, то «не старше» будем понимать как «моложе». Требуется упорядочить множество (В, С, К) отношением «моложе» с учетом условий: 1) Ваня моложе Коли; 2) Саша моложе Вани. Строим схему с учетом этих условий и достраиваем ее на основе отношения «моложе».

Ответ: Коля — старший, Ваня — средний, Саша — младший.

Задача:На улице 5 жилых домов. Известно, что в доме № 14 больше этажей, чем в доме № 10; в доме № 11 больше, чем в доме № 13, и меньше, чем в доме № 10; в доме № 14 этажей меньше, чем в доме № 12. Какой из этих домов самый высокий, а какой самый низкий?

Множество домов (№ 10, № 11, № 12, № 13, № 14) нужно упорядочить отношением «иметь больше этажей», то есть «выше». Выделим сначала все условия, для удобства переформулировав их: 1) дом№ 14 выше дома № 10; 2) дом№ 11 выше дома № 13; 3) дом № 10 выше дома № 11; 4) дом № 12 выше дома № 14. Отразим эти условия на схеме а).

Дополним схему стрелками так, чтобы любые две точки были соединены стрелкой. Проведем недостающие стрелки, учитывая отношение «выше». Из стрелок 3 и 2 следует стрелка 5, из стрелок 4 и 1 — стрелка 6, из стрелок 1 и 3 — стрелка 7, из стрелок 6 и 5 — стрелка 8, из стрелок 7 и 2 — стрелка 9, из стрелок 6 и 3 -стрелка 10.

Из точки № 12 выходит больше всего стрелок (4) и ни одна не входит. Значит, дом № 12 самый высокий. Из точки № 13 не выходит ни одна стрелка, все только входят. Дом № 13 самый низкий.

Ответ: дом № 12 самый высокий, дом № 13 самый низкий.

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

Рис. 7.

Пример из истории:

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

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

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

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

И всё же теория графов —- наука сравнительно молодая; во времена Ньютона такой науки ещё не было, хотя и были в ходу «генеалогические деревья» представляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру. Появилась она в 1736 году в публикациях Петербургской Академии наук. В работе Эйлер описывал решение головоломок и математических задач. Широкое распространение теория графов получила в 50-ых годах XX века.

Приложение 1

ОДНОЙ ЛИНИЕЙ НЕ ОТРЫВАЯ КАРАНДАША ОТ БУМАГИ

Одной линией

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

Ответы:

Литература

1. Энциклопедия «Я познаю мир» математика 1997 г. изд., изд. «Москва», стр.314−317.

2. «Занимательные задачи и опыты» Перальман Я. И., 1919 г. изд., стр.406−411.

3. «Внеклассная работа по математике» Гусев В. А., Орлов А. И., Розенталь А. Л., изд. «Просвещение» 1984 г. изд., стр.32−35.

4. «Энциклопедический словарь юного математика» А. П. Совин 1989 г. изд., изд. «Педагогика», стр. 85−89.

5. «Математическая энциклопедия» том 1, 1977 г. изд., изд. «Советская энциклопедия», стр. 1106.

6. Задачи со «звёздочкой» Л. А. Бондарева Мн.: Бел. Ассоц. «Конкурс» 2006 г., стр. 11.