ВУЗ:
Составители:
Рубрика:
18
структурные особенности системы на язык чисел, фигурирующих в математических
уравнениях. С каждым помеченным графом связаны несколько матриц, которые
часто удается использовать при выявлении определенных свойств графа.
Матрица смежности. Матрицей смежности А=(а
ij
) помеченного графа G с n
вершинами называется матрица порядка (nxn) с элементами
а
ij
=
⎩
⎨
⎧
случаепротивномв
межныjиiвершиныесли
,0
,с ,1
Это симметрическая матрица с нулями по диагонали, в которой число единиц
в стоке (сумма элементов матрицы А(G) по строкам) равно степени
соответствующей вершины. Очевидно, что существует взаимно однозначное
соответствие между помеченными графами с n вершинами и симметрическими
бинарными
(nхn) матрицами с нулями на диагонали. Бинарной называют матрицу,
каждый элемент которой равен 0 или 1.
Рис. 22. Помеченный граф и его матрица смежности.
Аналогично определяются матрицы смежности А мульти- и псевдографов: а
ij
равно
числу ребер, соединяющих вершины i и j (при этом петля означает два ребра).
Также определяется матрица смежности А(G) ориентированного графа G:
а
ij
=
⎩
⎨
⎧
случаепротивномв
Gтпринадлежиvvдугаесли
ji
,0
, ,1
Очевидно, что любая квадратная бинарная матрица является матрицей
смежности некоторого ориентированного графа.
Рис. 23. Ориентированный граф и его матрица смежности.
Абстрактный граф приводит к различным матрицам смежности в зависимости
от нумерации вершин. Пусть G и Н помеченные графы порядка (nxn) и G
≅ Н, т.е. G
и Н различаются только нумерацией вершин, т.е. существует подстановка S на
множестве вершин, сохраняющая смежность: вершины u и v тогда и только тогда
смежны в G, когда их образы S(u) и S(v) смежны в Н. Следовательно, графы
изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
