Суббота, 10.12.2016, 04:02
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 6
Гостей: 6
Пользователей: 0
» »
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).

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

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


Похожие материалы:

Всего комментариев: 0
avatar
  .