Математическое моделирование на графах. Часть 1. Берцун В.Н. - 19 стр.

UptoLike

Составители:

Рубрика:

Глава 1. Основные понятия теории графов 19

123

Рис. 1.21

Для изоморфных графов некоторые числовые характеристики

(инварианты) сохраняются. К инвариантам относятся, например,

число вершин, число ребер графа и др. Однако совпадение числа

вершин, числа ребер и степеней вершин не всегда соответствует

изоморфным графам. Неизвестно набора инвариантов, определяю-

щих граф с точностью до изоморфизма.

Свойства графов можно исследовать и с помощью матриц, свя-

занных с ними. Матрицей смежности вершин помеченного графа G

называется матрица A = [a

]

, где элемент a

есть число ребер, со-

единяющих вершины x

и x

(при этом петля означает два ребра).

Очевидно, что для простых графов такие матрицы являются симмет-

ричными. На рис. 1.22 представлены неизоморфные графы, разли-

чающиеся отсутствием или наличием простых циклов нечетной

длины.

Рис. 1.22

Матрицы смежности для этих графов имеют соответственно вид

010101 010101

101010 101010

010101 010011

101010 100011

010101 011100

101010 101100

AA==