Как найти декартово произведение двух графов

Например: Найти декартово произведение графов Γ1 и Γ2

РЕШЕНИЕ.

Если даны два ориентированных графа Γ1 и Γ2, то их декартово произведение строится так. В качестве множества вершин берётся декартово произведение множеств вершин, то есть вершинами нового графа будут все пары вида (v1,v2), где vi -- вершина графа Γi (i=1,2). Далее проводим ориентированные рёбра, делая это для каждой из пар ориентированных рёбер из Γ1 и Γ2. Например, если e1 и e2 -- два таких ребра, где первое идёт из a в b, а второе из c в d, то проводим стрелочку из вершины (a,c) в вершину (b,d).

В Вашем примере получится ориентированный граф с четырьмя вершинами и одной стрелочкой.