5.6. Операции над графами

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

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

Удаление вершины. При удалении вершины из графа удаляются не только сама вершина, но и все инцидентные ей ребра (дуги). Пример удаления центральной вершины v из графа приведен на рис.14.

Слияние или отождествление вершин. Говорят, что вершины и в графе G отождествляются (сливаются), если они заменяются такой новой вершиной , что все ребра (дуги) графа, инцидентные и , становятся инцидентными новой вершине .

Стягивание ребра (дуги). Эта операция означает удаление ребра и отождествление его концевых вершин. Граф G₁ называется стягиваемым к графу G₂, если граф G₂ может быть получен из G₁ в результате некоторой последовательности стягиваний ребер. На рис.15 указан исходный граф, а так же граф, полученный стягиванием ребра _.

Подразбиение ребра. С графической точки зрения эта операция означает «внесение в ребро новой вершины». Операция разбиения ребра проиллюстрирована на рис.16.

Рассмотрим алгебраические операции над графами.

О бъединение графов. Объединением графов и называется граф , множество вершин которого является объединением вершин графов и , а множество ребер – объединением множеств ребер и (рис.17).

Пересечение графов. Пересечение графов и представляет собой граф , множество вершин которого состоит только из вершин, присутствующих одновременно в графах и , т.е. из пересечения множеств а множество ребер состоит только из ребер, присутствующих одновременно в графах и . т.е. из множества (рис. 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-той вершинами.)