3.4. Подграфы. Связность

Определение. Подграфом графа G называется граф, все вершины и дуги которого содержатся среди вершин и дуг графа G.

Сам граф по отношению к своим подграфам называется надграфом (суграфом или суперграфом).

Теорема. (Критерий плоской реализуемости). Для того, чтобы конечный граф имел плоскую реализацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфным ни одному из графов G₅ и G рис.3.9 и 3.10.

Подграф называется собственным, если он отличен от самого графа.

Подграфом графа G = (V, X) порожденным подмножеством V V, где

V 0, называется граф G₁ = (V₁, X₁), множество дуг Х₁ которого состоит из тех и только тех дуг графа G, оба конца которых лежат в V₁.

Эти определения распространяются и на орграфы.

На рис.3.16 показан подграф графа рис.3.14, порожденный подмножеством

V₁ = {v₁, v₂, v₄}, и его матрица смежности А.

Рис. 3.16

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

Вершина v_j называется достижимой из вершины v_i, если v_i = v_j, или существует путь из вершины v_i в вершину v_j.

Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v_i и v_j существует путь из вершины v_i в вершину v_j.

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

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

На рис. 3.17 показан односторонне связный ориентированный псевдограф и ассоциированный с ним псевдограф.

Рис. 3.17

Определение. Орграф, не являющийся сильно связным, называется слабо связным, если связным является ассоциированный с ним граф.

Орграф рис.3.17 является слабо связным.

Определение. Граф (орграф), не являющийся связным (слабо связным), называется несвязным.

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

У графа, изображенного на рис.3.18, три компоненты связности. У орграфа, изображенного на рис.3.19, три компоненты сильной связности, показанные на рис.3.20.

Рис. 3.18

Рис. 3.19 Рис. 3.20

Утверждение. Пусть G₁(V₁, X₁) – компонента связности (сильной связности) графа (орграфа) G. Тогда G₁ – подграф графа (орграфа) G, порожденный мно-жеством V₁.

Данное утверждение справедливо и для произвольных ориентированных и

неориентированных псевдографов.

Пусть граф G с n вершинами и m ребрами содержит k компонент связности.

Тогда ранг графа определяется как (G) = n – k, а цикломатическое число графа определяется как (G) = m – n + k. При этом (G) + (G) = m.

Ранг и цикломатическое число графа являются одними из наиболее важных характеристик графа.

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

Примером эйлерова графа являются так называемые сабли Магомета рис.3.21. Для этого графа замкнутый путь из первой вершины x x x x x x будет эйлеровым циклом.

Рис.3.21

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

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

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

На рис.3.22 графы G и G являются эйлеровыми, а графы G и G таковыми не являются.

Рис.3.22

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

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

На рис3.23 изображен орграф для которого выполняются условия этой теоремы. Для него ориентированный цикл x x x x x x x является эйлеровым.

Рис. 3.23

Определение. Связный граф называется квазиэйлеровым, если на нем существует эйлерова цепь.

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

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

Из рис.3.22 видно, что связные графы G и G - квазиэйлеровы, т.к. они имеют эйлеровы цепи (у них ровно по две вершины нечетной степени). Ранее отмечалось, что эти графы не имеют эйлеровых циклов.

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

Длина любой гамильтоновой цепи равна (n-1), а длина любого гамильтонового цикла равна n – число вершин псевдографа.

С понятием гамильтоновых циклов связана так называемая задача о коммивояжере: в нагруженном графе надо определить гамильтонов цикл минимальной длины.

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

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

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

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

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

Необходимым условием существования гамильтоновых цепей и циклов является связность графа.

Теорема. Если в графе с n вершинами для любых двух различных несмежных вершин v_i и v_j графа выполняется условие

deg v_i + deg v_j ≥ n, (3.6)

то в графе существует гамильтонов цикл.

Если выполняется условие

dеg v + deg v ≥ n – 1, (3.7)

то в графе существует гамильтонова цепь.

Следствие. Если для любой вершины v графа выполняется условие

deg v ≥ n/2,

то в графе существует гамильтонов цикл.

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

Для графа G оба условия теоремы выполняются, поэтому он имеет гамильтонов цикл и гамильтоновы цепи.

Для графа G условие (3.7) выполняется, а условие (3.6) нет, поэтому граф G имеет гамильтоновы цепи, но не имеет гамильтонов цикл.

Эйлеровы и гамильтоновы циклы не являются эквивалентными понятиями. Это видно из рис. 3.22. Для графа G₁ есть оба цикла, для графа G₂ есть эйлеров цикл, но нет гамильтонова, для графа G₃ есть гамильтонов цикл, но нет эйлерова, а для графа G нет

обоих циклов.