Суперпозиция графов

Материал из WEGA
Версия от 11:35, 12 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Суперпозиция графов (Superposition of graphs) — пусть

[math]\displaystyle{ G_{1}, \; G_{2}, \; \ldots, \; G_{m} }[/math]

[math]\displaystyle{ \,m }[/math] графов, каждый из которых имеет одно и то же множество вершин, содержащее [math]\displaystyle{ \,n }[/math] элементов, и пусть ребра графа [math]\displaystyle{ G_{i},\,1 \leq i \leq m }[/math], окрашены в цвет [math]\displaystyle{ \,i }[/math]; тогда суперпозиция этих графов есть граф на том же множестве вершин, что и исходные графы, и две вершины смежны по ребру [math]\displaystyle{ \,i }[/math], если они смежны в графе [math]\displaystyle{ \,G_{i} }[/math]

Литература

  • Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.