Операция произведения графов

Произведением графов и называется граф , для которого , а множество ребер определяется следующим образом: вершины и смежные в тогда и только тогда, когда , а и смежные в , или , а и смежные в (Рис. 2.7)

Рис.2.7

Оперция слияния вершин

Пусть граф, - две его вершины и - множество вершин, смежных с вершиной , а - множество вершин, смежных с вершиной . Граф , полученный присоединением новой вершины к множеству вершин графа и множества ребер вида (), называется графом, полученным из слиянием вершин и . На рис. 2.8. приведен пример слияния вершин 2 и 4.

Рис. 2.8