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

Материал из WikiGrapp
Перейти к:навигация, поиск
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>.
 +
 
  
 
[[Файл:Strong degree of a graph.png|700px]]
 
[[Файл:Strong degree of a graph.png|700px]]
 +
  
 
==Литература==
 
==Литература==
[Лекции]
+
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия на 12:25, 2 сентября 2011

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


Strong degree of a graph.png


Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.