Инструменты пользователя

Инструменты сайта


examination:diskretka:question6

Вопрос №6. Основные действия с графами: композиция (произведение) графов. Свойства композиции. Степени графа относительно композиции

**Композиция графов**

Г1=(V,E1,I1) Г2=(V,E2,I2) Г=Г1ºГ2=(V,E,I)- композиция или произведение графов т.е.


Обобщение для конструкции композиции графов, на случай несовпадения множества вершин.

Замечание: конструкция композиции графов в целях избежания «накладок» с одинаковыми именами ребер в различных графах, предполагает, что ∀ e∈E1∩E2, I1(v,e,w)=I2(v,e,w).

Пусть ∃ Г1=(V1,E1,I1),Г2=(V2,E2,I2)

Г=Г1∪Г2 (при условии, что ∀ e∈E1∩E2, I1(v,e,w)=I2(v,e,w))

Замечание: Для всякого графа определены его степени относительно композиции: Граф ε не имеет ребер.

examination/diskretka/question6.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)