1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества
 Скачать 4.95 Mb.
|
|
19. Диаметр, радиус и центр графа. Матрицы достижимостей и контрадостижимостей. Для связного графа определим расстояние между двумя его вершинами и как длину самой короткой цепи, соединяющей эти вершины, и обозначим через . Длина цепи – это количество ребер, составляющих цепь. Нетрудно проверить, что введенное расстояние удовлетворяет аксиомам метрики: Определим расстояние от каждой вершины графа до самой далекой от нее вершины , которое называется эксцентриситетом. Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – . Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа . В полном графе имеем , а в простом цикле – . Вершина называется центральной, если . Граф может иметь несколько таких вершин, а в некоторых графах все вершины являются центральными. В простой цепи при нечетном числе вершин только одна является центральной, а при четном их числе таких вершин две. В полном графе и для простого цикла центральными являются все вершины. Множество центральных вершин называется центром графа. Матрицы достижимостей и контрадостижимостей Матрица достижимостей определяется следующим образом: Матрица контрадостижимостей (обратных достижимостей) определяется следующим образом: , где – матрица, транспонированная к матрице . 20. Постановка задачи о кратчайшем пути в графе. Задача о кратчайшем пути в ненагруженном графе и волновой алгоритм ее решения. Задача о кратчайшем пути в нагруженном графе и ее решение на основе алгоритма Дейкстры. Постановка задачи о кратчайшем пути Вариант 1. Дана сеть автомобильных дорог, например, Тульской области. Найти кратчайшие пути от Тулы до каждого города области (если двигаться можно только по дорогам). Задача о кратчайшем пути в ненагруженном графе и волновой алгоритм ее решения Рассмотрим связный ненагруженный граф , ребра которого имеют одинаковый вес (длину), принимаемый за единицу. Решим для этого графа следующую задачу: найти кратчайшую цепь, связывающую заданную начальную вершину с заданной конечной вершиной . Общее правило для нахождения кратчайшего пути в графе состоит в том, чтобы каждой вершине присвоить индекс , равный длине кратчайшего пути из данной вершины в начальную. Присваивание индексов производится в следующем порядке: начальной вершине присваивается индекс ; всем вершинам, смежным с вершиной , присваиваем индекс 1; всем вершинам, смежными с вершинами, имеющими индекс 1, присваиваем индекс 2, и так далее, пока не будет помечена вершина . Сам кратчайший путь найдем, если будем двигаться из конечной вершины в направлении убывания индексов. Задача о кратчайшем пути в нагруженном графе и ее решение на основе алгоритма Дейкстры Поставим в соответствие каждому ребру связного графа целое число и будем называть его весом (длиной, стоимостью) ребра . В результате получим граф с нагруженными ребрами или просто нагруженный граф, который обозначается , где – матрица весов. Для любой цепи ее вес равен сумме весов составляющих ее ребер: . Решим следующую задачу: в связном графе найти кратчайшую цепь, связывающую две заданные вершины и . Алгоритм решения этой задачи, как и предыдущий, состоит в вычислении по определенным правилам индексов вершин. Индекс вершины обозначим . После окончания процесса вычисления индексов они должны удовлетворять условиям оптимальности, которые заключаются в следующем: 1. . 2. . 3. , где – смежная с вершина. При выполнении этих условий длина кратчайшей цепи между вершинами и равна , а сама кратчайшая цепь проходит по таким вершинам , для которых , . Рассмотрим далее алгоритм Дейкстры, который обеспечивает присвоение вершинам графа отметок, удовлетворяющих условиям 1–3. Алгоритм состоит из двух этапов: инициализация алгоритма, которая заключается в начальной расстановке отметок; циклически повторяющаяся процедура исправления отметок. На каждом шаге алгоритма все отметки делятся на предварительные и окончательные. Алгоритм обрабатывает только предварительные отметки и заканчивает работу, когда все отметки станут окончательными. Рассмотрим алгоритм Э. Дейкстры, который позволяет определить расстояние от одной из вершин графа до всех остальных. Каждой вершине графа поставим в соответствие метку – минимальное известное расстояние от вершины до начальной вершины . Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершены посещены. Инициализация (начальная расстановка отметок). Полагаем . Символ отражает тот факт, что расстояния от до других вершин пока неизвестны. Все отметки объявляем предварительными. Шаг алгоритма (исправление отметок). Из еще не просмотренных вершин выбираем вершину , имеющую минимальную метку . Для каждой вершины , смежной с и имеющей предварительную отметку , исправляем отметку по правилу . Объявляем отметку вершины окончательной и повторяем шаг алгоритма для следующей вершины. Число шагов равно числу вершин графа. Для графа, изображенного на рис. 2, показаны окончательные отметки и кратчайшая цепь. 21. Эйлеровы циклы и цепи. Теорема существования эйлерова цикла. Эйлеровы и полуэйлеровы графы. Эйлеровым циклом (цепью) в мультиграфе называется цикл (цепь), содержащий все ребра мультиграфа по одному разу. Граф, имеющий эйлеров цикл, также будем называть эйлеровым . Граф, содержащий эйлерову цепь, называется полуэйлеровым. Эйлеров граф можно нарисовать на бумаге, не отрывая от нее карандаша. Замкнутые линии, которые можно получить, не отрывая карандаша от бумаги, проходя при этом каждый участок один раз, называются уникурсальными. Теорема.Мультиграф обладает эйлеровым циклом тогда и только тогда, когда он связный и все его локальные степени четны. Следствия. 1. Связный мультиграф, имеющий ровно две вершины с нечетной степенью, является полуэйлеровым графом. Действительно, добавим к мультиграфу ребро, соединяющее вершины с нечетной степенью. В результате степени всех вершин станут четными. Построим в новом графе эйлеров цикл, а затем удалим добавленное ребро: цикл разорвется и станет цепью. Эта цепь будет начинаться и заканчиваться в вершинах нечетной степени. 2. В общем случае число вершин мультиграфа, имеющих нечетную степень, всегда четно. Если мультиграф имеет таких вершин, то все его ребра можно включить в цепей. Другими словами, мультиграф можно нарисовать, раз отрывая карандаш от бумаги. 22. Цикловые ребра и мосты. Цикломатическое число графа. Теорема о неотрицательности цикломатического числа. Ребро графа , через которое проходит хотя бы один цикл, называется цикловым. Ребро, которое не входит ни в один цикл, называется перешейком или мостом. Например, в графе, изображенном на рис. 2, ребра и – перешейки, а остальные ребра цикловые. Рис. 2. Пример разбиения ребер графа на цикловые и перешейки Справедливо следующее очевидное утверждение: при удалении из связного графа циклового ребра он остается связным; при удалении из связного графа перешейка граф распадается на две компоненты. Из этого утверждения следует, что при удалении из связного графа циклового ребра число связных компонент не изменяется. При удалении перешейка число связных компонент увеличивается на единицу. Рассмотрим -граф , имеющий компонентов связности. Величина называется коцикломатическим числом графа. Оно равно общему числу ребер в остовах каждой из связных компонент графа . Цикломатическим числом (дефектом или первым числом Бетти) называется величина . Теорема. Доказательство. Будем удалять из графа по одному ребру и следить за изменением величины . Параметры исходного графа обозначим , а после удаления ребра – . В процессе удаления ребер возможны две ситуации: 1. Удаляемое ребро цикловое. Тогда , , ; . 2. Удаляемое ребро – перешеек. В этом случае , , ; . Итак, при удалении ребра величина либо не изменяется, либо уменьшается на единицу. После удаления всех ребер получим пустой граф, для которого , , , то есть . Следовательно, в исходном графе . Из теоремы следует, что при в графе имеется, по крайней мере, один цикл. 23. Определение гамильтонова цикла и цепи. Задачи, приводящие к гамильтоновым циклам: задача Киркмана, задача о шахматном коне, задача о коммивояжере. Простой цикл в графе , проходящий через каждую вершину графа один и только один раз, называется гамильтоновым. Подобная задача сформулирована и решена Киркманом. Одиннадцать министров ежедневно садятся за круглый стол. Как их рассаживать, если желательно, чтобы каждый из них имел на каждом заседании новых соседей? Сколько дней это может продолжаться? Эта задача сводится к отысканию наибольшего числа гамильтоновых циклов без общих ребер в полном графе с одиннадцатью вершинами . В данном случае существует только пять циклов без общих ребер: , , , , . Эти циклы получаются вращением линии, проведенной на рис. 3 в направлении стрелок. В более общем случае вершин можно найти гамильтоновых циклов без общих ребер. a e g c i b k d j f h Рис. 3. Гамильтоновы циклы в задаче Киркмана В применениях графов к играм вершины соответствуют различным позициям. Таким образом, существование гамильтонова цикла равносильно существованию циклической последовательности ходов, содержащей каждую позицию по одному разу. Примером является известная задача о шахматном коне: можно ли, начиная из произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти через каждое из 64 полей и вернуться в исходное? Эта задача имеет несколько вариантов решений. Гамильтоновой цепью в графе называется простая цепь, проходящая через все вершины по одному разу. Если в графе не существует гамильтоновых циклов, то можно искать сумму непересекающихся простых циклов, проходящих через все вершины. В орграфах можно искать орциклы, проходящие через каждую вершину по одному разу. К гамильтоновым циклам относится так называемая задача о коммивояжере. Район, который должен посетить коммивояжер, содержит какое-то количество городов. Расстояния между ними известны, и нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный. Эта задача имеет ряд приложений в исследовании операций, например в вопросах о наиболее эффективном использовании подвижного состава или оборудования. В задаче о коммивояжере города можно представить как вершины графа , в котором каждой паре вершин приписывается расстояние . Если вершины не инцидентны, то полагают . Тогда задача состоит в том, чтобы найти такой гамильтонов цикл , для которого сумма минимальна. 24. Определение леса. Деревья и их свойства. Остовное дерево графа. Хорды. Граф без циклов называется ациклическим или лесом. Связный ациклический граф называется деревом. Если – лес, то каждая его компонента является деревом. Листом называют вершину, степень которой равна 1, если она не рассматривается как корень. В качестве корня в неориентированном дереве можно принять любую вершину. Теорема. Следующие определения дерева эквивалентны: дерево – это связный граф без циклов; дерево – это связный граф, в котором каждое ребро является мостом; дерево – это связный граф, цикломатическое число которого равно нулю; дерево – это граф, в котором для любых двух вершин существует ровно одна соединяющая их цепь. Эти утверждения выводятся одно из другого по схеме 1) 2) 3) 4) 5). Из свойства 3) имеем: или , то есть в любом дереве число ребер на единицу меньше числа вершин. Рассмотрим связный граф и будем из него удалять по одному цикловые ребра до получения ациклического подграфа. В результате получим остовное дерево графа , для которого , . Так как удаление цикловых ребер можно вести разными способами, то один и тот же граф в общем случае имеет несколько остовных деревьев. На рис. 1. представлен граф и три его остовных дерева. Ребра графа , не вошедшие в его остовное дерево , называются хордами дерева Лемма. В графе для любого остовного дерева и любой хорды этого дерева существует единственный цикл, содержащий хорду и не содержащий других хорд. Доказательство. Пусть . В дереве имеется единственная цепь, соединяющая вершины и . Присоединяя к этой цепи ребро , получим требуемый цикл. 25. Задача поиска кратчайшего остова в нагруженном графе. Задача поиска кратчайшего остова состоит в следующем: для нагруженного графа требуется построить остовное дерево , сумма длин ребер которого минимальна. Для каждой пары пунктов и задана стоимость их соединения , которая представляет длину ребра . Требуется построить связывающую сеть минимальной стоимости, которую называют кратчайшей связывающей сетью. Пример. Дана матрица расстояний , в которой элемент – вес ребра, который указывает в условных единицах затраты, необходимые для того, чтобы связать пункт с пунктом . Требуется с наименьшими затратами связать все пункты друг с другом. В результате получим следующий кратчайший остов: 5 4 8 1 7 3 9 2 6 Рис. 3 26. Пространство остовных подграфов. Зафиксируем некоторое множество и рассмотрим множество всех графов с множеством вершин . Буквой будем обозначать пустой граф из этого множества: . Для графов и из определим их сумму по модулю 2 как граф , где обозначает симметрическую разность множеств и . Иначе говоря, ребро принадлежит графу тогда и только тогда, когда оно принадлежит одному из графов и . Пример показан на рис. 1. 1 1 1 2 2 2 3 3 4 4 4 3 = 5 6 5 6 5 6 Рис. 1. Введенная операция обладает следующими свойствами: 1. Коммутативность: . 2. Ассоциативность: . 3. . 4. . Отсюда следует, что множество относительно операции образует абелеву группу. Нейтральным элементом («нулем») этой группы служит граф , а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным и заданными графами и имеет единственное решение . Благодаря свойству ассоциативности в выражении вида можно не использовать скобки для указания порядка действий. Очевидно, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству графов . Рассмотрим множество из двух элементов {0, 1}. Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы: . Множество с введенными операциями сложения графов и умножения на элементы поля является линейным векторным пространством. Зафиксируем некоторый граф и рассмотрим множество всех его остовных подграфов, которое будем обозначать . Это множество состоит из элементов, среди них сам граф и граф . Оно замкнуто относительно сложения графов и умножения на элементы поля, следовательно, является подпространством пространства . Его называют пространством остовных подграфов графа . Остовному подграфу можно поставить в соответствие двоичное слово , в котором нули указывают, какие ребра удалены, а единицы – какие оставлены: 27. Квазициклы. Пространство циклов графа, его размерность и базис. Построение базисных циклов графа. Циклом будем называть граф, у которого одна компонента связности является простым циклом, а остальные – изолированными вершинами. Определение. Остовный подграф, у которого степени всех вершин четны, называется квазициклом. Отметим, что всякий цикл является квазициклом, в том числе и пустой граф. Покажем, что множество квазициклов замкнуто относительно операции сложения. Лемма. Сумма двух квазициклов есть квазицикл. Из леммы следует, что множество квазициклов является линейным векторным пространством над полем {0, 1}, которое называется пространством циклов графа . Обозначим это пространство через . Очевидно, что является подпространством векторного пространства остовных подграфов. Построить базис пространства , состоящий из простых циклов, можно следующим образом. Выберем в графе какой-нибудь остов (каркас) . Пусть – все хорды графа . Если добавить к хорду , то в графе образуется единственный цикл . Таким образом, получим семейство из циклов, которые называются фундаментальными (базисными) циклами относительно остова . Теорема. Множество всех фундаментальных циклов относительно любого остова графа образует базис пространства циклов этого графа. Покажем теперь, что любой квазицикл графа является суммой фундаментальных циклов. Пусть – все ребра , не принадлежащие (хорды графа ). Рассмотрим квазицикл . Каждое из ребер ( ) входит ровно в два слагаемых этой суммы – в и в . Следовательно, при сложении эти ребра уничтожатся. Все остальные ребра, присутствующих в графах-слагаемых, принадлежат . Значит, – подграф графа . Поскольку в нет циклов, то . Отсюда . Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его остов, то есть числу хорд. Так как остов содержит ребер, то эта размерность равна . Таким образом, размерность пространства циклов графа равна его цикломатическому числу. 12-9+1=4 Пример. Построим систему базисных циклов для графа на рис. 2. Рис. 2. Граф и его остовные деревья , и Выделим остовное дерево . Присоединяя к дереву по очереди хорды , , и , получим 4 базисных цикла (рис. 3). Рис. 3. Базисные циклы графа Для дерева получим другую систему базисных циклов (рис. 4). Циклы одной из систем можно выразить как линейные комбинации циклов из другой системы. В данном случае имеем: Обратное преобразование имеет вид: Пусть – остов неориентированного графа , а – система фундаментальных циклов графа относительно остова . Матрицей фундаментальных циклов графа называется матрица размера , в которой Определение. Если вершины неориентированного графа разбиты на два подмножества и ( , ), то множество ребер графа , одни концевые вершины которых лежат в , а другие – в , называется разрезом графа , порождаемым множеством вершин , и обозначается . Таким образом, остовный подграф , полученный из удалением ребер, принадлежащих разрезу, является несвязным графом, состоящим из двух компонент. Матрица фундаментальных разрезов графа называется матрица размера , в которой Пример. Построить матрицы фундаментальных циклов и разрезов для графа Рис. 5 Найдем цикломатическое число графа: . На рис. 5 показан один из остовов графа, ребра которого выделены жирными линиями. Тогда матрица фундаментальных циклов равна
Матрица фундаментальных разрезов имеет вид
Существует несколько соотношений между матрицами циклов, разрезов и инциденций. Далее будем рассматривать неориентированные графы без петель. Теорема 2. Матрица инциденций и транспонированная матрица фундаментальных циклов ортогональны, т. е. . Теорема 3. Матрица фундаментальных циклов и транспонированная матрица фундаментальных разрезов ортогональны, т. е. . Из теоремы 3 следует |