close

Вход

Забыли?

вход по аккаунту

?

Теория графов

код для вставки
На практике часто бывает полезно изобразить некоторую ситуацию в виде
рисунков, составленных из точек (вершин), представляющих основные ситуации, и
линий (ребер), соединяющих определенные пары этих вершин и представляющих связи
между ними. Таким способом удобно представлять структуру системы, в которой
вершины – это блоки, а ребра – связи между блоками. Такие рисунки известны под
общим названием графов. Графы встречаются в разных областях: структуры в
строительстве, сети в электротехнике, социограммы в социологии и экономике,
молекулярные структуры в химии и т.д. Удобны графы и при исследовании систем
методом пространства состояний. В этом случае вершины – состояния системы,
процесса, ребра – действия, которые могут изменить состояние. При решении
оптимизационных задач вершинами могут быть предполагаемые решения, ребрами –
правила для их нахождения.
Простым графом G называется пара множеств (V,E), где V – не пустое, конечное
множество элементов, называемых вершинами. Графически это множество изображается
точками; E – конечное множество неупорядоченных пар различных элементов из V,
называемых ребрами. Графически это множество изображается линией, соединяющей
пару точек.
Простой граф – конечный граф без петель и кратных ребер.
Ориентированным графом (орграфом) G называется пара (V,E), где V – не
пустое, конечное множество элементов (вершин); E – конечное семейство
упорядоченных пар элементов из V, называемых дугами.
Замечание. В семействе допускаются одинаковые элементы.
Основные понятия:
соединенные ребром, называются смежными.
ребру.
зывается изолированной, степени 1 – висячей.
числу ребер.
Маршрутом
в
графе
называется
последовательность
ребер,начинающаяся и заканчивающаяся вершиной.
Длиной маршрута называется количество ребер в нем.
вершин
и
Маршрут может быть замкнутым и незамкнутым. В замкнутом маршруте
первая и последняя вершины совпадают.
Маршрут в котором все ребра различны, называется цепью.
Цепь, в которой нет одинаковых вершин, кроме, быть может, ее концов, называется
простой цепью.
Циклом называется простая замкнутая цепь.
Цикл длины 1 называется петлей.
Расстояния в графе
Расстоянием
(r)
между
цепи,соединяющей эти вершины.
вершинами
называют
длину
кратчайшей
Диаметром (d) называется максимальное расстояние между вершинами в графе.
Центром графа называется вершина, максимальное расстояние от которой до
другой вершины графа является минимальным при другом выборе центра.
Радиус – максимальное расстояние от центра.
Связный граф — граф, содержащий ровно одну компоненту связности. Это
означает, что между любой парой вершин этого графа существует как минимум один
путь.
В ориентированных графах различают несколько понятий связности:
Ориентированный граф называется сильно-связным, если в нём существует
(ориентированный) путь из любой вершины в любую другую, или, что эквивалентно,
граф содержит ровно одну сильно связную компоненту.
Ориентированный граф называется слабо-связным, если является связным
неориентированный граф, полученный из него заменой ориентированных рёбер
неориентированными.
Некоторые критерии связности:
Здесь приведены некоторые критериальные (эквивалентные) определения связного
графа:
Граф называется односвязным (связным), если:
У него одна компонента связности
Существует путь из любой вершины в любую другую вершину
Существует путь из заданной вершины в любую другую вершину
Содержит связный подграф, включающий все вершины исходного графа
Содержит в качестве подграфа дерево, включающее все вершины исходного графа
(такое дерево называется остовным)
При произвольном делении его вершин на 2 группы всегда существует хотя бы 1
ребро, соединяющее пару вершин из разных групп
Способы задания графов
1. Перечисление вершин и ребер.
2. Графическое изображение.
3. С помощью матриц смежности вершин.
4. С помощью матриц инциденции.
Свойства матрицы инцидентности простого графа
-строке равно степени i-вершины
-столбце равно двум
ниц равно удвоенному числу ребер
Основные типы графов
пустым, нуль-графом или вполне несвязным.
графом.
называется
регулярным графом степени r. Регулярный граф степени 3 называется кубическим.
можно разделить на два не пустых и не
пересекающихся подмножества таким образом, чтобы каждое ребро соединяло вершины
из разных подмножеств, то такой граф называется двудольным.
одного подмножества соединена с каждой
вершиной другого подмножества, то такой граф называется полным двудольным.
мощность одного из подмножеств равна 1, то
такой граф называется звездой
– связный граф без циклов.
– граф без циклов.
Операции над графами
- Удаление / добавление ребра e.
- Удаление / добавление вершины
- Отождествление (слияние) вершин
- Объединение, Пересечение, Соединение, Произведение, Дополнение графа
В теории графов паросочетание или независимое множество рёбер в графе — это
набор попарно несмежных рёбер.
Пусть дан граф G = (V,E), паросочетание M в G — это множество попарно
несмежных рёбер, то есть рёбер, не имеющих общих вершин.
Максимальное паросочетание — это такое паросочетание M в графе G, которое
не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно
добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания.
Другими словами, паросочетание M графа G является максимальным, если любое ребро
в G имеет непустое пересечение, по крайней мере, с одним ребром из M. Ниже
приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах[1].
Наибольшее паросочетание (или максимальное по размеру паросочетание[2])—
это такое паросочетание, которое содержит максимальное количество рёбер. У графа
может быть множество наибольших паросочетаний. При этом любое наибольшее
паросочетание является максимальным, но не любое максимальное будет наибольшим.
Следующие три рисунка показывают наибольшие паросочетания в тех же трёх графах[1].
Некоторые авторы используют термин «максимальное паросочетание» для
наибольшего паросочетания
Совершенным паросочетанием (или 1-фактором) называется паросочетание, в
котором участвуют все вершины графа. То есть любая вершина графа инцидентна ровно
одному ребру, входящему в паросочетание. Фигура (b) на рисунке выше является
примером такого паросочетания. Любое совершенное паросочетание является
наибольшим и максимальным.
Наибольшие паросочетания[править | править код]
Основная статья: Алгоритм для паросочетаний Эдмондса
Имеется алгоритм полиномиального времени для нахождения наибольшего паросочетания или
паросочетания максимального веса в графе, не являющемся двудольным. Следуя Джеку Эдмондсу[en] его
называют методом путей, деревьев и цветов или просто алгоритмом Эдмондса для паросочетаний[en].
Алгоритм использует двунаправленные дуги[en]. Обобщение той же техники может быть использовано для
поиска максимального независимого множества в графах без клешней. Алгоритм Эдмодса был
впоследствии улучшен до времени работы
, что соответствует алгоритмам для двудольных графов[14].
Другой (рандомизированный) алгоритм, разработанный Муча и Санковсим (Mucha, Sankowski)[10],
основанный на быстром произведении матриц, даёт сложность
.
Максимальные паросочетания[править | править код]
Максимальное паросочетание можно найти простым жадным алгоритмом. Наибольшее паросочетание
является также максимальным, и, поэтому, имеется возможность найти самое большое максимальное
паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени
алгоритма для нахождения наименьшего максимального паросочетания, то есть максимального
паросочетания, содержащего наименьшее возможное число рёбер.
Заметим, что наибольшее паросочетание из k рёбер является рёберным доминирующим
множеством с k рёбрами. И обратно, если задано минимальное рёберное доминирующее множество
с k рёбрами, мы можем построить наибольшее паросочетание с k рёбрами за полиномиальное время.
Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна
задаче нахождения минимального рёберного доминирующего множества[15]. Обе эти задачи оптимизации
известны как NP-трудные, а их распознавательные версии являются классическими примерами NP-полных
задач[16]. Обе задачи могут быть аппроксимированы с коэффициентом 2 с полиномиальным временм —
просто находим произвольное максимальное паросочетание M[17].
Задачи перечисления[править | править код]
Число паросочетаний в графе известно как индекс Хосойи. Вычисление этого числа является #Pполной задачей. Задача остаётся #P-полной в специальном случае перечисления совершенных
паросочетаний в двудольном графе, поскольку вычисление перманента случайной 0-1 матрицы (другая #Pполная задача) — это то же самое, что вычисление числа совершенных паросочетаний в двудольном
графе, имеющем заданную матрицу в качестве матрицы смежности.
Автор
shhrike
Документ
Категория
Техническая литература
Просмотров
17
Размер файла
29 Кб
Теги
trening2018, графов
1/--страниц
Пожаловаться на содержимое документа