Операции над графами. Части графов

Пусть граф G содержит множество V вершин и множество Е ребер.

Определим некоторые операции на графах:

1. Удаление или добавление ребра;

2. Удаление вершины. Из множества вершин удаляем выбранную вершину, а из множества ребер все инцидентные ей ребра;

3. Стягивание ребра. Отождествляем (стягиваем) вершины инцидентные выбранному ребру;

4. Добавление вершины (разбиение ребра). Выберем некоторое ребро (u,v) из множества ребер и удалим его. В множество вершин добавим новую вершину w, а в множество ребер новые ребра (u,w) и (w,v);

5. Объединение графов. Объединением графов и называют граф , где ;

6. Пересечение графов. Пересечением двух графов G₁ и G₂ называется граф , где , .

Маршрутом длины n называется непустая последовательность n ребер вида:

v1, e1, v2, e2, v3, e3, …, vn, en, vn+1,

.

где ребро e_j (j = 1, 2, …, n) соединяет вершины v_j и v_j+1 . Очевидно, что в последовательности. одни и те же вершины могут повторяться.

Маршрут называется цепью, если в нем нет повторяющихся ребер.

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

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

Замкнутая цепь называется циклом.

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

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

Число ребер, входящих в цепь, называется длиной цепи или расстоянием между соответствующими вершинами

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