Сильная степень графа: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 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]] | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 12:25, 2 сентября 2011
Сильная степень графа (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].
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.