Сильная степень графа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Сильная степень графа''' (''Strong degree of a graph'') - для графа <math>G=(V,E)</math> граф <math>G^{...)
 
Нет описания правки
Строка 1: Строка 1:
'''Сильная степень графа''' (''Strong degree of a graph'') -  
'''Сильная степень графа''' (''[[Strong degree of a graph]]'') -  
для графа <math>G=(V,E)</math> граф <math>G^{k} = (V^{k}, E^{k})</math> у
для [[граф|графа]] <math>G=(V,E)</math> граф <math>G^{k} = (V^{k}, E^{k})</math> у
которого множество вершин <math>V^{k} = \underbrace{V \times V
которого множество вершин <math>V^{k} = \underbrace{V \times V
\times \ldots \times V}_{k}</math> а несовпадающие вершины
\times \ldots \times V}_{k}</math> а несовпадающие вершины
<math>(u_{1}, u_{2}, \ldots, u_{k})</math>и <math>(v_{1}, v_{2}, \ldots,
<math>(u_{1}, u_{2}, \ldots, u_{k})</math> и <math>(v_{1}, v_{2}, \ldots,
v_{k})</math>смежны в графе <math>G^{k}</math>тогда и только тогда, когда
v_{k})</math> [[смежные вершины|смежны]] в графе <math>G^{k}</math> тогда и только тогда, когда
для каждого индекса <math>i = 1, 2, \ldots, k</math> выполняется
для каждого индекса <math>i = 1, 2, \ldots, k</math> выполняется
условие <math>u_{i} = v_{i}</math>или <math>(u_{i},v_{i}) \in E</math>.
условие <math>u_{i} = v_{i}</math> или <math>(u_{i},v_{i}) \in E</math>.
==Литература==
==Литература==
[Лекции]
[Лекции]

Версия от 18:49, 29 января 2010

Сильная степень графа (Strong degree of a graph) - для графа [math]\displaystyle{ G=(V,E) }[/math] граф [math]\displaystyle{ G^{k} = (V^{k}, E^{k}) }[/math] у которого множество вершин [math]\displaystyle{ V^{k} = \underbrace{V \times V \times \ldots \times V}_{k} }[/math] а несовпадающие вершины [math]\displaystyle{ (u_{1}, u_{2}, \ldots, u_{k}) }[/math] и [math]\displaystyle{ (v_{1}, v_{2}, \ldots, v_{k}) }[/math] смежны в графе [math]\displaystyle{ G^{k} }[/math] тогда и только тогда, когда для каждого индекса [math]\displaystyle{ i = 1, 2, \ldots, k }[/math] выполняется условие [math]\displaystyle{ u_{i} = v_{i} }[/math] или [math]\displaystyle{ (u_{i},v_{i}) \in E }[/math].

Литература

[Лекции]