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

Пример

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

 

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

ì í î
1, если существует дуга из вершины хi в вершину х j

0, если нет

 

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

 

       
   
 
 


· ·

 
 

 
· ·

 

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

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

       
 
 
 


· ·

 

       
 
 


· ·

 

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

 
 

 

 


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

 
 
ì ï í î


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

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

bij = 0, если хi не инцидентно дуге Uj

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

 

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

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

n

 

 

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

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

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

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

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

 

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