Решение графов в excel
Обновлено: 07.07.2024
Построить максимальный поток от истока I к стоку S в сети, заданной графом (см. рис.1):
В скобках заданы пропускные способности ребер в направлении от меньшего номера вершины к большему и в обратном направлении.
Решение задачи:
Согласно алгоритму Форда-Фалкерсона:
Строим произвольный начальный поток на сети.
Находим подмножество А вершин, достижимых из истока I по ненасыщенным ребрам.
Если S не принадлежит A, то построенный поток максимальный и задача решена. Если S принадлежит A, то переходим к пункту 4.
Выделяем путь из I к S, состоящий из ненасыщенных ребер, и увеличиваем поток xij по каждому ребру этого пути на величину, равную min по всем ребрам (i,j) выделенного пути. После построения нового потока возвращаемся к пункту 2 алгоритма.
Реализация в Excel
В качестве начального потока выбираем, например, поток, проходящий по ребрам 1-3-5-6. Максимальная величина потока, который можно пропустить по этим ребрам, равна 2.
На чистом рабочем листе заполняем форму решения задачи. В ячейки B 3: G 8 заносим данные о пропускных способностях ребер сети.
Ниже строим матрицу начального потока на сети.
Обратите внимание на то, что матрица начального потока должна быть антисимметрична. Поэтому сначала заполняем ее диагональные элементы, выделяя их каким-либо цветом, и ту часть матрицы, которая находится выше главной диагонали.
Для заполнения нижней части матрицы воспользуемся функцией ТРАНСП(массив).
Эта функция возвращает вертикальный диапазон ячеек в виде горизонтального и наоборот. Функция ТРАНСП должна быть введена как формула массива в интервал, который имеет столько же строк и столбцов, сколько столбцов и строк имеет аргумент массив.
Для заполнения столбца В13:В17 установите курсор в ячейку В13, введите формулу = - ТРАНСП( C 12: G 12) и нажмите клавишу < ENTER > (знак <–> перед формулой вводится для того, чтобы матрица получилась антисимметричной). В ячейке появится знак ошибки. Затем нужно выделить диапазон В13:В17, нажать клавишу , а затем клавиши . В результате будет сформирован первый столбец матрицы потока. Остальные столбцы под нижней диагональю заполняются аналогично.
Ниже матрицы потока строим матрицу ненасыщенности ребер.
Для этого в ячейку В21 вводим формулу:
После чего выделяем диапазон В21: G26, нажимаем клавишу , а затем клавиши .
В результате третья матрица заполняется значениями, равными «недогрузке» ребер.
Находим ненасыщенные пути. Для этого в матрице ненасыщенности выбираем ненулевые элементы:
Таким образом, можно выбрать путь 1-2-4-6 с максимально возможным объемом дополнительного груза, равным 4.
Для удобства можно выписать процедуру поиска ненасыщенного пути справа от матрицы ненасыщенности ребер:
Выделяя потоки по выбранным ребрам каким-либо цветом, легко найти их минимум (см. рис.4). Строим справа матрицу дополнительного потока по аналогии с матрицей начального потока.
Ниже строим матрицу нового потока №1 путем суммирования матриц начального и дополнительного потока (не забываем, что формулы вводятся как формулы массива). Снова находим матрицу ненасыщенных ребер для потока №1.
Процедуру повторяем до тех пор, пока не останется ненасыщенного пути из вершины 1 в вершину 6. Поток, найденный на этом шаге, будет максимальным.
Задание для самостоятельной работы
Учащиеся выбирают номер варианта согласно списку.
Сеть содержит 10 вершин (рис. 5). Пропускные способности дуг заданы таблицей. Найти максимальный поток между вершинами 1 и 10 (номера вариантов указаны в верхнем левом углу таблицы).
В статье Поиск решения MS EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель) рассматривались модели, в которых коммивояжёру требуется посетить все имеющиеся города. В этой задаче посещение всех городов не требуется.
Задача
Имеется 11 городов, координаты которых известны. Маршруты проложены только между некоторыми городами (неполный граф). Найти кратчайший путь между 2-мя заданными городами. Построить Линейную модель.
Создание модели
Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера ).
Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);1)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);1))^2 +(ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);2)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);2))^2)
Теперь создадим линейную модель для решения задачи с помощью Поиска решения .
Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .
Переменные (выделено зеленым) . В качестве переменных модели следует взять номера маршрутов между городами: если маршрут включен в кратчайший путь, то переменная =1, если нет, то =0. Ограничения (выделено синим) . Необходимо, чтобы из каждого города, в котором побывал путешественник, был входящий и выходящий маршрут. Так как входящий маршрут обозначается 1, а исходящий -1, то их сумма, равная 0, будет означать, что в город вошли и вышли (включен в кратчайший путь). Исключение составляют город – начальная точка путешествия (сумма =-1) и город – конечная точка (сумма =1). Изменяя ограничение в синем столбце, можно задавать начальные и конечные пункты путешествия. Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.
Примечание : для удобства настройки Поиска решения используются именованные диапазоны .
Выберите Линейный метод поиска решения, т.к. созданная модель является линейной.
Найденное Решение
Поиск решения гарантировано найдет самый короткий маршрут, т.к. модель линейная.
Изменив начальный и конечный пункт путешествия, и перезапустив Поиск решения , получим другой маршрут.
Будьте внимательны, не все пары конечных и начальных пунктов допустимы. Например, задав путешествие из Москвы в Копенгаген, Поиск решения не найдет маршрут, т.к. для этого потребуется «двигаться назад», а в маршрутах между городами обратные пути не прописаны (маршруты, конечно, можно добавить в столбцы J:M, но не забудьте изменить и другие формулы).
Граф — это математический объект, представляющий собой множество вершин графа, соединенных рёбрами . У ориентированного графа ребра имеют направление и изображаются стрелочками.
Для построения ориентированного графа на диаграмме MS EXCEL сделаем следующие шаги:
1. Построим на Точечной диаграмме вершины (или узлы) графа;
2. Присвоим каждой вершине индивидуальную подпись (в MS EXCEL это придется сделать с помощью макроса);
3. Зададим порядок соединения вершин ребрами. Например, ребро С будет соединять вершину 1 (начало) и вершину 2 (конец). Опишем соединения двумя способами: через непосредственное описание ребер и через маршруты;
4. Присвоим каждому ребру свою подпись на диаграмме.
Файл примера с ориентированным графом можно скачать внизу статьи.
Построение вершин
Создадим исходную таблицу для вершин. С каждой вершиной сопоставим произвольную точку с условными координатами (Х и Y). Координаты точек выберем лишь из соображений удобства отображения вершин на точечной диаграмме.
Выделите 2 столбца с координатами и создайте точечную диаграмму с маркерами (см. статью Основы построения диаграмм в MS EXCEL ), т.е. без соединительных линий. Путем настройки свойств маркеров их можно превратить в кружки без заливки.
Присваиваем вершинам подписи
В MS EXCEL 2013 индивидуальные подписи для точек можно присвоить стандартными способом. В MS EXCEL 2010 и более ранних - придется использовать макрос. Подробнее см. статью Подписи для точечной диаграммы в MS EXCEL . Для того чтобы иметь возможность переименовывать вершины, в файле примера создана кнопка Изменить подписи вершин .
Соединение вершин ребрами (отдельный ряд)
Создадим таблицу для построения ребер.
Для этого зададим названия для каждого ребра (пусть это будут буквы латинского алфавита), начальную и конечную вершину, которую соединяет ребро. С помощью простых формул =ВПР(G8;$A$8:$C$23;2;0) вычислим начальные и конечные координаты каждого ребра.
На точечной диаграмме для каждого ребра создадим отдельный ряд (см. Лист Граф1).
Чтобы не создавать вручную множество рядов, этот процесс можно автоматизировать через макрос. В файле примера создана кнопка Нарисовать ребра . Макрос работает, если нет ни одного ряда с ребрами.
Подписи ребер
Чтобы подписи располагались по центру ребра, потребуется создать еще 1 ряд. Ряд состоит из точек с координатами центра ребра. Координаты центра ребра вычисляются на основе координат начала и конца ребра (см. таблицу, столбец M и N). Подписи точкам присваиваются макросом аналогично тому, как мы делали для вершин. В итоге, как видно на диаграмме, название ребра будет выведено в его середине, в центре кружка.
Соединение вершин ребрами (пути)
Построение ребер было сделано выше через использование отдельного ряда для каждого ребра. Это трудоемко и потребовало написания макроса. Существует и другой путь. Можно определить пути обхода вершин, например 1; 4; 8; 14 (см. Лист Граф2). Это путь, который располагается в нижней части графа.
Задав путь, можно вычислить координаты ребер, которые соединены последовательно. Это существенно сократит количество рядов для построения ребер. Теперь каждый ряд будет представлять собой путь. При задании путей нужно избегать включения ребра в более чем 1 путь.
Путям для удобства присвоена произвольная последовательная нумерация. Четные и нечетные пути выделены цветом с помощью Условного форматирования .
Координаты начальных точек ребер вычисляются с помощью формулы = ВПР($F8;$A$8:$C$23;H$6;0)
ВНИМАНИЕ!
Построение ориентированного графа в этой статье приведено лишь с целью демонстрации такой возможности в MS EXCEL. Не ставилось целью сделать "удобную программу для пользователей" при построении графов. Это означает, что при изменении пользователем количества вершин / ребер графа в файле примера, переименовании листов и других изменений, макрос может потребовать дополнительной настройки.
Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата). Подобная задача решена в статье Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель) с помощью нелинейной модели.
Задача
Найдем кратчайший путь между 5 городами, координаты которых известны. Сначала рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.
Создание модели
Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).
Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$A16+1;1)-ИНДЕКС($C$7:$D$11;B$15+1;1))^2+(ИНДЕКС($C$7:$D$11;$A16+1;2)-ИНДЕКС($C$7:$D$11;B$15+1;2))^2)
Теперь создадим модель для Поиска решения .
Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .
Переменные (выделено зеленым) . В качестве переменных модели следует взять номера всех маршрутов соединяющих города. Маршрут из города 0 в город 1 эквивалентен маршруту из 1 в 0, так как направление обхода городов не имеет значения. Необходимо соединить все города (полный граф).
Ограничения (выделено синим) . Необходимо, чтобы из каждого города был 1 входящий и 1 исходящий маршрут.
Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.
Примечание : для удобства настройки Поиска решения используются именованные диапазоны .
Найденное Решение
Поиск решения гарантировано найдет самый короткий маршрут, т.к. построенная нами модель линейная.
Данную задачу можно решить для максимального количества городов =20, т.к. число маршрутов (ребер) вычисляется по формуле n*(n-1)/2, а количество переменных у Поиска решения ограничено 200.
Также в файле примера приведено решение задачи для прохождения 5 городов по незамкнутому маршруту, а также задачу для 9 городов.
Совет : Решение задачи о поиске кратчайшего пути между 2-мя заданными городами можно найти в статье Поиск решения MS EXCEL (6.4). Кратчайший путь (неполный граф, линейная модель) .
На прошлых занятиях мы познакомились с тем, что же такое граф, узнали, какой граф называется ориентированным и порешали задачи на уже готовом графе. Сегодня же мы познакомимся с новым типом графов, а именно с нагруженным графом.
Нагруженный граф – это такой граф, у которого каждому ребру сопоставлено определенное число.
Чаще всего, в задачах ОГЭ и ЕГЭ это число обозначает расстояние от одной вершины до другой, или время, за которое можно пройти от одной вершины до другой.
Пример нагруженного графа:
Кратчайшее расстояние (время) от стартового до конечного пункта?
В задачах мы постоянно будем сталкиваться с вопросом определения кратчайшего расстояния от одного пункта до другого. Давайте разберемся, что же это значит.
Кратчайшим называется минимальное из множества всех возможных расстояние (время), за которое можно добраться от одного пункта до другого.
Единственная проблема заключается в том, что на практике нам редко будет дан уже готовый нагруженный граф. Чаще всего нам будет необходимо его построить с помощью данных, указанных в таблице.
Рассмотрим конкретный пример:
Между населенными пунктами А, Б, В, Г, Е, Ж, З построены дороги, протяженность которых указана в таблице (Если числа в ячейке нет, это значит, что прямая дорога между этими населенными пунктами отсутствует). Передвигаться можно только по построенным дорогам. Определите длину кратчайшего расстояния между пунктами А и З.
Давайте сначала разберёмся как читать эту таблицу. На самом деле она симметрична относительно линии из крестиков (это отражает то, что длина из условного пункта А в условный пункт Б равна длине из пункта Б в пункт А, и что граф не является ориентированным, т.е. двигаться можно в обе стороны). А дальше читаем по строчкам. Берем строчку А и видим, что числа стоят на пересечении со столбцами Б (28), В (20) и Г (28). Это значит то, что из А ведут дороги в Б, В, Г и им соответствует данные длины, и так далее.
Дальше строим граф.
При построении графа нужно учесть некоторые вещи:
Рёбра графа не должны пересекаться ни в коем случае! (Они могут пересекаться, но вы запутаетесь при решении гарантированно)
Точки, в которые приходит больше всего дорог, должны стоять примерно в центре графа (это скорее рекомендация)
Попробуем построить граф по этой таблице и получаем такую картину:
Дальше просто анализируем наш граф и избавляемся от дорог, которые заведомо нам не выгодны, т.е. слишком длинные. В конечном итоге мы должны зачеркнуть практически все дороги, чтобы у нас остался один единственный верный путь.
Тут мы можем избавиться от дороги АБ (можно пройти АВБ), от дорог ВБ и БЕ (можно пройти ВЕ), от дороги ВЖ (можно пройти ВЕЖ). И у нас остается два пути, через верх и через низ.
Подсчитываем оба варианта и видим, что через верх длина будет 42, а через низ 43. Делаем вывод, что через верх идти выгодней
Читайте также: