Файл: 1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 82
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Ребро графа , через которое проходит хотя бы один цикл, называется цикловым. Ребро, которое не входит ни в один цикл, называется перешейком или мостом. Например, в графе, изображенном на рис. 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 показан один из остовов графа, ребра которого выделены жирными линиями. Тогда матрица фундаментальных циклов равна