Код Харари графа

Пример

- симметричная матрица

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

ì í î

1, если существует дуга из вершины х_i в вершину х _j

0, если нет

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

· ·

· ·

Петли изображаются единицами на главной диагонали.

Матрица смежности определяет орграф однозначно (вместе с нумерацией его вершин).

При перемене нумерации вершин строки и столбцы меняются местами. Матрицу смежности аналогично строят и для неориентированного графа, но она будет обязательно симметричной.

· ·

· ·

Замечание. Обычно матрица смежности очень разрежена (большой процент нулей), чем ближе граф к полному графу (в котором проведены все возможные ребра или дуги), тем больше заполнена матрица единицами.

II Матрица инцидентности (инциденции). Если граф имеет n вершин и m дуг, то составим матрицу В размера m x n, заполненную числами b_ij.

	ì ï í î

1, если вершина х_i есть начало дуги U_j

-1, если вершина х_j есть конец дуги U_j

b_ij = 0, если х_i не инцидентно дуге U_j

2, если х_i и начало, и конец дуги U_j(дуги)

Заметим, что в каждом столбце матрицы инциденции +1 и –1, а остальные 0 (или одна»2» если это петля), поэтому матрица В будет весьма разреженной при большом числе вершин.

Пусть дан неориентированный граф. Тогда, нумеруя его вершины, составим матрицу смежности А. Поскольку она симметрична, достаточно знать верхний треугольник .

n

Расположим в виде двоичной строки (cлева направо и сверху вниз).

Например, 010 …. 0

Меняя нумерацию вершин, получим другие двоичные строки. Наибольшая из них называется кодом Харари, а соответствующая нумерация вершин – канонической. При желании переводим код в десятичное число.

При этом двоичные строки сравниваем как числа (по первому биту).

Заметим, что не всякое число служит кодом Харари некоторого графа

Следующие способы применяются только для деревьев. Поэтому изучим это понятие.

Дата добавления: 2014-01-06