Суперпозиция графов: различия между версиями

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

Версия от 12:58, 3 февраля 2010

Суперпозиция графов (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} }[/math] [math]\displaystyle{ 1 \leq i \leq m }[/math], окрашены в цвет [math]\displaystyle{ i }[/math]; тогда суперпозиция этих графов есть граф на том же множестве вершин, что и исходные графы, и две вершины смежны по ребру [math]\displaystyle{ i }[/math], если они смежны в графе [math]\displaystyle{ G_{i} }[/math]

Литература

[Харари-Палмер]