ShPORA_po_VychMetodKompMod

17. Способы задания графа. Матрицы смежностей и инциденций. Обходы графов

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

прямой, соединяющий точки vi , v j . В результате таких действий возникнет некоторый рисунок,

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

Число вершин графа называют порядком графа и обозначают V = n. Граф будем обозначать парой G = (V, E). Граф G называется помеченным, если его вершинам приписаны числа 1, 2, …, n, где n − порядок графа.

Граф можно задать с помощью матрицы размера n x n: А(G)=[aij], где 1 i, j n

Введенная так матрица B(G) называется матрицей инциденций данного графа. Очевидно, вид матрицы смежностей и вид матрицы инциденций существенно зависят от того, как именно занумерованы вершины и ребра. Если в приведенном выше примере графа считать, что

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

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

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

Прежде всего, уточним термины "маршрут", "цепь", "цикл" и "путь". Эти четыре понятия находятся в следующем соотношении: пути и циклы – это особые виды цепей, цепь – особый вид маршрута.

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

Цепь – это маршрут без повторяющихся ребер.

Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.

Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны. Пример.

Можно составить следующие маршруты из А в С в графе G:

М1: А – е1 – В – е3 – С (путь); М2: А – е2 – Е – е6 – Д – е7 – Д – е6 – Е – е5 – С (не цепь);

М3: А – е1 – B – е3 – C – е5 – Е – е4 – С (цепь, но не путь).

Циклы:

А – е1 – В – е3 – С – е4 – Е – е2 – А; Е – е4 – С – е5 – Е; Д – е7 – Д.

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

петлю , вторая компонента – вершины А,В,С,Е, связанные между собой всеми оставшимися ребрами.

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

Вершины 5,6,3,7,8,9 называют листьями дерева. Несвязный неорграф, компонентами которого являются деревья, называют

лесом.

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

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

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

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

18. Графы типа дерево. Остовное дерево. Минимальное остовное дерево

Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

Граф G1 является деревом

(рис.38). Граф G2 является лесом (рис. 38), он содержит три связные компоненты, каждая из которых является деревом.

Следующие утверждения эквивалентны: граф G есть дерево; граф G является связным и не имеет простых циклов; граф G является связным и число его ребер ровно на единицу меньше числа вершин; любые две различные вершины графа G можно соединить единственной (и притом простой) цепью; граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один (с точностью до направления обхода и начальной вершины обхода) и притом простой цикл (проходящий через добавляемое ребро).

Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина. Пусть G – дерево. Тогда любая цепь в G будет простой.

Опр. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G

ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.

Опр. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ - Задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами. Длиной пути такого графа называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути возникает чаще всего при решении транспортных задач, дискретных задач динамического программирования и др. Остовное дерево связного неориентированного графа — ациклический связный подграф данного графа, в который входят все его вершины. Иначе говоря, остовное дерево состоит из некоторого подмножества рѐбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рѐбрами, и в нѐм нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

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

Остовное дерево также иногда называют покрывающим деревом, остовом или скелетом графа.

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

(  Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.)

Задача о нахождении минимального остовного дерева встречается в постановке: допустим, есть n городов, которые надо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой дороги. Требуется решить, какие дороги нужно строить, чтобы минимизировать общую стоимость строительства.

19. Задачи оптимизации на графах.

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

Описание

Алгоритм Краскала изначально помещает каждую вершину в своѐ дерево, а затем постепенно объединяет эти деревья, объединяя на каждой итерации два некоторых дерева некоторым ребром. Перед началом выполнения алгоритма, все рѐбра сортируются по весу (в порядке неубывания). Затем начинается процесс объединения: перебираются все рѐбра от первого до последнего (в порядке сортировки), и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. По окончании перебора всех рѐбер все вершины окажутся принадлежащими одному поддереву, и ответ найден.

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них: алгоритм Прима; алгоритм Краскала (или алгоритм Крускала); алгоритм Борувки.

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

(  Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.)

Задача о нахождении минимального остовного дерева встречается в постановке: допустим, есть n городов,

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

20. Сетевое планирование: основная идея и модели решаемых задач

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

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

Метод сетевого планирования и управления является методом решения задач исследования операций, в которых необходимо оптимально распределить сложные комплексы работ. Методы СПУ используются при планировании сложных комплексных проектов, например, таких как:

−строительство и реконструкция каких-либо объектов;

−выполнение научно-исследовательских и конструкторских работ;

−подготовка производства к выпуску продукции;

−перевооружение армии;

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

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

СПУ состоит из трех основных этапов: 1)Структурное планирование. 2) Календарное планирование. 3) Оперативное управление.

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

В ходе оперативного управления используются сетевой и календарных графики для составления периодических отчетов о ходе выполнения проекта.

Сущность метода сетевого планирования и управления (СПУ) заключается в особом моделировании исследуемого процесса, а именно – создаѐтся

информационно-динамическая модель задачи.

Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.

21. Моделирование систем массового обслуживания

Большой класс систем, которые сложно изучить аналитическими способами, но которые хорошо изучаются методами статистического моделирования, сводится к системам массового обслуживания (СМО). В СМО подразумевается, что есть типовые пути (каналы обслуживания), через которые в процессе обработки проходят заявки. Принято говорить, что заявки обслуживаются каналами. Каналы могут быть разными по назначению, характеристикам, они могут сочетаться в разных комбинациях; заявки могут находиться в очередях и ожидать обслуживания. Часть заявок может быть обслужена каналами, а части могут отказать в этом.

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

Примерами СМО: автобусный маршрут и перевозка пассажиров; производственный конвейер по обработке деталей; влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО; ствол и рожок автомата, которые «обслуживают» патроны; электрические заряды, перемещающиеся в некотором устройстве и т. д.

Примеры систем массового обслуживания

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

Все модели СМО собираются типовым образом из небольшого набора элементов (канал, источник заявок, очередь, заявка, дисциплина обслуживания, стек, кольцо и так далее), что позволяет имитировать эти задачи типовым образом. Для этого модель системы собирают из конструктора таких элементов. Неважно, какая конкретно система изучается, важно, что схема системы собирается из одних и тех же элементов. Разумеется, структура схемы будет всегда различной.

Судить о результатах работы СМО можно по показателям. Наиболее популярные из них:

вероятность обслуживания клиента системой;

пропускная способность системы;

вероятность отказа клиенту в обслуживании;

вероятность занятости каждого из канала и всех вместе;

среднее время занятости каждого канала;

вероятность занятости всех каналов;

среднее количество занятых каналов;

вероятность простоя каждого канала;

вероятность простоя всей системы;

среднее количество заявок, стоящих в очереди;

среднее время ожидания заявки в очереди;

среднее время обслуживания заявки;

среднее время нахождения заявки в системе.

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