Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

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

6

Кольцевой суммой графов G₁ и G₂ называется граф , где (рис.19).

Произведением графов и называется граф G=(S,U), у которого множество вершин полученного графа является прямым произведением множеств вершин , а множество ребер U образуется следующим образом: вершины и смежны в графе G, когда либо вершины и совпадают, а вершины и смежны в G₂, либо вершины и совпадают, а вершины и смежны в G₁.

На рис. 20 показано произведение двух графов - цепей P₃ и P₄.

5.7. Пути, контуры, маршруты, цепи, циклы

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

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

Теорема 1: если между вершинами в орграфе существует путь, то существует и простой (элементарный) путь между ними.

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

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

Маршрут часто обозначается посредством перечисления ребер в этом маршруте, например . В маршруте одно и то же ребро может встречаться несколько раз. Если начало и конец маршрута совпадают, т.е. , то маршрут называется замкнутым или циклическим, в противном случае - открытым.

Если все ребра различны, то маршрут называется цепью. Например, на рис. 21 цепью является маршрут . Если цепь не содержит повторяющихся вершин (все вершины, а значит, и ребра, различны), то маршрут называется простой цепью. Например, на рис. 21 простой цепью является маршрут .

Замкнутая цепь называется циклом, например, маршрут является циклом. Замкнутая простая цепь называется простым циклом, например, маршрут является простым циклом. Число циклов в графе G(V,Е) обозначается . Граф без циклов называется ациклическим.

Длиной маршрута называется количество ребер в нем (с повторениями).

Теорема 2. Если существует маршрут между вершинами, то существует и простая цепь между ними.

Теорема 3. Для того, чтобы граф представлял собой простой цикл, необходимо и достаточно, чтобы каждая вершина имела бы степень 2.

Теорема 4. Для того, чтобы n–вершинный граф имел хотя бы один цикл, необходимо и достаточно, чтобы матрица , составленная и степеней матрицы смежности A, имела хотя бы один ненулевой диагональный элемент. (Как отмечалось ранее, каждый ij-тый элемент матрицы указывает количество маршрутов длиной q между i-той и j-той вершинами.)

5.8. Расстояние в графах

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

(симметричность),

(неравенство треугольника).

Матрица D=(d_ij), в которой d_ij=d(v_i,v_j), называется матрицей расстояний. Заметим, что матрица D симметрична, т. е. D^T=D. Для фиксированной вершины , величина называется эксцентриситетом вершины . Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее вершины. Если D – матрица расстояний, то эксцентриситет е(v_i) равен наибольшему из чисел, стоящих в i-й строке.

Максимальный эксцентриситет вершин графа называется диаметром графа G и обозначается diam(G). Минимальный из всех эксцентриситетов вершин графа называется радиусом графа G r(G): r(G) = min{e(v_i)|v_iV}. Вершина v_i называется центральной, если е(x_i)=r(G). Множество всех центральных вершин графа называется его центром. Вершина v_i называется периферийной, если ее эксцентриситет равен диаметру графа.

П ример 5.1. Найдем центр и диаметр графа G, изображенного на рис. 22.

Матрица расстояний D имеет вид

_.

Матрица D позволяет найти эксцентриситеты как максимальные значения по строкам: е(1)=3, е(2)=2, е(3)=3, е(4)=2, е(5)=2 и, следовательно, diam(G)=3. Вершины и являются периферийными. Радиус графа, показанного на рис. 22, равен 2, а его центром является множество { , , }.

В полном графе К_п все различные вершины смежны, и поэтому diam(K_n) = r(К_n) = 1.

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

5.9. Связность в неориентированных графах

Две вершины неорграфа графа называются связными, если существует маршрут, их связывающий. Неориентированный граф G(V, E) называется связным, если для любой пары вершин , существует соединяющая их цепь.

Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств оказываются несвязны. Все выделенные таким образом подграфы называют компонентами связности графа G. Граф, имеющий одну компоненту связности, называется связным графом. Если свойство связности не выполняется, граф называется несвязным. Компонентой связности неориентированного графа G(V, E) называется максимальный связный подграф, т.е. не являющийся подграфом любого другого связного подграфа.

Отношение связности разбивает множество вершин на классы эквивалентности (компоненты связности).

Чтобы граф с n вершинами был связным, он должен иметь не менее (n-1) рёбер.

Теорема. Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно

.

Если граф связный и без циклов (то есть это дерево), то удаление любого ребра приведёт к потере связности.

Свойство связности вершин неорграфа графа описывается квадратной матрицей связности S = [s_ij] порядка n, где n - число вершин. Элементы матрицы связности могут принимать значение 1, если существует цепь, соединяющая вершины v_i и v_j, или значение 0, если не существует цепи, соединяющей вершины v_i и v_j..

Матрица связности неориентированного графа является симметрической, и может быть приведена к блочно-диагональному виду, как, например, для графа, представленного на рис. 23.

Вершина называется шарниром (или точкой сочленения), если при ее удалении число компонент связности увеличивается. Ребро, при удалении которого увеличивается число компонент связности, называется перешейком (мостом). У графа, изображенного на рис. 24, вершина является шарниром, а ребро ( , ) является мостом.