Проект "Решение задач с помощью графов"

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

Введение

Математика - это очень непростая наука, можно сказать, что очень сложная. И сейчас мы рассмотрим несложную тему в математике, которая называется - ТЕОРИЯ ГРАФОВ В РЕШЕНИИ ЗАДАЧ.

Теория графов один из наиболее интересных разделов математики. Родоначальником теории графов считается швейцарский математик Леонард Эйлер, который в 1736 году сформулировал решение задачи о семи кёнигсбергских мостах, ставшей впоследствии классической задачей теории графов. Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

$C:\Users\PC\Downloads\thumb.jpeg$

Примеры графов: схемы авиалиний, метро, дороги, электросхемы, чертежи многоугольников.

$C:\Users\PC\Downloads\Ирбисовская-электросхема.jpg$ $C:\Users\PC\Downloads\147117_original.jpg$

Теория графов

$C:\Users\PC\Downloads\img5.jpg$

$C:\Users\PC\AppData\Local\Microsoft\Windows\Temporary Internet Files\Content.Word\img5 (1).jpg$

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

$C:\Users\PC\Downloads\200px-Complete_graph_K7.svg.png$

Количество рёбер, выходящих из вершины графа, называется степенью вершины.

Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст. А. На рисунке: Ст. А = 1, Ст. Б = 2, Ст. В = 3, Ст. Г= 2, Ст. Д= 0.

gr9

Виды графов

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2. Неориентированный граф - это граф, в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Примеры решения задач

Задача 1.

Из лагеря вышли четыре туриста: Вася, Галя, Толя и Лена. Вася идет впереди Лены, Толя впереди Гали, а Лена впереди Толи. В каком порядке идут дети?

Попробуем вначале эту задачу решить без использования графа. При этом условие, что Толя идет впереди Гали придется вначале пропустить, т.к. неясно, они идут перед Васей и Леной или позади их. И только после прочтения последнего условия и установления, что Толя идет за Леной, можно определить месторасположение Гали.

Когда же мы решаем эту задачу при помощи графов, нам лишь необходимо представить условие задачи на графе. Изобразим всех туристов точками, которые обозначим первыми буквами имен детей. В задаче рассматривается отношение “идти впереди”, поэтому стрелку будем ставить от впереди идущего к идущему вслед за ним. Вася идет впереди Лены, значит стрелку ставим от Васи к Лене. Толя впереди Гали – стрелку ставим от Толи к Гале. Также ставим стрелку от Лены к Толе, т.к. она идет впереди него. На графе видно, что первый идет Вася, за ним Лена, Толя и Галя идет последней.

Задача 2.

У Маши были родные сёстры и братья. Сестра Вероника родилась раньше сестры Кати, а сестра Катя родилась после Вероники. Никита родился после Вовы, т.е. Вова родился после Кати, а самый младший ребёнок семьи - Маша. Вопрос такой: кто самый старший ребёнок в семье? Кто родился третьим в семье Маши?

Составлять этот граф мы будем так:

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

Делается вывод, что таким способом (т.е. путём составления графа мы легко можем ответить на эти вопросы). Итак - самый старший ребёнок семьи - Вероника, а третьим родился Вова.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо? $C:\Users\PC\Downloads\thumb (3).jpeg$

Задача 4.

В детском лагере отдыха в одной комнате живут четыре девочки: Маша, Валя, Таня и Галя. Две из них ровесницы. Известно, что Таня старше Маши, которая моложе Гали. Таня моложе Вали, которая старше Гали. Кто ровесницы?

Рассмотрим решение этой задачи при помощи графа. В задаче рассматриваются два отношения “быть младше” и “быть старше”. Выберем одно из них и построим граф отношения “быть старше”. При этом стрелку будем ставить от старшей девочки к младшей. По графу видно, что старше всех Валя, а Маша – младшая из девочек. Следовательно, ровесницы – это Галя и Таня.

Задача 5. На урок в танцкласс пришли слон, волк и лев. Партнершами для них были выбраны мышка, белочка и лисичка. Помогите учителю расставить их в пары, если белочка боится, что ее съест волк, а слон - что он раздавит мышку. Сколько вариантов составления пар есть у учителя танцев? Перечислите их.

Составим граф:

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

Решение олимпиадных задач с помощью графов

Пример 1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун - Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. Можно ли добраться (возможны пересадки) с Земли до Марса?

Решение. Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршрутам - непересекающиеся между собой линии.

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

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

$C:\Users\PC\Downloads\image007_27.jpg$

Решение. Покажем возможные маршруты, нарисовав граф. И в этой задаче 1 и 9 попали в две разных части графа. Ясно, что в правой части графа сгруппировались города-цифры нацело делящиеся на 3, а в левой части графа ребра соединяют две цифры: одну — делящуюся на 3 с остатком 1, а другую — делящуюся на 3 с остатком 2.

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

Пример 3. Сколькими способами, двигаясь по указанным отрезкам, можно кратчайшим путем переместиться из точки А в точку В?

$C:\Users\PC\Downloads\image008_19.jpg$

Решение. Это классическая задача на минимальный путь и возможное количество путей. Начнем с того, что вычеркнем все отрезки, лежащие вне прямоугольника с вершинами А и В. Ясно, что они не могут давать минимальный путь:

$C:\Users\PC\Downloads\image009_12.jpg$

Теперь последовательно будем убирать симметричные пути:

$C:\Users\PC\Downloads\image010_8.jpg$

Пройдем из точки А по периметру через верхний правый угол (рис. 1), потом пройдем через левый нижний угол (рис. 2) — два пути уже получены. Обратимся к рисунку 2: пройдя через точки А и С, далее мы можем попасть в точку В двумя способами (см. рис. 3). Задача имеет симметрию. Теперь из точки В пройдем через точку D (см. рис. 3) в точку А. Ясно, что это можно сделать еще двумя способами. Пройдя из А через G и Е, мы получим еще два варианта пути. И оставшиеся два варианта представлены на рисунке 5.

Ответ: десятью способами.

Примечание. Это задача на отыскание оптимального (симметричного) решения задачи.

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

Пример 4. В деревне есть 15 телефонов, а АТС отсутствует. Можно ли телефоны соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение. Предположим, что это возможно. Рассмотрим граф, вершины которого соответствуют телефонам, а ребра — соединяющим их проводам. В этом графе 15 вершин, степень каждой из которой равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 37,5. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

Правило. Для подсчета числа ребер графа необходимо просуммировать степени вершин и полученный результат разделить на два.

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

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

Теорема. Число нечетных вершин любого графа — четно.

Для доказательства этой теоремы остается заметить, что сумма нескольких целых чисел четна тогда и только тогда, когда количество нечетных слагаемых четно.

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

Пример 5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей.

Примечание. Если Петя друг Васи, то Вася - друг Пети.

Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3; 11 — степень 4; 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

Пример 6. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).

$C:\Users\PC\Downloads\image012_8.jpg$

Решение. Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог (с этим мы уже сталкивались в примере 3), в которой начало очередной дороги совпадает с концом предыдущей. Каждый из двух городов по условию задачи соединен не менее чем с 7 другими; при этом все упомянутые города различны - ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.

Таким образом, мы указали 16 городов. Противоречие с условием задачи.

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

Определение. Несвязный граф состоит из нескольких «кусков».

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

Примечание. В примерах 1 и 2 мы имели дело с графами несвязными; во всех остальных примерах рассматривались графы связные.

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

Пример 7. В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов по 20. Докажите, что из столицы можно долететь в Дальний (возможно с пересадками).

Доказательство. Рассмотрим компоненту связности графа ковро-линий, содержащую столицу. Нам нужно доказать, что она содержит также и город Дальний. Предположим противное. Тогда в этой компоненте связности из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин — 20 ребер. Таким образом, в этом графе (компоненте связности) ровно одна нечетная вершина. Мы пришли к противоречию!

Эйлеровы графы

Пример 8. Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаша от бумаги?

$C:\Users\PC\Downloads\image013_9.jpg$

Подобные задачи достаточно часто встречаются в книжках по занимательной математике для младших школьников.

Решение. Для того чтобы нарисовать любой граф не отрывая руки от бумаги, необходимо в каждую вершину графа, за исключением начальной и конечной, войти столько же раз, сколько и выйти. Поэтому, степени всех вершин нарисованного графа, кроме начальной и конечной, должны быть четными - такой граф должен иметь не более двух нечетных вершин! Ясно, что левая фигура и конверт могут быть нарисованы, не отрывая руки от бумаги, при этом рисунок должен начинаться в любой нечетной вершине: у первой фигуры две такие точки лежат на концах горизонтального отрезка, а у конверта такими двумя точками являются нижние углы конверта. Эмблема «Мерседеса» нарисована быть не может. Впервые графы, обладающие подобными свойствами, были исследованы великим русским математиком Леонардом Эйлером в 1736 году в связи со знаменитой задачей о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются эйлеровыми.

Пример 9. Леонард Эйлер, совершая прогулку по городу, в котором он жил, — Кенигсбергу (ныне Калининград), поставил для себя задачу: прогуляться по всем мостам, перекинутым на два острова реки и между островами так, чтобы по каждому мосту пройти не более одного раза. Представим схему задачи Эйлера:

$C:\Users\PC\Downloads\image014_4.jpg$

Ясно, что задача Эйлера при переводе на язык графов имеет 4 нечетных вершины и, следовательно, не решается.

Заключение

Вот так легко и просто мы можем решать задачи с помощью графов. Подробно изучая эту тему, я узнала много интересного для меня. Графы – это замечательные математические объекты, с помощью, которых можно решать математические, логические и экономические задачи. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту. Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы упрощают решение задач в математике (но жалко, что использовать их можно не во всех задачах).