Теоретико-множественные операции над графами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть графы <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex...»)
(нет различий)

Версия 19:48, 11 января 2015

Пусть графы [math]G_1[/math] и [math]G_2[/math] имеют непересекающиеся множества вершин [math]V_1[/math] и [math]V_2[/math] и непересекающиеся множества ребер [math]X_1[/math] и [math]X2[/math].

Определение:
Объединением [math]G_1 \cup G_2[/math] называется граф, множеством вершин которого является [math]V=V_1 \cup V_2[/math], а множество ребер [math]X=X_1 \cup X_2[/math].


Определение:
Соединением [math]G_1 + G_2[/math] называется граф, который состоит из [math]G_1 \cup G_2[/math] и всех ребер, соединяющих [math]V_1[/math] и [math]V_2[/math].


Определение:
Произведением [math]G_1 \times G_2[/math] называется граф с множеством вершин [math]V[/math] равным декартовому произведению [math]V_1 \times V_2[/math]. Множество ребер [math]X[/math] определяется следующим образом:

Рассмотрим любые две вершины [math]u=(u_1, u_2)[/math] и [math]v=(v_1, v_2)[/math] из [math]V=V_1 \times V_2[/math].

Вершины [math]u[/math] и [math]v[/math] смежны в [math]G=G_1 + G_2[/math] тогда и только тогда, когда ([math]u_1 = v_1[/math], а [math]u_2[/math] и [math]v_2[/math] - смежные) или ([math]u_2 = v_2[/math], а [math]u_1[/math] и [math]v_1[/math] - смежные).


Определение:
Композицией [math]G_1[G_2][/math] называется граф с множеством вершин [math]V[/math] равным декартовому произведению [math]V_1 \times V_2[/math]. Множество ребер [math]X[/math] определяется следующим образом:

Так же рассмотрим любые две вершины [math]u=(u_1, u_2)[/math] и [math]v=(v_1, v_2)[/math] из [math]V=V_1 \times V_2[/math].

Вершины [math]u[/math] и [math]v[/math] смежны в [math]G=G_1 + G_2[/math] тогда и только тогда, когда ([math]u_1[/math] и [math]v_1[/math] - смежные) или ([math]u_1 = v_1[/math], а [math]u_2[/math] и [math]v_2[/math] - смежные).