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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть графы <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex...»)
 
Строка 1: Строка 1:
 +
==Определения==
 
Пусть графы <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex> и непересекающиеся множества ребер <tex>X_1</tex> и <tex>X2</tex>.
 
Пусть графы <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex> и непересекающиеся множества ребер <tex>X_1</tex> и <tex>X2</tex>.
 
{{Определение
 
{{Определение
Строка 10: Строка 11:
 
'''Соединением''' <tex>G_1 + G_2</tex> называется граф, который состоит из <tex>G_1 \cup G_2</tex> и всех ребер, соединяющих <tex>V_1</tex> и <tex>V_2</tex>.
 
'''Соединением''' <tex>G_1 + G_2</tex> называется граф, который состоит из <tex>G_1 \cup G_2</tex> и всех ребер, соединяющих <tex>V_1</tex> и <tex>V_2</tex>.
 
}}
 
}}
 +
[[Файл:соединение.png|thumb|1100px|center]]
 
{{Определение
 
{{Определение
 
|id = proizvedenie
 
|id = proizvedenie
Строка 17: Строка 19:
 
Вершины <tex>u</tex> и <tex>v</tex> смежны в <tex>G=G_1 + G_2</tex> тогда и только тогда, когда (<tex>u_1 = v_1</tex>, а <tex>u_2</tex> и <tex>v_2</tex> - смежные) или (<tex>u_2 = v_2</tex>, а <tex>u_1</tex> и <tex>v_1</tex> - смежные).
 
Вершины <tex>u</tex> и <tex>v</tex> смежны в <tex>G=G_1 + G_2</tex> тогда и только тогда, когда (<tex>u_1 = v_1</tex>, а <tex>u_2</tex> и <tex>v_2</tex> - смежные) или (<tex>u_2 = v_2</tex>, а <tex>u_1</tex> и <tex>v_1</tex> - смежные).
 
}}
 
}}
 +
[[Файл:произведение.png|thumb|1100px|center]]
 
{{Определение
 
{{Определение
 
|id = compozicia
 
|id = compozicia
Строка 24: Строка 27:
 
Вершины <tex>u</tex> и <tex>v</tex> смежны в <tex>G=G_1 + G_2</tex> тогда и только тогда, когда (<tex>u_1</tex> и <tex>v_1</tex> - смежные) или (<tex>u_1 = v_1</tex>, а <tex>u_2</tex> и <tex>v_2</tex> - смежные).
 
Вершины <tex>u</tex> и <tex>v</tex> смежны в <tex>G=G_1 + G_2</tex> тогда и только тогда, когда (<tex>u_1</tex> и <tex>v_1</tex> - смежные) или (<tex>u_1 = v_1</tex>, а <tex>u_2</tex> и <tex>v_2</tex> - смежные).
 
}}
 
}}
 +
[[Файл:композиция.png|thumb|1100px|center]]

Версия 23:33, 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].
Соединение.png
Определение:
Произведением [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] - смежные).
Произведение.png
Определение:
Композицией [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] - смежные).
Композиция.png