Произведение графов

[StudentKB]

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

[Sonic86]

Есть такое определение и вводится оно естественным образом: инцидентность вершин множителей переносится на инцидентность вершин произведения. В Богопольском Теория групп в начале 2-й главы есть определение (но кроме него больше ничего нет), я его немного упрощу и напишу:

Def. Прямым произведением $X \times Y=(V,E)$ графов $X=(V_X,E_X),Y=(V_Y,E_Y)$ называется граф со множеством вершин $V=V_X \times V_Y$ и множеством дуг $E=E_X \times E_Y$ с условием $\alpha (e_1,e_2) = (\alpha (e_1), \alpha (e_2)), \omega (e_1,e_2)=(\omega (e_1), \omega (e_2))$ для $(e_1,e_2) \in E$.
Здесь для дуги $e$ $\alpha (e)$ - начало дуги, а $\omega (e)$ - конец дуги.

А вообще я в теории графов произведения графов я не встречал.

[Legioner93]

Sonic86 в сообщении #522030 писал(а):

А вообще я в теории графов произведения графов я не встречал.

А как же произведение автоматов? Очень полезная штука.
Оно ровно так и строится. А автомат - это граф.