Составим матрицу соседстваданного графа. Для этого введем некоторые понятия.

Опр. Матрицей соседства (смежности) А(G) неориентированногографа G называется матрица размера n´n, гдеn— число вершин данного графа, причем ее элементы a_ij представляют собойчисло различных ребер, соединяющих вершины vi иvj , равно числу ребер, соединяющих вершины vi иvj.

Отметим, что если существует ребро, соединяющее две вершины, то эта пара вершин называется соседними (смежными).

Матрица соседства неориентированного графа всегда симметрична, т.к. число ребер, соединяющих вершины vi иvj, равно числу ребер, соединяющих вершины vj и vi.
По матрице соседстваможно определить ряд свойств графа:
1 ) если в графе есть изолированная вершина vi, то i-тая строка и i-ый столбец ц будут состоять из 0;
2) еслиграф имеет петлю, то на главной диагонали соответствующий элемент будет отличен от 0.

Замечание 3.
Как уже было сказано, на основании матрицы соседства можно посчитать степень вершинграфа,а именно:
-если у графа нет петель при вершине vi, то ее степеньравна сумме всехэлементов i-той строки или же i-тогостолбца
- если в графе присутствуют петли, то при подсчете валентности каждая петля учитываетсядважды (например, если петля при вершине vi , то ее степень также вычисляют суммированием всех элементов i-той строки (i-того столбца), но при этом элемент а_ii,стоящий на главной диагонали нужно увеличить в 2 раза)

Таким образом, матрица соседства нашего графа имеет вид:

А(G)=

3) Запишем матрицу инцидентности данного графа.

Опр. Матрицей инцидентности B(G) неориентированного графа Gназывается матрица размераn´m, где n — число вершин данного графа,m-число ребер, где b_ij определяются следующим образом:
- b_ij_=1,если вершина v_i принадлежит ребру e_j
- b_ij_=0,если вершина v_i не принадлежит ребру e_j, или если e_j — петля.

Итак, матрица инцидентностинашего графа определяется следующим образом:
e₁ e₂ e₃ e₄ e₅ e₆ e₇

B(G) =

4)В этом пункте нам также не обойтись без ряда определений.
Опр. Расстоянием d(v_i , v_j) между вершинами v_i‘, и v_jв неориентированном графе G называется наименьшее число ребер, соединяющих эти вершины.

Опр. Условный радиусграфа относительно вершины v_i, вычисляют последующей формуле:

г(v_i)=max d(v_i ,v_j).. Радиус граф R(G) -это наименьший из условных радиусовграфа.
Опр. Центром графа называется множество вершин, относительно которыхусловные радиусы графа совпадают с радиусом графа.
Таким образом, теперь мы можем определить таблицу расстояний, радиус и центр данногографа.

_V1 v₂ v₃ v₄ r(v_i)

_V1

_V2

_V3

_V4

Следовательно, радиусграфа R(G)=1,откуда получаем, что центр графа
— это множество вершин { v₁ v₂ v₃ v₄ }.