Задача о кратчайшем пути в нагруженном графе и ее решение на основе алгоритма Дейкстры

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

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

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

1^. .

2^. .

3^. , где – смежная с вершина.

При выполнении этих условий длина кратчайшей цепи между вершинами и равна , а сама кратчайшая цепь проходит по таким вершинам

,

для которых , .

Рассмотрим алгоритм Э. Дейкстры, который позволяет определить расстояние от одной из вершин графа до всех остальных.

Каждой вершине графа поставим в соответствие метку – минимальное известное расстояние от вершины до начальной вершины . Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершены посещены.

Инициализация (начальная расстановка отметок). Полагаем .

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

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

Объявляем отметку вершины окончательной и повторяем шаг алгоритма для следующей вершины. Число шагов равно числу вершин графа.

11. 1   2   3   4

---

Эйлеровы циклы и цепи. Теорема существования эйлерова цикла. Эйлеровы и полуэйлеровы графы.

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

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

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

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

11. 
    Цикловые ребра и мосты. Цикломатическое число графа. Теорема о неотрицательности цикломатического числа.
    

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

---

Рассмотрим -граф , имеющий компонентов связности. Величина

называется коцикломатическим числом графа. Оно равно общему числу ребер в остовах каждой из связных компонент графа . Цикломатическим числом (дефектом или первым числом Бетти) называется величина .

Теорема.

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

1. Удаляемое ребро цикловое. Тогда , , ; .

2. Удаляемое ребро – перешеек. В этом случае , , ; .

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

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

11. 
    Определение гамильтонова цикла и цепи. Задачи, приводящие к гамильтоновым циклам: задача Киркмана, задача о шахматном коне, задача о коммивояжере.
    

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

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

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

,

,

,

,

.

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

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

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

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

---

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

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

11. 
    Определение леса. Деревья и их свойства. Остовное дерево графа. Хорды.
    

Граф без циклов называется ациклическим или лесом. Связный ациклический граф называется деревом. Если – лес, то каждая его компонента является деревом. Листом называют вершину, степень которой равна 1, если она не рассматривается как корень. В качестве корня в неориентированном дереве можно принять любую вершину.

Существует несколько эквивалентных определений неориентированного дерева, каждое из которых отражает различные свойства последнего. Приведем некоторые из них.

Теорема. Следующие определения дерева эквивалентны:

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

Ребра графа , не вошедшие в его остовное дерево , называются хордами дерева .

Лемма. В графе для любого остовного дерева и любой хорды этого дерева существует единственный цикл, содержащий хорду и не содержащий других хорд.

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

24. Алгоритм Краскала нахождения минимального остовного дерева.

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

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

---

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

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

25. 
    Пространство остовных подграфов.
    

Зафиксируем некоторое множество и рассмотрим множество всех графов с множеством вершин . Буквой будем обозначать пустой граф из этого множества: .

Для графов и из определим их сумму по модулю 2 как граф , где обозначает симметрическую разность множеств и . Иначе говоря, ребро принадлежит графу тогда и только тогда, когда оно принадлежит одному из графов и . Пример показан на рис. 1.

Введенная операция обладает следующими свойствами:

1. Коммутативность: .

2. Ассоциативность: .

3. .

4. .

Отсюда следует, что множество относительно операции образует абелеву группу. Нейтральным элементом («нулем») этой группы служит граф , а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным и заданными графами и имеет единственное решение . Благодаря свойству ассоциативности в выражении вида можно не использовать скобки для указания порядка действий. Очевидно, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству графов .

Рассмотрим множество из двух элементов {0, 1}. Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы:

.

Множество с введенными операциями сложения графов и умножения на элементы поля является линейным векторным пространством.

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

Остовному подграфу можно поставить в соответствие двоичное слово , в котором нули указывают, какие ребра удалены, а единицы – какие оставлены:

25. 
    Квазициклы. Пространство циклов графа, его размерность и базис. Построение фундаментальных циклов графа. Матрица фундаментальных циклов.
    

---

Смотрите также файлы

• Правила проектирования и оформления проектов стандартизованы в Единой системе конструкторской документации (ескд), которая устанавливает пять стадий разработки конструкторской документации.pptx

• Министерство образования и науки государственное образовательное учреждение высшего профессионального образования.docx

• Закон противоречия и споры вокруг него.docx

• Основная образовательная программа начального (основного) общего образования. 1)срок получения ооо 5 лет (не установлено сокращение).docx

• Темам 4 Тема Практическое занятие Требования к соблюдению основных принципов работы психолога Ситуация 4.docx