Например такие графы

img

задан 6 Авг '13 20:18

изменен 7 Авг '13 15:17

Deleted's gravatar image


126

10|600 символов нужно символов осталось
1

Если даны два ориентированных графа $%\Gamma_1$% и $%\Gamma_2$%, то их декартово произведение строится так. В качестве множества вершин берётся декартово произведение множеств вершин, то есть вершинами нового графа будут все пары вида $%(v_1,v_2)$%, где $%v_i$% -- вершина графа $%\Gamma_i$% ($%i=1,2$%). Далее проводим ориентированные рёбра, делая это для каждой из пар ориентированных рёбер из $%\Gamma_1$% и $%\Gamma_2$%. Например, если $%e_1$% и $%e_2$% -- два таких ребра, где первое идёт из $%a$% в $%b$%, а второе из $%c$% в $%d$%, то проводим стрелочку из вершины $%(a,c)$% в вершину $%(b,d)$%.

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

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

ссылка

отвечен 7 Авг '13 0:41

спасибо большое! можно еще один вопрос задать? как найти соединение этих графов (+ так операция эта обозначается)? При соединении графов получаем граф, который является результатом их объединения и добавления ребер, инцидентных вершинам из разных графов. то есть мне нужно добавлять дуги разных направлений (b->c, c->b; a->d, d->a; d->b; b->d; a->c, c->a.)? или достаточно будет(b->c; a->d; d->b; a->c.)

(7 Авг '13 23:23) IviBring

Соединение графов -- это довольно специальное понятие. Оно не относится к числу стандартных. Насколько я знаю, для случая обычных графов под этим понимают два графа с непересекающимися множествами вершин с добавлением полного двудольного графа. Версия для ориентированных графов должна сопровождаться отдельным определением, которому и надо следовать. Скорее всего, там добавляются все двойные стрелки, но лучше уточнить по лекционному курсу.

(8 Авг '13 0:08) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,037
×379

задан
6 Авг '13 20:18

показан
3823 раза

обновлен
8 Авг '13 0:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru