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

Материал из WikiGrapp
Версия от 12:25, 2 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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