|
Если даны два ориентированных графа $%\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 
falcao спасибо большое! можно еще один вопрос задать? как найти соединение этих графов (+ так операция эта обозначается)? При соединении графов получаем граф, который является результатом их объединения и добавления ребер, инцидентных вершинам из разных графов. то есть мне нужно добавлять дуги разных направлений (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
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
6 Авг '13 20:18
показан
3823 раза
обновлен
8 Авг '13 0:08
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.