|
|
||||
|
Графы и их применение при решении задач |
||||
|
|
|
|||
|
|
||||
|
Оглавление |
|
|||
|
|
Введение |
3 |
|
|
|
1 |
История возникновения теории графов. |
4-6 |
|
|
|
2 |
Графы и их применение при решении задач |
7-13 |
|
|
|
|
Заключение |
14 |
|
|
|
Список литературы |
15 |
|
||
Введение
Что такое графы знает не каждый школьник, но практически все знают, как начертить фигуру на рис. 1 одним росчерком пера (или одним движением карандаша).
Рис 1
«Графы» нашли широкое применение в различных областях науки. В школьном курсе математики «Графы» встречаются с первого класса, когда детям предлагают, например, найти «потерявшееся число».
Рис 2
Далее они встречаются все чаще и чаще, но само определение графа не дается. А жаль! Я считаю, что интересно было бы познакомиться с этим понятием, научиться применять графы для решения задач. Графы - это не только схемы, к графам еще можно отнести и таблицы, с которыми дети встречаются еще в детском саду.
История возникновения теории графов.
Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рис. 3. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Причем, он не только решил эту конкретную задачу, но придумал общий метод решения подобных задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии.
Рис 3
В результате получилась фигура, изображенная на рис.4.
Рис 4 Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 4 из вершин B, С, D выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
• Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.• Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Графы и их применение при решении задач
Легко нарисовать окружность, не отрывая карандаша от бумаги и не проводя никакую линию дважды. Это можно сделать и когда надо нарисовать окружность вместе с ее диаметром: выйдем из конца диаметра, пройдем его, а потом по окружности вернемся обратно. Но как провести и второй диаметр? Как бы мы не старались, нарисовать такую фигуру одним росчерком пера (или одним движением карандаша) не удастся.
Рис 5
Какие же фигуры можно нарисовать таким образом?
Рассмотрим следующую задачу: ЗАДАЧА: Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?РЕШЕНИЕ: Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: рис.6.
рис 6
Глядя на него можно ответить, что от З до М добраться нельзя. Таким образом эта задача решена с помощью графов.
Что же такое граф?
В жизни мы часто встречаемся с графами. Это всевозможные схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д. Графы упрощают решение многих логических задач, экономических, физических и других. Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом.
Графы, в которых не построены все возможные ребра, называется неполным.
Графы, в которых построены все возможные ребра, называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа.
Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.
1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива для любого графа.
3) Если степени всех вершин графа равны, то граф называется однородным.
4) Число нечетных вершин любого графа четно.
5) Невозможно начертить граф с нечетным числом нечетных вершин.
6) Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.
7) Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.
8) Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет, то граф несвязный.
Рис 7
Рассмотрим задачу, которую легко можно решить, используя теорию графов.
ЗАДАЧА. Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?
РЕШЕНИЕ: обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, пунктирная – не лежит(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш, то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис. 8), который и дает решение задачи.
Рис 8
ЗАДАЧА. В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз. Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой. Сколько пар проведено и сколько еще осталось?
РЕШЕНИЕ:
Изобразим данные задачи в виде схемы. Участники – это точки, сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно, проведено 7 игр, осталось провести – 8 игр.
ЗАДАЧА: В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена. Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три. Сколько лет Лене? Ответ: Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет.
ЗАДАЧА: Начертить фигуру одной линией, не отрывая карандаша от бумаги и не проводя дважды линий карандашом.
Рис 10
При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая А и В, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами. (В нашем примере это вершины В и А).
Многие известные головоломки могут быть изложены на языке теории графов. Так, решение широко известной задачи о перевозке козы (К), волка (В) и капусты (к) можно представить в виде графа, изображенного на рисунке. Перевозчик обозначен буквой (П).
Рис 11
Из графа видно, что решение может быть получено двумя способами.
Заключение
Зародившись при решении головоломок и занимательных задач, теория графов стала в настоящее время простым, доступным и мощным средством решения широкого круга важных практических задач. Особенно велико значение графов как универсального языка при создании математических моделей. Я считаю, что благодаря доступности и наглядности, графы могут успешно использоваться в школьном обучении при проведении факультативных занятий. Изучение основ теории графов позволяет развивать мышление учащихся, направленное на восприятие дискретных объектов, подготавливать их к обучению в вузах. Кроме того, задачи, решаемые с помощью графов, постоянно встречаются на олимпиадах по математике и информатике. Теория графов вызывает интерес у учащихся, развивает у них навыки абстрактного и логического мышления, творческий подход к решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.
Литература
1. Альхова З. Н., Макеева А. В. Внеклассная работа по математике—Саратов: ОАО Издательство лицей, 2001.
2. Березина, Л. Ю. Графы и их применение. — М.: Просвещение, 1979.
3. Депман И. Я., Виленкин Н. Я. За страницами учебника математики пособие для учащихся 5 – 6 классов средней школы. — М.: Просвещение, 1979.
4. Мельников, О. И. Занимательные задачи по теории графов: Учебно-метод. пособие.— Мн.: ТетраСистемс, 2001.
5. Уилсон, Р. Введение в теорию графов.— М.: Мир, 1977.
Рабочие листы
к вашим урокам
Скачать
Зародившись при решении головоломок и занимательных задач, теория графов стала в настоящее время простым, доступным и мощным средством решения широкого круга важных практических задач. Особенно велико значение графов как универсального языка при создании математических моделей. Я считаю, что благодаря доступности и наглядности, графы могут успешно использоваться в школьном обучении при проведении факультативных занятий. Изучение основ теории графов позволяет развивать мышление учащихся, направленное на восприятие дискретных объектов, подготавливать их к обучению в вузах. Кроме того, задачи, решаемые с помощью графов, постоянно встречаются на олимпиадах по математике и информатике. Теория графов вызывает интерес у учащихся, развивает у них навыки абстрактного и логического мышления, творческий подход к решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.
6 654 995 материалов в базе
Настоящий материал опубликован пользователем Мусалимова Людмила Петровна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
6 ч.
Мини-курс
8 ч.
,"
oncontextmenu="return false;"
ondragstart="return false;"
onselectstart="return false;"
data-worksheet-id="24181"
data-source="LIBRARY_DOCUMENT_PAGE_CENTER"
data-token="ODliQ3A4OG1HeEt5bUdrNlBlX2sxV3l0al93cVFZRXVuwUN_TwqJHDS2H3S_skkhcxu0SAR6BgxV_TCR8_Y86A=="
/>
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.