Сильная степень графа

Материал из WikiGrapp
Перейти к:навигация, поиск

Сильная степень графа (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.