лекция. Теория графов. Решение задач. Лекция Курбанова И.Н. История возникновения теории графов
 Скачать 0.56 Mb.
|
Применение графов к решению задач.Практический материал по теме «Графы» в 6-м классе. Понятие «графа» в школьной программе не дается. Отличаясь простотой теоретических сведений, наглядностью и доступностью, теория графов поможет решить довольно сложные задачи учащимся 6 класса. В некоторых задачах условие записанное с помощью рисунка, помогает найти правильный ход решения. Задача: Я задумал число. Если к нему прибавить 24, потом полученную сумму умножить на 9, затем из произведения вычесть 76 и, наконец, полученную разность разделить на 19, то получится число 23. Найти задуманное число. Решение: 1 способ: Сделаем рисунок.  Исходя из рисунка видим, чтобы найти задуманное число, надо выполнить обратные действия:  2 способ:  Видно, что решать задачу следует с конца, заменяя каждое действие на обратное ему. Получаем:  Ответ: 33. Задача: Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий? Решение: Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия. 1)  2)  3)  4)  Из рисунка видно, что на вокзале встретились 5 мальчиков. Фигуры, которые получились при решении этих задач, состоят из точек и линий, соединяющих эти точки. Такую фигуру называют графом. Линии графа называют ребрами, а точки – вершинами. В графе не обязательно, чтобы каждая вершина была соединена со всеми остальными.  Если в графе ни одна часть не является замкнутой линией, то такой граф называется деревом. Графы помогают решать задачи.  Классная работа: Задача 1. Если задуманное число умножить на 5 и к результату прибавить 1, потом сумму увеличить в 6 раз и к результату прибавить 2, затем новую сумму умножить на 7 и полученное произведение увеличить на 4, то получим число, которое в 16 раз больше числа 135. Найдите это число. Решение: Сделаем рисунок (построим граф).  Решая, действия выполняем наоборот.   Ответ: 10. Задача 2. В первом матче футболисты «Звездочки» забили в ворота противника половину мячей, забитых ими во втором матче, и еще один мяч. Во втором матче они забили вдвое меньше мячей, чем в третьем матче, и еще один мяч. В третьем матче они забили вдвое меньше мячей, чем в первом, и еще один мяч. Сколько всего мячей забили футболисты «Звездочки» за три матча? Решение:  Из рисунка видно, что в каждой игре было забито одинаковое число мячей. В каждой игре забито по 2 мяча. Ответ: 6 мячей забито в 3-х играх. Задача 3. Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II – половину остатка и еще 1 яблоко, III – половину нового остатка и еще 1 яблоко и т.д. Последнему – шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница? Решение: Составим граф.  Решая, действия делаем обратно.  Ответ: 126 яблок. Домашнее задание. Задача. На вопрос путника: «Сколько у тебя в стаде голов скота?» - пастух ответил: «Если бы к моему стаду добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козленок». Сколько голов скота было в стаде? Решение: Составим граф по условию задачи.  Решаем обратно.  Ответ: в стаде 59 голов скота. Методические рекомендации к теме “Графы”. Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая. Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоит рассказывать обо всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. Тема “Графы” в 7–м классе. Введение Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач. Понятие графа. Повторение всех понятий, пройденных в 6-м классе. Рассмотрим две задачи. Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ? Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.  Теперь сразу видно, что долететь с Земли до Марса нельзя. Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.  Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ? Решение: Занумеруем последовательно клетки доски:  А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:  Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями. Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен. Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:  Такие одинаковые, но по-разному нарисованные графы, называются изоморфными. Степени вершин и подсчет числа ребер графа Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной. С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу. Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным  . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.Ответ. Соединить телефоны таким образом невозможно. Теорема: Любой граф содержит четное число нечетных вершин. Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин. Связность графа Есть еще одно важное понятие, относящееся к графам – понятие связности. Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа. Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города можно добраться в любой другой. Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:  Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного. Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.” Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:  Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности: Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний. Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать. Графы Эйлера Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами. Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?  Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом. Сейчас мы доказали теорему об Эйлеровых графах: Теорема: Эйлеров граф должен иметь не более двух нечетных вершин. Дополнительные задачи по теме “Графы” 1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?
Решение. Занумеруем клетки доски, как показано на рисунке:  Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:
При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно. 2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ? Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя. Степени вершин и подсчет числа ребер. 3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве. Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200. 4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ? Ответ. Нет (теорема о четности числа нечетных вершин). 5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ? Ответ. Нет, не может. 6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог? Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может. 7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно. Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа. Связность. 8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого. Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой. Графы Эйлера. 9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист а) не с него начал и не на нем закончил? б) с него начал, но не на нем закончил? в) с него начал и на нем закончил? 10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор ровно 1 раз?  Гамильтоновы циклы. Существует еще одна очень интересная задача, связанная с графами. В ней требуется отыскать простой цикл, который проходит через все вершины данного связного графа. Эта задача является частным случаем «задачи коммивояжера1», суть которой в следующем. Коммивояжер (разъездной торговец) должен проехать по всем городам некоторого региона и вернуться в исходный пункт. При этом целесообразно так составить маршрут, чтобы в каждом городе побывать ровно один раз (иначе покупатели могут предъявить счет за некачественный товар). У коммерсанта естественно, имеется карта дорог региона. Циклы, обладающие указанным выше свойством, называют гамильтоновыми, в честь изобретателя Гамильтона, придумавшего игру – головоломку, в которой требовалось отыскать такие пути. В отличие от эйлеровых циклов, для гамильтоновых циклов нет исчерпывающего условия, подобного теореме 4. Имеется следующий достаточный признак. Теорема 5. Пусть связный граф имеет не меньше четырех вершин (p>3) и степень каждой вершины не меньше p/2, тогда в графе имеется гамильтонов цикл.  Рассмотрим граф на рисунке. У него 6 вершин, при этом пять вершин имеют степень три, и одна степень пять. Согласно теореме, в этом графе существует гамильтонов цикл. Нетрудно проверить, что таким циклом является цикл (AEFDBCA). Олимпиадные задачи на использование теории графов. Задача 1: В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве? Решение: Общее число дорог равно 100 • 4/2 = 200. Задача 2: В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей? Решение: Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме. Задача 3: В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими? Решение: Нельзя. Примените теорему о числе нечетных вершин. Задача 4: У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств? Решение: Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин. Задача 5: Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? Решение: Если в государстве k городов, то дорог – 3k/2. Это число не может быть равно 100. Задача 6: Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера? Решение: Да, верно, иначе нарушается теорема о числе нечетных вершин. Задача 7: Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно. Решение: Это в точности теорема о нечетных вершинах. Задача 8: Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими? Решение: Нет, нельзя. Примените теорему к графу, вершины которого – данные отрезки, а ребро соединяет две вершины тогда, когда два соответствующих отрезка пересекаются.
Доказательство леммы о рукопожатиях Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды. Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины). Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно. Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные. Как рассуждаем: Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях. Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых. Как рассуждаем: Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3. Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие. Теория графов широко применяется во многих смежных математических дисциплинах. Далее приводится пример применения графов в теории кодирования.  |
