Декартово произведение графов

Декартово произведение графов (Cartesian product of graphs) — граф $\pi =H_1\times H_2\times \dots \times H_k$ множество вершин которого есть декартово произведение множеств вершин графов $H_i$и в $\pi$ существует ребро $(v,w)$, где $v=(v_1,\dots ,v_k)$ и $w=(w_1,\dots ,w_k)$ тогда и только тогда, когда существует семейство ребер

$E_1=(v_1,w_1),\dots ,E_k=(v_k,w_k),E_i\subset H_i.$

См. также

• Произведение графов.

Литература

• Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.

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