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

Пусть А₁ и A₂ – матрицы смежности вершин графов G₁ (X,E₁ ) и G(X,E₂ ) соответственно. Рассмотрим матрицу A₁₂ элементы a_ij которой вычисляется так:

_n

a_ij = Ú a _{1 ik} Ù a _{2 kj} (1)

^{k =1}

где a_1ik и a_2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент a_ij равен 1, если в результирующем графе G₁ (G₂ ) существует дуга, исходящая из вершины x_i и заходящая x_j , и нулю – в противном случае.

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

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