yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.4 Операции с частями графа

Дискретная математика

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

 

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 совпадают, то маршрут  называется циклическим (или просто циклом).

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

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

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

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

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

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

 

 

 

23