Операции с частями графа

1.Дополнение. _

Если задан граф G и его часть H, то дополнение части H - H со-

держит части ребер графа G, которые не принадлежат H.

2.Объединение.

H1 U H2 = H

V(H1) U V(H2) = V(H), E(H1) U E(H2) = E(H),

- 23 -

где H1, H2 - части графа H;

V(H), V(H1), V(H2) - множества вершин;

E(H), E(H1), E(H2) - множества рёбер.

_

H U H = G (объединение части графа и его дополнения).

3.Пересечение.

H1 П H2 = H;

V(H1) П V(H2) = V(H) (если Н1 и Н2 не имеют общих вершин, то эта операция не определена);

E(H1) П E(H2) = E(H).

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

Вершина Vo, инцидентная ребру e1 и не инцидентная ребру e2, называется началом маршрута в графе G.

Вершина Vn, инцидентная ребру en и не инцидентная ребру e(n-1),называется концом маршрута.

Число ребер маршрута называется его длиной.

Если вершины Vo и Vn совпадают, то маршрут называется циклическим (или просто циклом).

Отрезок конечного или бесконечного маршрута сам является маршрутом.

Маршрут называется цепью, если все ребра различны, и простой цепью, если все вершины (а значит и ребра) различны.

Другими словами, в цепи ребро может встретиться не более одного раза, в простой цепи вершина - не более одного раза.

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

В частном случае расстояние и протяженность между вершинами

могут быть одинаковыми.