Примеры решений задач по теории графов
На этой странице вы найдете готовые примеры по теории графов (разделу дискретной математики). Теория графов берет свое начало еще в 18 веке, когда Эйлер написал свою знаменитую статью о Кёнигсберских мостах (см. решения на алгоритм Эйлера). Сейчас достижения теории графов применяются в строительстве, программировании, электротехнике, социологии, экономике, биохимии, телекоммуникациях и планировании транспортных коммуникаций, психологии и т.д.
Какие виды заданий решаются студентами?
Задачи, решаемые в рамках теории графов, можно условно поделить на несколько групп:
- Определение графа и его свойства. Задачи на построение графа по заданному числу вершин и ребер, построение матрицы смежности и инцидентности, вычисление основных характеристик графа (связность, простота, эйлеровость, полнота, двудольность, регулярность графа и т.п.). Проверка планарности и изоморфности графов.
- Действия с графами. Добавление и удаление вершин и ребер, компонент связности, слияние вершин, объединение, пересечение, соединение и декартово произведение графов. Построение дополнение графа.
- Маршруты, цепи и циклы, контуры. Эйлерова цепь и гамильтонов цикл и проверка графа на выполнение этих свойств.
- Вычисление характеристик графа. Расстояния: диаметр графа, центр графа, радиус графа. Вычисление цикломатического и хроматического числа.
- Задачи на графах. Задача о кратчайшем пути (алгоритм Дейкстры, Беллмана, построение дерева путей). Задача на построение минимального остовного дерева (алгоритм Краскала). Задача о максимальном потоке в сети (алгоритм Форда-Фолкерсона). Задача о раскраске графа.
- Изучение деревьев (специальных видов графов без циклов). Деревья применяются в шифровании, программировании и многих других прикладных областях.
Лучшее спасибо — порекомендовать эту страницу
Задачи по графам с решением онлайн
Задача 1. Постройте граф отношения «x+y ≤7» на множестве М=. Определите его свойства.
Построение графа отношения (pdf, 134 Кб)
Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.
Решение по алгоритму Дейкстры (pdf, 196 Кб)
Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.
Решение задачи о нахождении максимального потока в сети (pdf, 282 Кб)
Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).
Решение задачи на построение остовного дерева (pdf, 173 Кб)
Задача 5. Требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути $P_$ из вершины $i$ в вершину $j$, затем найти все сечения $S_$ между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет. Напомним, что для нахождения путей из вершины $i$ в вершину $j$ нужно раскрывать минор структурной матрицы$М_$ (вычеркивать из структурной матрицы строчку с номером $j$ и столбец с номером $i$). Сечения же находятся отрицанием путей (конъюнкция меняется на дизъюнкцию и наоборот).
Задача 6. Для графа $G=(X,U)$ выполнить следующее:
1.1. Построить:
— матрицу смежности,
— матрицу инцидентности.
1.2. Определить степени для всех вершин $$ данного графа.
Задача 7. Найти все кратчайшие пути в орграфе, используя алгоритм Флойда.
Задача 8. Задан $G (X,ГX)$
$X=$,
ГХ:
Гx1=, Гx2=, Гx3=, Гx4=, Гx5=.
Определить хроматическое и цикломатическое число данного графа.
Задача 9. Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить.
3.1. Локальные степени и окружения каждой вершины в виде структуры смежности;
3.2. Построить матрицы инцидентности и смежности;
3.3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;
3.4. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
3.5. Определить центр, диаметр и радиус графа.
Считая граф ориентированным, определить
3.6. Степени вершин
3.7. Матрицы инцидентности и смежности.
3.8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.
Решение теории графов на заказ
Выполняем решение задач, контрольных и практических работ по любым разделам теории графов. Подробное оформление, таблицы, чертежи, пояснение, возможно написание программ на языках программирования (для алгоритмов на графах) или использование специальных программ. Решение экономических задач, связанных с теорией графов.
Стоимость примера от 100 рублей , оформление производится в Word, срок от 2 дней. Также оказываем помощь в сдаче тестов по графам.
Графы. Применение графов к решению задач
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.
Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2. Теоретический материал к теме “Графы”.
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Рассмотрим две задачи.
Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.
Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?
Решение: Занумеруем последовательно клетки доски:
А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:
Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.
Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.
Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:
Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.
Степени вершин и подсчет числа ребер графа
Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.
Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.
Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:
Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.
Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”
Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:
Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:
Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.
Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?
Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.
Сейчас мы доказали теорему об Эйлеровых графах:
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
И в заключение – задача о Кенигсбергских мостах.
Задача 7. На рисунке изображена схема мостов города Кенигсберга.
Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?
3. Задачи к теме “Графы”
Понятие графа.
1. На квадратной доске 3×3 расставлены 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 раз?
Практическое применение графов — Алгоритмы на графах
Вы уже знаете, что граф — это фигура, состоящая из вершин и соединяющих их ребер. С помощью графов решают многие важные классы задач, с которыми мы познакомимся далее в этом уроке.
Выбираем оптимальный путь на метро
Представьте себе схему метро крупного города: скорее всего, в центре будут пересекаться несколько разных веток. Из-за этого получается, что проехать между станциями можно разными способами.
Например, в московском метро от станции «Фрунзенская» до станции «Полянка» можно доехать двумя способами:
Попробуем определить, какой из этих маршрутов короче. Чтобы посчитать общее время в пути, нужно знать, сколько времени занимает проезд между соседними станциями и сколько времени занимает переход.
По сути, карта метро — это граф. Немного дорисуем его, чтобы обозначить переходы с ветки на ветку. На новом рисунке проставим время в минутах рядом с каждым ребром — перегоном между соседними станциями или переходом:
Теперь можно вычислить полное время на каждом маршруте и выбрать самый короткий. Решение выглядит обманчиво простым. Люди интуитивно отбрасывают заведомо плохие варианты и сразу видят два подходящих маршрута. У компьютера интуиции нет — он переберет все маршруты, которых в действительности гораздо больше двух.
Задачи такого рода в программировании относят к классу «задачи о кратчайшем пути». Число, приписанное каждому ребру, называют весом ребра, а сам граф называют взвешенным.
Неочевидно, почему используют слово «вес», а не «длительность пути». Этому есть объяснение. За названием «взвешенные графы» скрываются разные задачи, решаемые одним и тем же способом. Для некоторых задач числа обозначают время, для других — расстояния, для третьих — денежные суммы, для четвертых — вес.
Этот термин широко используется в математике — там есть весовые коэффициенты или весовая функция. Так что программисты получили этот термин в наследство от математиков.
Строим маршрут по автомобильным дорогам
Рассмотрим еще одну задачу — построение автомобильного маршрута. Для начала нужно определиться с ребрами и вершинами:
- Ребрами будут считаться сами дороги
- Вершинами — развилки и пересечения дорог
Здесь мы сталкиваемся с одной сложностью, которой не было в задаче с метро. В отличие от метро, автомобильные дороги могут быть с односторонним движением. Рисуя граф, мы должны учитывать эту особенность.
Граф движения по городу может выглядеть так, как показано на картинке ниже. Голубым цветом нарисованы проспекты, а зеленом — односторонняя часть пути во дворах:
На этот граф мы добавили стрелки, которые показывают направление движения:
- Если дорога односторонняя, мы рисуем ребро со стрелкой
- Если дорога двухсторонняя, мы рисуем два ребра с противоположными стрелками
Если у ребер графа задано направление, такой граф называют направленным или ориентированным. Часто название «ориентированный граф» сокращают до «орграфа».
Обратите внимание, что граф автомобильных дорог не только ориентированный, но и взвешенный — ведь нам нужно находить по нему оптимальные маршруты. В отличие от метро, на автомобильных дорогах бывают пробки. Поэтому мы не можем заранее присвоить ребрам точный вес — придется обозначать его как время проезда без учета пробок.
Выбираемся из лабиринта
Иногда нам не нужно выискивать идеальный маршрут — достаточно выяснить, можно ли его построить. Для примера представьте, что нам надо выбраться из лабиринта:
В таком случае мы согласимся на любой путь и не будем уточнять, если ли пути покороче.
Есть несколько стратегий выхода из лабиринта. Например, есть правило правой руки, которое предлагает такую стратегию:
- Мы кладем правую руку на стену и начинаем идти по лабиринту
- Если мы пришли к развилке, всегда выбираем правый путь
- Если мы пришли в тупик, возвращаемся к последней развилке и идем в следующий по счету коридор
- Если все коридоры закончились тупиком, возвращаемся к предпоследней развилке и продолжаем обход справа налево
Конечно, коридоры можно обходить и слева направо, тогда речь будет идти о правиле левой руки — оно работает абсолютно так же. Здесь важно придерживаться всегда одной стороны, не смешивая повороты направо и налево.
Как и в случае с автомобильной картой, вершинами графа будут только места развилок и тупики. Посмотрим, как будет выглядеть маршрут по лабиринту:
Рассмотрим этот рисунок подробнее:
- Красными линиями обозначены ребра графа
- Кружками обозначены вершины
- Направление обхода графа показано синим цветом
Стратегия предполагает, что мы пытаемся пройти как можно глубже, а если попадаем в тупик, возвращаемся назад. На рисунке это тоже видно — синяя линия часто идет в двух направлениях.
Такой способ движения по графу называется обходом в глубину. Этот алгоритм применяется для поиска вершины с определенными свойствами, поэтому часто употребляют похожий термин — «поиск в глубину». В профессиональной литературе вы можете встретить аббревиатуру DFS — depth first search, то есть «поиск сначала в глубину».
Этот алгоритм прекрасно работает, если в лабиринте нет замкнутых коридоров или петель. Если мы попадем на петлю, мы можем вечно ходить по одному и тому же коридору, как показано на рисунке:
Если мы нарисуем граф для такого лабиринта, мы обнаружим такую же петлю. Графы с петлями называются циклическими и требуют осторожности при обходе:
Обходя лабиринт с петлями, можно помечать посещенные развилки мелом. Встретив пометку, мы узнаем, что попали в цикл. Действовать в этом случае надо так же, как и в тупике — развернуться и идти назад.
Обходим препятствия
В ролевых и стратегических играх пользователь управляет игровыми юнитами. Например, он может отправить боевой или строительный юнит на другой конец карты. Как правило, на карте встречаются препятствия — непроходимые горы и озера.
Игровая карта может выглядеть так:
Двигаясь по карте, юниты уверенно огибают преграды и достигают цели за кратчайшее время. Разберемся, как это работает.
Как и в предыдущих задачах, мы сначала решаем, что будет считаться ребрами и вершинами графа. В компьютерных играх вершины размещают в клетках карты. Ребра связывают соседние пустые клетки, в которых нет гор или озер.
Представим, что нам надо добраться из вершины Н в вершину К:
Поиск в глубину поможет найти дорогу, но если на карте много поворотов и узких проходов, эффективнее будет другой алгоритм. Он называется волновым, потому что напоминает волны, кругами расходящиеся на воде от брошенного камня:
Сначала мы проверяем соседей начальной вершины, затем — соседей соседей, и так далее, каждый раз удаляясь от начальной вершины на один шаг. В какой-то момент очередной круг доберется до конечной вершины. Это будет означать, что путь найден:
Другое название этого алгоритма — поиск в ширину или BFS, breadth first search. Он позволяет найти маршрут с наименьшим количеством ребер. Впрочем, у него гораздо больше применений. В частности, одна из его модификаций позволяет закрашивать на изображениях замкнутые области произвольной формы.
Может показаться, что задачи на графах касаются в первую очередь карт или каких-то картинок, но это не так. Далее мы узнаем, как графы применяют при решении экономических и логистических задач.
Считаем сдачу
Одна из задач, которую решает программное обеспечение банкоматов и вендинговых аппаратов — выдача сдачи. Как правило, автоматы пытаются выдать сдачу наименьшим количеством банкнот или монет.
Номиналы монет подбираются так, чтобы ими можно было выдать любую сумму. Например, сдачу в 8 рублей можно выдать тремя монетами: 5 рублей, 2 рубля и 1 рубль.
Чтобы посчитать сдачу, можно использовать простой алгоритм выбора монет:
- Пока можем, набираем сумму самыми крупными монетами
- Затем переходим к следующим по номиналу монетам, и так далее
Проблема в том, что иногда в автомате заканчиваются монеты определенного номинала. Отсутствие двухрублевых монет не скажется на работе алгоритма: он выберет одну пятирублевую монету и три однорублевых.
Но если в автомате закончатся рублевые монеты, алгоритм не сможет вернуть сдачу в 8 рублей. Сначала он выберет монету в 5 рублей, потом монету в 2 рубля, а дальше начинаются сложности — надо выбрать монету в 1 рубль, а они закончились.
Даже в этом случае задача может быть решена — сдачу можно выдать четырьмя монетами по 2 рубля. Проблема в том, что простой алгоритм этот вариант не найдет.
Более сложный алгоритм работает на графах. Это может показаться странным, потому что не совсем очевидно, как они сюда относятся:
На рисунке мы видим, что каждый узел графа может содержать набор монет. Двигаясь по стрелкам, мы добавляем к набору одну новую монету. Мы начинаем с пустого узла, в котором нет ни одной монеты. Далее мы ищем узлы, где достигается нужная сумма в 8 рублей.
У нас нет карты, которая стала бы основой для графа, потому что мы не храним все узлы графа. Вместо этого, можно генерировать новые соседние узлы по мере надобности, следуя простым правилам.
Подобные графы часто встречаются в программировании, они называются неявными. Неявный граф не требует хранения своих узлов — узлы можно вывести или вычислить.
Хорошим кандидатом для решения задачи о монетах будет алгоритм поиска в ширину. Мы продвигаемся во всех направлениях от пустого узла, в поисках узлов, содержащих сумму 8 рублей.
К сожалению, этот алгоритм не очень эффективен. Нам надо дать сдачу наименьшим числом монет, поэтому мы можем всегда начинать с монеты самого крупного номинала. Это решение похоже на то, которые мы рассматривали в начале. Разница только в том, что у нас остается возможность найти правильный ответ, даже если каких-то номиналов не хватает.
Такой поиск похож на поиск в ширину, у которого есть предпочтительное направление. Мы можем использовать его, потому что у нас есть дополнительная информация о задаче.
При работе с графами программисты часто используют подобную информацию для того, чтобы ускорить алгоритм. Такие модификации называются информированными алгоритмами. Классические алгоритмы без дополнительной информации называют неинформированными.
Выводы
Повторим ключевую мысль из этого урока — графы решают множество практических задач, с которыми мы сталкиваемся каждый день. Изучив эту тему, вы сможете:
- Находить кратчайшие маршруты на карте метро — решать задачи о кратчайшем пути с помощью взвешенных графов
- Строить пути на автомобильных картах с помощью ориентированных графов
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях:
Решение задач с помощью графов
Назад Вперёд
Цели:
- закрепить понятие графа и отработать навыки использования графов для решения задач;
- проверить уровень усвоения понятия графа через умение применять имеющиеся знания для решения новых задач.
- развивать логическое и творческое мышление учащихся, сообразительность, наблюдательность, интуицию и адекватность при оценке работы одноклассника;
- формировать активный познавательный интерес к предмету.
- воспитывать культуру общения на уроке, аккуратность, внимательность и взаимоуважение.
ПЛАН УРОКА
1. Организационный момент
2. Великий Эйлер и его задача
Кенигсбергские мосты (совместная работа с учителем)
Осознание, осмысление, обобщение
3. Задача о 15 мостах (самостоятельная работа)
ХОД УРОКА
1. Организационный момент
Домашнее задание. (Презентация, сл.2)
Применение теории графов. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Давайте вспомним основные понятия теории графов (Презентация, сл.3)
По ходу урока ученики работают с электронными тетрадями, которые можно подготовить в PowerPoint. Все необходимые зарисовки они делают с помощью средств рукописных заметок в режиме показа презентации. После урока презентацию со своими записями ученики сохраняют и уносят домой для подготовки домашнего задания (приложение 3)
2. Великий Эйлер и его задача
Учитель: Сегодня на уроке мы продолжим изучение графов и познакомимся с еще одним методом решения задач.
(Презентация, сл.4)
Одним из крупнейших математиков XVIII века был Леонард Эйлер. Он родился в швейцарском городе Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения.
Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:
«Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может».
(Презентация, сл.5)
«Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D — части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g «.
Ученики в электронных тетрадях пробуют прорисовать возможные пути движения ( приложение 3, сл. 2). Один или два ученика вызываются к доске и тоже пробуют рисовать пути движения (Презентация, сл.5)
Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
Дать время на поиск решения.
Простой путь решения задачи, казалось бы, такой: сделать все возможные пробы таких переходов, т. е. перечислить все возможные пути, и затем рассмотреть, какой или какие из них удовлетворяют условиям вопроса. Но, очевидно, что даже в случае только семи мостов приходится делать слишком много таких проб. А при увеличении числа мостов такой способ решения практически совершенно немыслим. Да, кроме того, при одном и том же числе мостов задача изменяется в зависимости еще от расположения этих мостов.
Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,
«Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, — таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре — A, B, C, D.»
(Презентация, сл.6)
Ход решения задачи будем представлять в виде графа, где вершины — острова и берега, а ребра — мосты.
«Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным — по три моста».
(Презентация, сл.7)
То есть нам нужно определить степень каждой вершины и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.
«Когда это определено, применяем следующее правило: если все вершины имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить переход, как это предписано, но только начало обхода непременно должно быть взято в одной из этих двух вершин, а конец обхода непременно должен быть во второй нечетной вершине. Если, наконец, больше двух нечетных вершин, то тогда такое движение вообще невозможно. «.
Итак, используя правило Леонардо Эйлера мы можем сделать
ВЫВОД. Так как количество нечетных вершин в графе равно 4, а это > 2, то обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов нельзя.
(Презентация, сл.8) (приложение 3, сл.3)
Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах. Во всяком случае, мы можем сразу убедиться в возможности или невозможности решения.
Это правило записано у вас в тетрадях:
(Презентация, сл.9) (приложение 3, сл.4)
1. Нарисовать граф, где вершины — острова и берега, а ребра — мосты.
2. Определить степень каждой вершины и подписать возле нее.
3. Посчитать количество нечетных вершин.
4. Обход возможен:
a. ЕСЛИ все вершины — четные, и его можно начать с любого участка.
b. ЕСЛИ 2 вершины — нечетные, но его нужно начать с одной из нечетных местностей.
5. Обход невозможен, если нечетных вершин больше 2.
6. Сделать ВЫВОД.
7. Указать Начало и Конец пути.
Вопрос разрешимости таких задач также входит в теорию графов. Графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задание: Графы,нарисованные у вас в тетрадях,необходимо достроить до Эйлеровых.
(Презентация, сл.10) (приложение 3, сл.5)
Проверка проходит сразу по окончании работы: либо учитель сам дорисовывает недостающие линии на доске, либо запускает анимацию.
А теперь, основываясь на нашем правиле, решим задачу о 15 мостах.
Задача о 15 мостах.
(Презентация, сл.11)
В некоторой местности через протоки переброшено 15 мостов.
У вас в тетрадях есть этот рисунок. Можно ли обойти все мосты, проходя по каждому из них только один раз?
Ученики в электронных тетрадях пробуют прорисовать возможные пути движения (приложение 3, сл.6).Дать время на поиск решения.
Построим граф, где вершины — острова и берега, а ребра — мосты.
(Презентация, сл.12)
Нечетные вершины: D, E.
ВЫВОД: Так как количество нечетных вершин = 2, то обход возможен.
Его Начало может быть в местности D, а Конец в местности E.
Сегодня мы с вами познакомились еще с одним методом решения задач с помощью графов.
Поучительная сторона этих задач состоит в исследовании, возможно или нет решение данной задачи, прежде чем приниматься за само решение.
Мы еще раз убедились, что теория графов позволяет быстро и изящно решать задачи, которые весьма трудно решить другими методами и позволяет решить не только одну отдельно взятую задачу, но и находить методы решения целого класса задач.
Домашнее задание: Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? (решить с помощью графа)
(Презентация, сл.13) (приложение 3, сл.7)