Доминирование.
Пример
Теорема
Если граф G(x) представим с однократными ребрами и без петель и имеет n вершин и K связный компонент, то общее число ребер не превышает числа
max число ребер.
Допустим, задано число связных компонентов. Есть смысл рассмотреть такие графы, в которых свойство компонента представляет собой граф.
Частный случай: Пусть из K-компонентов (K-1) – изолированная вершина какая-то -полный граф имеющий – вершин, тогда - полное число вершин графа .
Локальной степенью вершин этого графа будут равны ( -однородный граф ( , а число ребер в таком графе =
Предположим что в графе хотя бы 2 связных компонента имеющих более одной вершины
(рисунок)
Будем передавать информацию к пошагово, при этом число вершин и общее число связных компонентов не меняются.
Общее число ребер уменьшится на , если уберем одну вершину для одного графа а его число ребер увеличивается на
Таким образом, число ребер будет возрастать.
После того как эту операцию произведем с парой
Таким образом, при данном числе вершин не связных компонентов наибольшее число ребер имеет граф, у которых - компонента – суть изомеров, вершины, а одна компонента – полный граф ( -вершин.
Допустим, имеем всего 2 свойства компонент, тогда
Связность графов
2 часть
Пусть G(x,Г) – ориентированный граф. Граф G(х) называется связным, если он связан с соответственным неориентированным графом G(x) → Gn (x).
Орграф G(x) называется сильно связным, если для любых двух вершин xi , xj существует путь из xi → xj . Очевидно, что сильно связный граф всегда связен, тогда как обратное утверждение в общем случае неверно.
Пример:
Сильно связный граф
Связан, но не сильно
В связном графе принято выделять компоненты связности. В любом графе выделяют связные и несильно связные графы. (Первостепенная и второстепенная работа в технологиях).
Определение: Сильно связный подграф G’ графа G(x,Г) называется максимальным сильно связным подграфом, если не существует сильно связного подграфа G”, строго содержащего в себе G’.
Перечисление таких подграфов представляет собой пустое множество (пустой граф). Однако, в отличие от связных компонент объединения всех максимально сильно связных подграфов может не совпадать с исходным подграфом, что характерно для сетевого планирования.
Алгоритм для отыскания всех максимально сильно связных подграфов в ориентированном графе G(x, Г).
Алгоритм предложен Маль Гранжем.
Обозначим хi = ГхiГ2хi Г3xi … Гnxi – обратное транзитивное замыкание множества вершин, из которых можно попасть в вершину хi любым путём.
С(хi) – множество вершин максимально сильно связного подграфа, содержащего вершину хi.
Это множество содержит сумму вершин хk С(хi),
если хk Гхi ˄ хk Г-1хi хk хi -1 хi , то есть
С(хi) = { хi } (хi -1 хi) ③
Метод отыскания всех максимально сильно связных подграфов состоит из:
1) Берём произвольную вершину хi . Для неё находим транзитивное замыкание, обратное транзитивное замыкание по формуле ③
(орп. С (хi)).
2) Берём вершину С, выбираем хj , повторяем шаг 1.
3) Берём вершину хk и повторяем шаг 1 (это можно назвать набрасыванием сетки на вершины) и так далее.
Для любой вершины матрицы G(x) транзитивное замыкание совпадает с обратным транзитивным замыканием самой вершины в обратном
графе G-1(x).
Деревья.
Деревом называется конечный связный неориентированный граф, имеющий не менее двух вершин и не содержащий циклов (петель и кратных рёбер).
Лесом называется граф без циклов, связный, компоненты которого являются деревья.
Теорема 1: Если граф G(x) имеет n вершин (n>1), то следующие характеристики свойства деревьев равносильны:
1) G(x) связен, нет циклов.
2) G(x) связен, не содержит циклов и имеет n-1 рёбер.
3) G(x) связен и имеет n-1 рёбер.
4) G(x) не содержит циклов, но добавление ребра между двумя любыми несмежными вершинами приводит к появлению одного элементарного цикла.
5) G(x) связен, но утрачивает свойства после удаления ребра.
6) Всякая пара вершин связна цепью, притом одной.
Любое из этих свойств можно рассмотреть как определение дерева.
Теорема 2: Граф G(x) ó содержит частичный граф и является деревом, когда он связен.
Доказательство:
1) Необходимость. Предположим, что граф G(x) не связен, поэтому его частичные графы не связны, так как частичный граф строится на том же множестве вершин.
2) Достаточность. Предположим, что граф G(x) связен, проверим нет ли у него такого ребра, удаление которого нарушит связность. Согласно теореме 1 сам граф G(x) будет деревом, если таких рёбер нет. Если такое ребро есть, то удалим его и проверим, нет ли подобных рёбер в оставшемся частном графе и так далее. Очевидно, что через конечное число шагов мы получим граф без таких рёбер, то есть получим дерево.
3) Резюме. Доказательство теоремы даёт алгоритм построения в заданном графе частного, то есть дерева, его назовём частичным графом, покрывающим деревом, каркасом для связного графа.
Пример:
Пусть задано множество вершин, на котором нужно построить дерево из оставшихся вершин хi . Проведём рёбра на расстоянии ① от вершины х0 , затем ②, ③ и так далее. Вершину х0 назовём корнем дерева. Не существует ни одного ребра (x’n-1 , x”n-1 ), так как появился бы цикл и граф не был бы деревом. Иногда в графе выгодно выделить какую-то цепь, которая называется стволом дерева. Любая вершина, лежащая на стволе, связана со стволом элементарной цепью – ветвь дерева.
Вопрос: Сколько различных деревьев можно построить на n – пронумерованных вершинах.
Решена Кели, показав, что на n – пронумерованных вершинах можно построить nn-2 , результат Кели позволяет сделать следующий вывод:
-имеется n городов, сколькими способами можно построить дороги между ними, чтобы путник мог спокойно их обойти, не останавливаясь в поисках пути и не возвращаясь назад. Пусть также известно стоимость дорог µ( xi , xj ). Какие именно линии можно построить, чтобы все города были связаны, а стоимость минимальна.
Алгоритм: задача построения минимального каркаса.
1) В графе G(x) выбирается ребро, имеющее наименьшую меру. Ребро Е1 , то есть это ребро образец частичного подграфа графа
G(x) А1 (Е1 А1).
Рассмотрим первый шаг. На этом шаге к уже построенному частному графу Аi-1 добавляем ребро Еi , имеющее минимальную меру среди всех неисследованных рёбер.
Ограничение: добавление ребра Еi к Аi-1 не должно приводить к образованию цикла, иначе нужно брать другое ребро. Если имеется несколько рёбер с одинаковыми мерами и удовлетворяющими данному условию, то можно выбирать любое из них.
В соответствии с теоремой 1, на n-1 шаге мы построим частный подграф Аn-1 являющийся каркасом для графа G(x).
Введём доказательство от противного.
Предположим, что покрывающее дерево Аn-1 не является минимальным каркасом, то есть µ(T) < µ(Аn-1). Сравним T и Аn-1 по ходу построения. Пусть Еi первое по ходу построения ребро графа Еi , которое не принадлежит дереву Т, присоединим это ребро к дереву Т, в результате получим объединенный граф Т Еi . По построению граф Аn-1 также является деревом и не содержит циклов, соответственно в этом цикле должно быть хотя бы одно ребро Е’ не принадлежащее Аn-1.
Отвергнуть Е’ мы не можем, так как он принадлежит Т. Удалим ребро Е’ из графа Аn-1 , получим граф Т1 = (Т Еi)\Е’. После удаления ребра граф разрушится, но оставшийся граф Т1 – покрывающий, с каркасом определяющим меру µ(T1). Наверняка µ(T1) µ(T), так как это минимальная мера.
2) Рассмотрим меру µ(Еi) µ(Е’). ②
Рассмотрим в этом неравенстве случай с равенством µ(Еi) µ(Е’). Если бы в графе была мера Еi Е1 , то возвращаемся на шаг 1 и выполняем соответствующие действие. Фактически имеет место равенство µ(Еi) = µ(Е’), соответственно мерой графа µ(Т1) = µ(Т) и получим минимальное значение графа, аналогичная операция производится с графами Аn-1 и Т1 , то есть получим решение:
Т2 = (Т1 Еj)\Е”, через конечное число шагов получим каркас совпадающий с Аn-1 , являющийся минимальной мерой, то есть Т и есть минимальный каркас.
Циклический ранг
Циклический ранг (цикломатическое число) – замечательные числа графа.
Пусть G(x) конечный, связный неориентированный граф. Построим граф из его рёбер. Берём произвольное ребро, далее добавляем к данной части любое ребро, соединённое с ней хотя бы одной общей вершиной. На каждом шаге будем вычислять цикломатическое число.
i = mi – ni + 1 (где mi – число использованных рёбер, ni – вершины).
1: m1 = 1, n1 = 2 => 1 = 0.
Если на каждом шаге число не уменьшается, а увеличивается на единицу, то , если граф имеет m рёбер и n вершин, то n = (G) = m – n +1 0 – это число называется цикломатическим числом графа.
Свойства цикломатического числа.
Пусть граф – дерево, тогда если граф имеет число рёбер меньше числа вершин то j = 0, то есть цикломатический ранг любого дерева = 0, что необходимо и достаточно. Таким образом, необходимость вытекает из свойств деревьев, а достаточность из построения.
Цикломатическое число равно числу независимых циклов.
Прадеревья.
Конечный граф G(x, Г) называется прадеревом с корнем х1 Х, если в каждую вершину, не совпадающую с х1 , заходит единственная дуга и граф G не содержит контуров.
На этом рисунке соотнесенный неориентированный граф для поддерева, также является деревом.
Определение путей и кратчайших путей в графах.
Существует несколько алгоритмов о решении задач о лабиринте.
1) Алгоритм Тарри. Каждое ребро графа проходит дважды в каждом из двух направлений.
Правило 1: не проходить дважды по одному и тому же ребру в одном и том же направлении.
Правило 2: находясь в вершине xj не двигаться по ребру. Приведшему в эту вершину один раз, если имеются другие возможности.
Можно показать, что остановка из-за невыполнения этого алгоритма произойдёт в x0 , причём все рёбра графа к этому времени будут пройдены во всех направлениях по одному разу.
2) Алгоритм Бержа.
Алгоритм прост, но не экономичен.
Л
В ряде случаев, когда известен тип задачи, алгоритм Тарри можно рассматривать в упрощённом виде: идём столько раз вперёд, пока не попадём в висящую вершину, попадая в неё поворачиваем в сторону не пройденного пути, снова попадаем в висящую вершину, пока не попадём в нужную. Пусть соответствует однократному графу (то есть прохождение одного раза).
Отсечение (введение ещё одной вершины, не совпадающей с первой).
Граф G(x) представляет собой граф с нагруженными рёбрами, под длиной пути подразумевается сумма мер.
= (xi , xj), где (xi , xj) принадлежат .
В особый класс выделяются задачи для графа с ненагруженными рёбрами, причём такой граф считается графом с нагруженными рёбрами, длина пути которого составит
i, j (µ(xi , xj)).
Алгоритм 1: Начиная от х0 просматриваем сначала все вершины смежные с х0 путём. Состоящим из одного ребра. У каждой из этих вершин записываем по мере от каждой вершины до х0. На следующем шаге просматриваем все вершины достижимые из х0 , двухрёберными путями, и опять в каждой вершине записываем её расстояние до вершины х0. Очевидно, возможны случаи, когда в какую-нибудь вершину мы попадаем дважды. В таком случае (если в вершину идёт несколько путей), в этой вершине записывается мера кратчайшего из путей и указывается по какому пути достигнута.
Допустим, на некотором шаге попали в вершину хк по пути длинной М, далее исключим из рассмотрения все вершины не совпадающие с хк, для которых длина пути М М1 (так как через эти вершины нет более короткого пути). После этого на оставшемся графе продолжаем осмотр путей описанным способом. Возможно, что на некотором шаге мы опять попадем в хк по пути М2 < М1. Тогда исключим все просмотренные вершины, не совпадающие с хк и длиной < М1. Этот алгоритм представляет собой один из вариантов задачи исследования операции методов динамического программирования.
Алгоритм Форда: Этот алгоритм предназначен для нахождения кратчайшего пути в ориентированном графе из х0 в х1.
На первом шаге каждая вершина хi помечается индексом i. Ищем дугу
(хi , xj) , для которой выполняется неравенство:
j – i µ(xi , xj).
Выполним эту операцию несколько раз, причем j – уменьшается, а индексы установлены до некоторого уровня. Ищем хр – смежную с вершиной хn и такую для которой λn-λp= µ(xр , xn).
Пусть хр – последняя вершина, в которой удалось уменьшить индекс, далее переходим к вершине хs, смежной с вершиной хр такую, что λp - λs = µ(xs , xp). Такая вершина найдётся из аналогичных рассуждений и так далее. В результате последовательность индексов λn , λp , λs … - убывающая, соответственно на каком-то из шагов мы попадём в вершину (xp)к+1 = х0 , для которой . Справедливо следующее утверждение: установившееся значение n есть длина кратчайшего пути, ведущего из х0 в хn.
Внешняя и внутренняя устойчивость графов.
Пусть G(x, Д) – ориентированный граф или неориентированный граф. Подмножество Д , принадлежащее х , называется доминирующим для G, если х\Д является подмножеством ГД, где ГД – отображение.
Теорема 1: Доминирующее множество Д0 является минимальным доминирующим множеством в том случае, когда для каждой вершины
хi0 Д0 выполняется одно из условий:
1) В вершине хi0 не существует входящего ребра (хj0 , хi0) внутреннего для Д0 , оба конца которого лежат в Д0.
2) Существует ребро (хi0, хк), причём хi0 принадлежит, а хк принадлежит Х\Д0 единственное и идущее к хк.
Определение 1: Наименьшее число вершин составляет минимальное доминирующее множество и называется числом доминирования.
Определение 2: Подмножество Т множества Х называется внешним устойчивым множеством для графа Т, если разность Х\Т принадлежит
Т-1 * Т.
Таким образом все вершины, не принадлежащие множеству Т , являются началом хотя бы одного ребра, ведущего в множество Т.
Из определения 1 следует, что всё множество Т является внешне устойчивым.
Определение 3: Внешне устойчивое множество Т называется минимальным, не является внешне устойчивым.
В графе может быть несколько различных минимальных внешне устойчивых множеств с различным количеством вершин. Наименьшее число вершин, входящих в такое множество называется внешне устойчивым числом графа (G).
Из сравнения чисел любое доминирующее множество графа является внешне устойчивым, то есть для графа G(x) = G-1(x). В неориентированном графе понятия внешней устойчивости и доминирования совпадают.
Если G(x) неориентированный граф, то устойчивое число графа S(G) = (G).
Для ориентированного графа такое равенство несправедливо.
Определение: Подмножество S, входящее в Х, называется внутренне устойчивым для графа G(x, Г), если пересечение S ГS = и ГS = ГХ, Х принадлежит S. В частности следует, что пустое множество и множество S состоят из одной петли в единственной вершине.
Внешне устойчивое множество является независимым и несвязным, если в некотором подмножестве вершин хотя бы одна пара соединена ребром, то такое подмножество является зависимым или внешне устойчивым.
Если в некотором подмножестве вершин любая пара вершин соединена ребром, то такое подмножество является полностью зависимым.
Независимое множество, которое становится зависимым после добавления одной вершины, называется максимально независимым множеством. Таким образом, в графе может существовать несколько независимых решений.
Максимальное число вершин, составляющее независимое множество называется числом независимости.
Теорема 2: Независимое множество в неориентированном графе максимально, когда оно доминирующее.
Необходимость: Предположим, что S максимальное множество, покажем, что оно доминирующее.
Для этого возьмем вершину хj принадлежащую Х\S.
S {xj} добавим ее к S. Множество S {xj} не будет независимым множеством, так как вершина xj – конец ребра выходящего из S. Поэтому S – доминирующее.
Достаточность: Предположим, S – неравно доминирующее множество. Покажем, что оно максимально. Для этого xj Х\S добавим к S {xj}, ее добавление приводит к потере свойства, таким образом теорема 2 дает достаточное условие максимальной независимости графа.
Из теоремы 2, .