Определение

Граф G ₁ называется разбиением графа G, если он может быть получен из G конечным числом операций разбиения ребер.

Определение

Графы G₁ и G₂ называются гомеоморфными, если существуют такие их разбиения, которые являются изоморфными.

Например, графы, изображенные на рис. 5.9, гомеоморфные:

Рис. 5.9

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

ТЕОРЕМА 5.3

(Критерий планарности Понтрягина-Куратовского)

Граф G является плоским или планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K₃,₃ или A₅ .

Следовательно, планарность или непланарность произвольного графа G зависит от того, содержится ли в G подграф, стягиваемый к K₃,₃ и A₅ или нет.

Для каждого графа G существует ровно две альтернативы:

1) граф имеет плоскую реализацию;

2) граф содержит подграф, гомеоморфный K₃,₃ или A₅.

Поэтому решение вопроса о планарности произвольного графа G всегда может быть получено либо построением плоской реализации G, либо нахождением такого подграфа G, который гомеоморфен одному из графов K₃,₃ или A_5.

При этом проверить наличие или отсутствие в G подграфов, стягиваемых к K₃,₃ или A_5, можно путем перебора всех подграфов этого графа.

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

Пример. Граф, приведенный на рис. 5.10 не является плоским:

a

1 2

3

b c

Рис. 5.10

Этот граф является непланарным, поскольку в нем содержится подграф, гомеоморфный K₃,₃. На приведенном рисунке выделены вершины, соответствующие вершинам K₃,₃.

Рис. 5.11

Граф на рис.5.11 является планарным, поскольку он может быть изображен как

Рис. 5.12

На рис. 5.11. и 5.12. изображен один и тот же граф. При этом закрашенная точка – это вершина графа, которая на этих рисунках размещается по-разному.

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

5.5. Пути и связность в графах

Пусть G = (V, U)  некоторый граф.

Отношение смежности (или соседства) вершин этого графа задает пары соседних вершин в G. Рассмотрим транзитивное обобщение понятия связи вершин посредством одного ребра для отношения смежности вершин.

Определение

Последовательность W = a₁, ... , a_n  вершин графа G образует путь в G, если  i = 1, ... , n  1 ((a_i, a_i+1)  U).

Прохождение пути в графе  это последовательное перемещение по вершинам графа, по ребрам, соединяющим такие вершины. О таких ребрах говорят, что они принадлежат пути и что путь проходит через эти ребра. Если W это путь в графе G, то запись E(W) используется для обозначения множества ребер, принадлежащих пути.

Частный случай пути  это пустой путь W = a, который состоит из единственной вершины a. Такой путь начинается и заканчивается в этой вершине.

Вершины a₁ и a_n называются началом и концом пути. При этом говорят, что W ведет из a₁ в a_n. Длиной пути W называется число ребер, проходимых при движении по W из a₁ в a_n. То есть, если W содержит m вершин, то длина W равна m  1.

Путь W называется элементарным, если все вершины в нем разные. Путь W называется простым, если все ребра из E(W) являются разными.

Путь W называется циклом, если его начало и конец совпадают.

Цикл называется элементарным (простым) циклом, если в нем все вершины за исключением первой и последней (все ребра) разные.

Если некоторый путь W в графе G не является элементарным, то он может быть преобразован в элементарный путь с теми же началом и концом.

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

Для каждой такой пары вершин a_i и a_j из W удаляется часть, состоящая из вершин a_i+1, ... , a_j, т.е. путь W=a₁, ... ,a_i, ...,a_j, ... ,a_n преобразуется в путь W₁ = a₁, ... , a_i, a_j+1 , ... , a_n.

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

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

Аналогично можно преобразовывать произвольные циклы в элементарные циклы с теми же начальной или заключительной вершинами.

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

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

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

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

Рассмотрим пример. Предположим, что некоторое предприятие планирует начать выпуск нового вида изделия. При этом предполагается проделать следующие виды работы:

А  проектирование принципиальной схемы изделия;

В  определение изготовителей комплектующих;

C  разработка внешнего вида изделия;

D  заключение договоров на производство комплектующих;

E  разработка технологического процесса;

F  изучение рынка сбыта и определение объема производства;

G  реклама изделия;

H  заключение договоров на поставку изделий;

I  переналадка производственных линий;

J  выпуск пробной партии;

K  доводка технологических процессов;

L  запуск продукции в массовое производство.

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

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

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

Предположим, что для рассматриваемого примера такой граф изображен на рис. 5.13:

A(2)

B(3)

C(2) G(5)

F(8) D(4) H(2)

E(6)

I(3)

J(4) K(6) L(2)

Рис. 5.13

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

Как видим, время, требуемое для реализации всего проекта, определяется самой длинной по общей продолжительности цепочкой этапов, заканчивающейся в L. В нашем случае это: F, E, I, J, K, L. Эта цепочка носит название критического пути.

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

Важной характеристикой семейства всех путей в произвольном графе является связность.

ОПРЕДЕЛЕНИЕ

Граф G называется связным графом, если для любых двух вершин G существует путь, соединяющий эти вершины.

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