G) найти точки сочленения и мосты.
Расстоянием между двумя вершинами vi и vj графа называется длина кратчайшей простой цепи, соединяющей эти вершины. Если вершины в графе не связаны, то расстояние полагается равным бесконечности. Обозначается: d(vi,vj).
Матрицей расстояний D называется такая квадратная матрица размером p´p, элементы которой находятся по формуле:
Эксцентриситетом вершины называется длина максимальной геодезической, исходящей из этой вершины. Обозначается: e(v).
Геодезической называется кратчайшая простая цепь между вершинами. Обозначается: σ(u,v).
Радиусом графа называется минимальный среди всех эксцентриситетов. Обозначается: r(G).
Диаметром графа называется максимальный среди всех эксцентриситетов. Обозначается: d(G).
Центром графа называется такое множество его вершин, для которого радиус равен эксцентриситету.
Периферией графа называется такое множество его вершин, для которых эксцентриситет равен диаметру.
Вершина называется точкой сочленения, если ее удаление приводит к появлению в графе большего числа компонент связности.
Ребро называется мостом, если удаление его приводит к появлению большего числа компонент связности.
Граф называется неразделимым, если в нем отсутствуют точки сочленения.
Блок – это максимальный неразделимый подграф исходного графа.
Так как граф G1 связный, то он имеет только одну компоненту связности, совпадающую с самим графом. Построим матрицу расстояний графа G1:
| D | e(vi) | |||||||||||||
В графе G1:
a) определим эксцентриситеты вершин:
e(1)=6; e(2)=6; e(3)=5; e(4)=4; e(5)=4;
e(6)=5; e(7)=4; e(8)=4; e(9)=7; e(10)=5;
e(11)=6; e(12)=5; e(13)=7;
b) определим радиус:
r(G1)=e(4)=4;
c) определим диаметр:
d(G1)=e(13)=7;
d) определим центр:
множество вершин {4,5,7,8} – центр графа;
e) определим периферию:
множество вершин {9,13} – периферия графа;
f) выделим блоки:
 |
g) найдем точки сочленения и мосты:
если удалить вершину 2, или вершину 1, или вершину 12, то компонент связности в графе станет больше, следовательно, точками сочленения данного графа являются вершины 1, 2, 12;
если удалить ребро (2,9), или ребро (1,12), или ребро (1,13), то граф станет не связным, следовательно, мостами данного графа являются ребра (2,9), (1,12), (1,13).
5. В графе G2: