Реферат: Операции на графах

Операция декартова произведения графов может быть выполнена в матричной форме.

Пусть G₁ (X,E₁ ) и G₂ (Y,E₂ ) – два графа, имеющие n_x и n_y вершин соответственно. Результирующий граф G₁ ´ G₂ имеет n_x × n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x × n_y ) ´ (n_x × n_y ) . Обозначим через a _{a b} = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z _a =(x_i y_j ) c z _b =(x_k y_l ) . Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a _{a b} = a_(ij)(kl) = K_ik × a_2,jl Ú K_jl × a_1,ik , (2)

где a_1,ik , a_2,jl – элементы матрицы смежности вершин графов G₁ и G₂ соответственно;

K_ik – символ Кронекера, равный 1, если i=k, и нулю, если i ¹ k .

Пример 4. Выполнить операцию декартова произведения на графах, приведенных на рис. 4.

Составим матрицы смежности вершин исходных графов.