2014-02-12
322
Опр. Матрицей соседства (смежности) А(G) неориентированногографа G наз ывается матрица размера n´n, где n— число вершин данного графа, причем ее элементы aij представляют собойчисло различных ребер, соединяющих вершины v i иv j, равно числу ребер, соединяющих вершины v i иv j.
Отметим, что если существует ребро, соединяющее две вершины, то эта пара вершин называется соседними (смежными).
Матрица соседства неориентированного графа всегда симметрична, т.к. число ребер, соединяющих вершины v i иv j, равно числу ребер, соединяющих вершины v j и v i.
По матрице соседстваможно определить ряд свойств графа:
1) если в графе есть изолированная вершина v i, то i-тая строка и i-ый столбец ц будут состоять из 0;
2) еслиграф имеет петлю, то на главной диагонали соответствующий элемент будет отличен от 0.
Замечание 3.
Как уже было сказано, на основании матрицы соседства можно посчитать степень вершинграфа,а именно:
- если у графа нет петель при вершине v i, то ее степеньравна сумме всехэлементов i-той строки или же i -тогостолбца
- если в графе присутствуют петли, то при подсчете валентности каждая петля учитывает ся дважды ( например, если петля при вершине v i, то ее степень также вычисляют суммированием всех элементов i-той строки (i-того столбца), но при этом элемент аii,стоящий на главной диагонали нужно увеличить в 2 раза)
|
|
|
Таким образом, матрица соседства нашего графа имеет вид:
А(G)=
3) Запишем матрицу инцидентности данного графа.
Опр. Матрицей инцидентности B(G) неориентированного графа G называется матрица размераn´m, где n — число вершин данного графа,m - чи с ло ребер, где bij определяются следующим образом:
- bij=1, если вершина vi принадлежит ребру ej
- bij=0, если вершина vi не принадлежит ребру ej, или если ej — петля.
Итак, матрица инцидентностинашего графа определяется следующим образом:
e1 e2 e3 e4 e5 e6 e7
B(G) =
4)В этом пункте нам также не обойтись без ряда определений.
Опр. Расстоянием d( vi, vj ) между вершинами vi‘, и vjв неориентированном графе G называется наименьшее число ребер, соединяющих эти вершины.
Опр. Условный радиус г рафа относительно вершины vi, вычисляют последующей формуле:
г(vi)=max d(vi,vj).. Радиус граф R(G) - это наименьший из условных радиусовграфа.
Опр. Центром графа называется множество вершин, относительно которыхусловные радиусы графа совпадают с радиусом графа.
Таким образом, теперь мы можем определить таблицу расстояний, радиус и центр данногографа.
| V1 | v2 | v3 | v4 | r(vi) | |
| V1 | |||||
| V2 | |||||
| V3 | |||||
| V4 |
Следовательно, радиусграфа R(G)=1,откуда получаем, что центр графа
— это множество вершин { v1 v2 v3 v4 }.
|
|
|
