Декартова сумма графов

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

Декартова сумма графов (Cartesian sum of graphs) — граф \Sigma = H_{1} \oplus H_{2} \oplus \, \ldots \, \oplus H_{k} множество вершин которого есть декартово произведение множеств вершин графов H_{i} и в \Sigma существует ребро (v,w), где v = (v_{1}, \ldots , v_{k}) и w = (w_{1}, \ldots , w_{k}) тогда и только тогда, когда хотя бы в одном графе H_{i} найдется ребро (v_{i},w_{i})

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.