Как решить задачу с помощью графа

4

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

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

Граф – это абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Граф из 6 вершин и 7 ребёр.

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

Полный граф – это граф со всеми возможными ребрами.

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

5 школьных команд по волейболу сыграли серию игр. Каждая команда провела с другими командами по одному матчу. Сколько всего матчей было сыграно?

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

Дерево – это граф без циклов, у которого между парами вершин имеется только одно ребро.

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac<6> <2>= 3$ варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac<3\cdot 2> <2>= 3$ — ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

Каждые три овоща на полном графе образуют треугольник.

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac<5\cdot 4> <2>= 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac<4\cdot 3> <2>= 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac<3\cdot 2> <2>= 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac<2\cdot 1> <2>= 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac<6\cdot 5 \cdot 4> <1\cdot 2 \cdot 3>= 20$ — ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

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

По аналогии с примерами 1 и 2, общее количество треугольников:

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ — общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^ <11>= 11\cdot10\cdot9 = 990 $ — ответ правильный.

Пример 4. В столовой есть на выбор

• два первых блюда: щи (Щ) и борщ (Б)
• три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)
• два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

10 Графовых алгоритмов

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

В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.

Начнём с того, что приведём определение графа.

Что такое граф?

Граф состоит из конечного множества вершин (узлов) и набора рёбер, соединяющих эти вершины. Две вершины считаются смежными, если они соединены друг с другом одним и тем же ребром.

Ниже приведён ряд базовых понятий, относящихся к графам. Они проиллюстрированы примерами на рисунке 1.

• Порядок: число вершин в графе.
• Размер: число рёбер в графе.
• Степень вершины: число рёбер, инцидентных вершине.
• Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.
• Петля: ребро, вершины которого совпадают.
• Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.
• Неориентированный граф: граф с рёбрами, которые не имеют направления.
• Взвешенный граф: рёбра такого графа имеют определённый вес.
• Невзвешенный граф: рёбра такого графа не имеют никаких весов.

1. Поиск в ширину

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

На рисунке 2 показан пример того, как выглядит поиск в ширину на графе. Жёлтым цветом помечаются обнаруженные вершины, красным — посещённые.

Применяется для:

• определения кратчайших путей и минимальных остовных деревьев;
• индексации веб-страниц поисковыми ботами;
• поиска в соцсетях;
• нахождения доступных соседних узлов в одноуровневых сетях, таких как BitTorrent.

2. Поиск в глубину

Поиск в глубину начинается с определённой вершины, затем уходит как можно дальше вдоль каждой ветви и возвращается обратно. Здесь тоже необходимо отслеживать посещённые алгоритмом вершины. Для того, чтобы стало возможным возвращение обратно, при реализации алгоритма поиска в глубину используется структура данных «стек».

На рисунке 3 показан пример того, как выглядит поиск в глубину на том же графе, который использован на рисунке 2. Граф обходится на всю глубину каждой ветви с возвращением обратно.

Применяется:

• для нахождения пути между двумя вершинами;
• для обнаружения циклов на графе;
• в топологической сортировке;
• в головоломках с единственным решением (например, лабиринтах).

3. Кратчайший путь

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

На рисунке 4 показан кратчайший путь на графе от вершины 1 до вершины 6.

Алгоритмы нахождения кратчайшего пути:

1. Алгоритм Дейкстры.
2. Алгоритм Беллмана-Форда.

Применяются в:

• картографических сервисах типа Google maps или Apple maps для прокладки маршрутов и определения местоположения;
• сетях для решения проблемы минимальной задержки пути;
• абстрактных автоматах для определения через переход между различными состояниями возможных вариантов достижения некоторого целевого состояния, например минимально возможного количества ходов, необходимого для победы в игре.

4. Обнаружение циклов

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

Алгоритмы обнаружения цикла:

1. Алгоритм Флойда.
2. Алгоритм Брента.

Применяются:

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

5. Минимальное остовное дерево

Минимальное остовное дерево — это подмножество рёбер графа, которое соединяет все вершины, имеющие минимальную сумму весов рёбер, и без циклов.

На рисунке 6 показан процесс получения минимального остовного дерева.

Алгоритмы поиска минимального остовного дерева:

1. Алгоритм Прима.
2. Алгоритм Крускала.

Применяются:

• для создания деревьев для распределения данных в компьютерных сетях;
• в кластерном анализе с использованием графов;
• при сегментации изображений;
• при социально-географическом районировании, когда смежные регионы объединяются.

6. Сильно связные компоненты

Граф считается сильно связным, если все вершины в графе достижимы из всех остальных вершин.

На рисунке 7 показан пример того, как выглядит граф с тремя сильно связными компонентами, вершины которых окрашены в красный, зелёный и жёлтый цвета.

Алгоритмы поиска сильных компонент связности:

1. Алгоритм Косараджу.
2. Алгоритм Тарьяна.

Применяются:

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

7. Топологическая сортировка

Топологическая сортировка графа — это такое линейное упорядочение его вершин, в котором для каждого направленного ребра, например (u, v), вершина u предшествует вершине v.

На рисунке 8 показан пример топологического упорядочения вершин, согласно которому вершина 5 должна следовать за вершинами 2 и 3, а вершина 6 — за вершинами 4 и 5.

Алгоритмы поиска топологической сортировки:

1. Алгоритм Кана.
2. Алгоритм на основе поиска в глубину.

Применяются:

• при планировании выполнения команд;
• при сериализации данных;
• определения порядка выполняемых при компиляции задач в Makefiles;
• для разрешения зависимостей символов в компоновщиках.

8. Раскраска графов

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

Хроматическое число графа — это наименьшее количество цветов, необходимых для окрашивания графа.

На рисунке 9 показан пример того, как выглядит раскраска вершин графа с использованием 4-х цветов.

Алгоритмы с раскраской графов:

1. Алгоритмы, использующие поиск в ширину или поиск в глубину.
2. Жадная раскраска.

Применяются для:

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

9. Максимальный поток

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

На рисунке 10 показан пример того, как выглядит нахождение максимального потока сети и определение конечного значения потока.

Алгоритмы нахождения максимального потока:

1. Алгоритм Форда-Фулкерсона.
2. Алгоритм Эдмондса-Карпа.
3. Алгоритм Диница.

Применяются:

• в авиакомпаниях для составления полётного расписания экипажей;
• при сегментации изображений для определения фона и переднего плана изображения.

10. Паросочетания

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

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

Алгоритмы нахождения паросочетаний:

1. Алгоритм Хопкрофта-Карпа.
2. Венгерский алгоритм.
3. Алгоритм сжатия цветков.

Применяются:

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

Заключение

Надеюсь, статья была полезной и в простой и краткой форме познакомила вас с графовыми алгоритмами. ��

А с реализациями графовых алгоритмов можно ознакомиться в модулях на Python networkx и igraph.

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

Мне нравится Проект нравится 23 участникам

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе — семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках — проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

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

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

Виды графов:

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

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

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

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

Задача 1.

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

Задача 2.

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

Вершины графа — это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

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

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

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

Получите невероятные возможности

Конспект урока «Решение задач с помощью графов»

Прежде чем приступить к решению задач, стоит сказать, что графы, о которых пойдёт речь, к аристократам былых времён никакого отношения не имеют. У наших графов в корне есть греческое слово «графо», что значит «пишу». Этот же корень («граф») встречается, например, в словах «график, «биография», «орфография» и некоторых других.

Давайте выясним понятие графа на примере решения задачи.

В первенстве класса по настольному теннису шесть участников: Андрей, Саша, Вова, Оля, Дима и Лена. Каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Сашей, Олей и Леной; Саша, как уже говорилось, с Андреем и ещё с Олей; Вова – с Олей, Димой и Леной. Сколько игр уже проведено и сколько ещё осталось?

Итак, изобразим данные этой задачи в виде схемы. Участников первенства обозначим точками, расположив их по окружности: Андрей – А, Саша – ЭС, Вова – ВЭ, Оля – О, Дима – ДЭ, Лена – ЭЛЬ.

Если двое участников уже сыграли между собой, то будем соединять, обозначающие их точки отрезками. В условии задачи сказано, что Андрей сыграл с Сашей, Олей и Леной.

Мы уже видим, что Саша сыграл с Андреем, а ещё он сыграл с Олей.

Вова сыграл с Олей, Димой и Леной.

Получившаяся схема называется графом. Точки А, С, В, О, ДЭ, Л называются вершинами графа. Отрезки, которые соединяют вершины графа, называются рёбрами графа. Каждое ребро соединяет две вершины графа.

При этом обратите внимание, что точки, в которых пересекаются рёбра графа, не являются его вершинами.

У графа 7 рёбер. Это означает, что к настоящему моменту было проведено 7 игр.

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

Итак, известно, что Андрей сыграл с Сашей, Олей и Леной. А значит, он не играл с Вовой и Димой.

Также известно, что Саша сыграл с Андреем и с Олей, а значит, он не сыграл с Вовой, Димой и Леной.

Вова сыграл с Олей, Димой и Леной. Получается, что он не сыграл с Андреем и Сашей. Но соответствующие отрезки уже проведены.

Оля сыграла с Андреем и Сашей, а также с Вовой. Это значит, что она ещё не сыграла с Димой и Леной.

Дима сыграл только с Вовой. Ему предстоит сыграть с Олей, Сашей и Андреем, но эти отрезки мы уже провели. Осталось провести отрезок от Димы к Лене.

Лена сыграла с Андреем и Вовой. Ей предстоит сыграть с Димой, Олей и Сашей, но эти отрезки мы уже провели. Больше ничего добавлять не надо.

Мы добавили 8 рёбер. Это значит, что осталось провести ещё 8 игр. Получается, что ответ на вопрос задачи будет таким: проведено 7 игр, осталось провести 8 игр.

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

Также отметим, что иногда рёбра удобнее изображать не отрезками, а «дугами».

Граф можно представить как набор пуговиц, некоторые из которых соединены нитями. Пуговицы – это вершины графа, нити – его рёбра.

При этом, где именно расположены пуговицы, и как проходят нити не важно, ведь граф от этого не меняется. Важно то, какие пары пуговиц (то есть вершин графа) соединены нитями.

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

Если из вершины графа выходит чётное количество рёбер, то её называют чётной. А если из вершины графа выходит нечётное количество рёбер, то её называют нечётной.

Посмотрите на такой граф.

У него вершины 1 и 4 являются нечётными, так как из них выходят по 3 ребра.

А вот вершины 2, 3 и 5 являются чётными, так как из вершины под номером 2 выходят 4 ребра, из вершины под номером 3 тоже выходят 4 ребра, а из вершины под номером 5 выходят 2 ребра.

Решим следующую задачу. Встретились три подруги: Белова, Чернова и Краснова. На одной из них было чёрное платье, на другой – красное, на третьей – белое. Девочка в белом платье говорит Черновой: «Нам надо поменяться платьями, а то у всех троих цвет платьев не соответствует фамилиям». Кто в какое платье был одет?

На одном из наших занятий было предложено решить эту задачу с помощью таблицы. Давайте решим её с помощью рисунка.

Обозначим фамилии девочек буквами. Пусть напротив буквы Б будет белое платье, напротив буквы Ч – чёрное, напротив буквы К – красное.

Соединим пунктирной линией букву Б и белое платье. Это означает, что Белова не в белом платье. Также соединим пунктирными линиями букву Ч и чёрное платье, букву К и красное платье. Это означает, что Чернова не в чёрном платье, а Краснова не в красном платье.

В условии задачи говорится, что девочка в белом платье говорит Черновой: «Нам надо поменяться платьями, а то у всех троих цвет платьев не соответствует фамилиям». Получается, что Чернова одета не в белое платье. Поэтому соединим букву Ч с белым платьем пунктирной линией.

Теперь, внимательно посмотрев на рисунок, становится понятно, что ни Белова, ни Чернова не одеты в белое платье. Значит, в белое платье одета Краснова. Поэтому соединим букву К и белое платье сплошной линией.

Так как на Чернова была одета не в белое платье, а также на ней не могло быть чёрного платья, то, следовательно, она была в красном платье. Соединим сплошной линией букву Ч и красное платье.

Мы выяснили, что Краснова была в белом платье, а Чернова была в красном. А значит, Белова была в чёрном платье. Соединим букву Б и чёрное платье сплошной линией.

Ответ на вопрос задачи будет таким: Белова была одета в чёрное платье, Чернова – в красное платье, Краснова – в белое платье.

И решим ещё одну задачу. Из города А в город Б ведут 3 дороги, а из города Б в город Б – 4 дороги. Сколькими способами можно проехать из города А в город В, если по пути надо обязательно заехать в город Б?

Решение. Отметим точками города А, Б и В. В условии задачи сказано, что из города А в город Б ведут 3 дороги. Также сказано, что из города Б в город В ведут 4 дороги.

Возьмём одну дорогу, которая ведёт из города А в город Б. Её можно продолжить до города В четырьмя различными способами.

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

То же самое можно сказать и про третью дорогу, ведущую из города А в город Б, то есть её также можно продолжить до города В четырьмя способами.

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

Таким образом, из города А в город В через город Б можно проехать 3 умножить на 4, то есть 12 способами.