Суперпозиция графов: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Суперпозиция графов''' (''[[Superposition of graphs]]'') | '''Суперпозиция графов''' (''[[Superposition of graphs]]'') — | ||
пусть | пусть | ||
<math>G_{1}, \; G_{2}, \; \ldots, \; G_{m}</math> | :::<math>G_{1}, \; G_{2}, \; \ldots, \; G_{m}</math> | ||
— <math>\,m</math> [[граф|графов]], каждый | |||
из которых имеет одно и то же множество [[вершина|вершин]], содержащее <math>n</math> | из которых имеет одно и то же множество [[вершина|вершин]], содержащее <math>\,n</math> элементов, и пусть [[ребро|ребра]] графа <math>G_{i},\,1 \leq i \leq m</math>, окрашены в | ||
элементов, и пусть [[ребро|ребра]] графа <math>G_{i} | цвет <math>\,i</math>; тогда суперпозиция этих графов есть граф на том же множестве | ||
цвет <math>i</math>; тогда суперпозиция этих графов есть граф на том же множестве | вершин, что и исходные графы, и две [[смежные вершины|вершины смежны]] по ребру <math>\,i</math>, | ||
вершин, что и исходные графы, и две [[смежные вершины|вершины смежны]] по ребру <math>i</math>, | если они смежны в графе <math>\,G_{i}</math> | ||
если они смежны в графе <math>G_{i}</math> | |||
==Литература== | ==Литература== | ||
* Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977. | |||
Текущая версия от 11:35, 12 сентября 2011
Суперпозиция графов (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.