Представление графов в памяти компьютера

Пусть дан орграф с n пронумерованными вершинами. Матрица А размером n n, заполненная числами

a_ij=

называется матрицей смежности орграфа.

Такая матрица определяет орграф однозначно вместе с нумерацией вершин.

Точно также строится матрица смежности неориентированного графа. Она обладает дополнительным свойством a_ij= a_ji, т.е. матрица симметрична относительно главной диагонали. Поэтому достаточно хранить в памяти только верхний треугольник матрицы смежности A’.

Пусть дан граф с n вершинами. Пронумеруем вершины произвольно и составим матрицу смежности А, поскольку граф не ориентированный, она будет симметрична относительно главной диагонали, поэтому достаточно знать ее верхний треугольник А ’ (рис 15).

Рис. 15

Расположим А’ в виде двоичной строки (слева направо, сверху вниз). Меняя нумерацию вершин, мы получим другие двоичные строки. Сравним их между собой как двоичные числа. Наибольшее из двоичных чисел называется кодом Харари, а возникшая при этом нумерация вершин – канонической. Код Харари определяет граф однозначно, но не всякое число может быть кодом Харари.

1. Найти код Харари графа (рис. 16)

Рис. 16

Дата добавления: 2014-11-20