Необходимо найти графическое прямое произведение графов

Необходимо найти графическое прямое произведение графов $$G_{1} \times G_{2} $$ .

$$G_{1} = (V_{1}, E_{1}) $$ , где: $\[V_{1} = {v_{1}, v_{2}, v_{3}, v_{4}}, \]$ $\[E_{1} = {⟨ v_{1}, v_{2} ⟩, ⟨ v_{2}, v_{4} ⟩, ⟨ v_{2}, v_{3} ⟩, ⟨ v_{3}, v_{3} ⟩, ⟨ v_{1}, v_{4} ⟩} . \]$
$$G_{2} = (V_{2}, E_{2}) $$ , где: $\[V_{2} = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}}, \]$ $\[E_{2} = {⟨ v_{1}, v_{3} ⟩, ⟨ v_{1}, v_{4} ⟩, ⟨ v_{2}, v_{4} ⟩, ⟨ v_{2}, v_{3} ⟩, ⟨ v_{2}, v_{2} ⟩, ⟨ v_{2}, v_{6} ⟩} . \]$

Прямое произведение графов $$G_{1} \times G_{2} $$ определяется как граф, в котором:

Множество вершин: $\[V (G_{1} \times G_{2}) = {(u, v) : u \in V_{1}, v \in V_{2}} . \]$
Это означает, что каждая вершина графа $$G_{1} $$ сочетается с каждой вершиной графа $$G_{2} $$ .
Множество рёбер: $\[E (G_{1} \times G_{2}) = {⟨ (u_{1}, v_{1}), (u_{2}, v_{2}) ⟩ : [⟨ u_{1}, u_{2} ⟩ \in E_{1} и v_{1} = v_{2}] или [⟨ v_{1}, v_{2} ⟩ \in E_{2} и u_{1} = u_{2}]} . \]$
Это означает, что вершины связаны ребром, если:
- вершины $$u_{1} $$ и $$u_{2} $$ смежны в $$G_{1} $$ , а $$v_{1} = v_{2} $$ ;
- или вершины $$v_{1} $$ и $$v_{2} $$ смежны в $$G_{2} $$ , а $$u_{1} = u_{2} $$ .

Множество вершин $$V (G_{1} \times G_{2}) $ :$
Каждая вершина $$G_{1} $$ ( $$v_{1}, v_{2}, v_{3}, v_{4} $$ ) сочетается с каждой вершиной $$G_{2} $$ :
$\[V (G_{1} \times G_{2}) = {(v_{i}, v_{j}) : v_{i} \in V_{1}, v_{j} \in V_{2}} . \]$
Всего вершин: $$| V_{1} | \times | V_{2} | = 4 \times 6 = 24 $ .$
Множество рёбер $$E (G_{1} \times G_{2}) $ :$
Проверяем каждую пару вершин по двум условиям:
- Если $$⟨ u_{1}, u_{2} ⟩ \in E_{1} $$ , то соединяем пары $$(u_{1}, v) $$ и $$(u_{2}, v) $$ для всех $$v \in V_{2} $ .$
- Если $$⟨ v_{1}, v_{2} ⟩ \in E_{2} $$ , то соединяем пары $$(u, v_{1}) $$ и $$(u, v_{2}) $$ для всех $$u \in V_{1} $ .$

Граф $$G_{1} \times G_{2} $$ имеет:

Чтобы избежать перегруженности, конкретное множество рёбер рекомендуется выписать отдельно (или построить графическим способом).

Если требуется графическое изображение, его можно построить на основе полученных данных.

Время — это деньги!