Пример решения типовых задач

Пример 1. Для вершин v1 и v6 графа G на рис.16 привести примеры марш­рута, цепи, простой цепи; определить в графе цикли­ческий маршрут, цикл, простой цикл, приняв вер­шину v1 за их начало и ко­нец.

Для вершин

- маршрут, не являющийся цепью, - (е1, е2, е3, е4, е5, е1, е8, е7, е6, е1, е8, е7) или (е1, е2, е3, е4, е5, е1, е8, е7) и т.п.;

Рис. 16

- цепь, не являющаяся простой цепью, - ( е1, е2, е3, е4, е5, е6)

- простая цепь - ( е1, е6) или - ( е8, е7) Для вершины v1:

- циклический маршрут, не являющийся циклом, - (е1, е2, е3, е4, е5, е7, е3, е4, е5, е6, е7, е8, е1, е6 , е7, е8)

- цикл, не являющийся простым циклом, - (е1, е2, е3,е4, е5, е6, е7, е8,)

- простой цикл -(е1, е6, е7, е8)

Пример 2. Какими свойствами обладает отношение связанности вершин н-графа на рис. 17. Чему равно число vc связных компонент графа G на рис. 17

1. Отношение связан­ности вершин н-графа обла­дает свойствами:

• рефлексивности: если вершина vG связана с ка­кой-либо другой вершиной v’, то она связана и сама с собой

(изолированные вер­шины также считаются свя­занными сами с собой);

• симметричности: если в графе существует маршрут с началом v’ и концом v” то существует маршрут с началом v” и концом v’;

• транзитивности: если вершина v’ связана v”маршрутом

M’(e’1,..,e’n), а v” и v”’- маршрутом M”(e”1,…,e”p), то v’ связана с v”’ маршрутом M(e’1,…,e’n, e”1,…,e”p)

Таким образом, отношение связанности вершин н-графа является отношением эквивалентности, а значит, разбивает все множество

Рис. 17

вершин V(G) на непересекающиеся подмно­жества

так что вершины одного и того же множества Vi связаны друг с другом, а вершины различных множествVi и Vj не связаны между собой: Ø. Поэтому в графенет ребер с концами в различных множе­ствах Vi и Vj, и он может быть разложен в прямую сумму подграфов

В графе G на рис. 17 V(G)={v1, v2,….,v11}. Отношение связанности вершин разбивает G на 4 непересекающихся класса: V1={v1, v2, v3,v4 v5}, V2={v6, v7}, V3={v8}, V4={v9,v10 v11}.

Поэтому граф G представляет прямую сумму

подграфов, являющихся связными компонентами графа G(V).

Таким образом, число связных компонент графа G на рис. 17, vc=4

Пример 3. Для четырех графов на рис.17 определить расстояния между вершинами. Какие вершины являются центрами графов? Чему равны радиусы графов?

Пусть G1 - граф с вершинами V1={v1,….v5}, G2 - с вершинами V2={v6,v7}, G3 - с вершинами V3={v8}, G4 - с V4={v9,v10,v11}.

Расстояние d(v’,v”) между вершинами v’, v” как минимальная длина простых цепей с началом v’и концом v”(за­метим, что d(v’,v”)= d(v”,v’)

G1= d(v1,v5)=2, d(v1,v4)=1, d(v3,v5)=2 и тд.

G2= d(v6,v7)=1, d(v6,v6)=d(v7,v7)=0

G3= d(v8,v8)=0

G4= d(v9,v10)=1, d(v9,v11)=2, d(v10,v11)=1, d(v9,v9)=0

Для определения центров и радиусов графов G1 – G4 найдем предварительно для каждого максимальные расстояния r(v’) от вершины v’:

G1= r(v1) = 2, r(v2)=2, r(v3)=2, r(v4)=1, r(v5)=2

G2= r(v6)=1, r(v7)=1

G3= r(v8)=0

G4= r(v9)=2, r(v10)=1, r(v11)=2

Отсюда нетрудно определить радиусы r(G) = min r(v') и центры G:

r(G1) = 1, центр - вершина v4;

r(G2) = 1, центры - обе вершины v6, v7;

r(G3) = 0, центр - вершина v8;

r(G4) = 1, центр - вершина v10