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

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


img

РЕШЕНИЕ.

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

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

Категория: Комбинаторика | Просмотров: 6085 | Добавил: Admin | Теги: декартово произведение графов | Рейтинг: 0.0/0
Всего комментариев: 0
avatar
close