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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
==Определения==
+
__TOC__
−
Пусть графы <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>X_2</tex>.
 
{{Определение
 
{{Определение
 
|id = obedinenie
 
|id = obedinenie
 
|definition =
 
|definition =
−
'''Объединением''' <tex>G_1 \cup G_2</tex> называется граф, множеством вершин которого является <tex>V=V_1 \cup V_2</tex>, а множество ребер <tex>X=X_1 \cup X_2</tex>.
+
'''Объединением''' (англ. ''union'') <tex>G_1 \cup G_2</tex> называется граф, множеством вершин которого является <tex>V=V_1 \cup V_2</tex>, а множество ребер <tex>X=X_1 \cup X_2</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|id = soedinenie
 
|id = soedinenie
 
|definition =
 
|definition =
−
'''Соединением''' <tex>G_1 + G_2</tex> называется граф, который состоит из <tex>G_1 \cup G_2</tex> и всех ребер, соединяющих <tex>V_1</tex> и <tex>V_2</tex>.
+
'''Соединением''' (англ. ''graph join'') <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]]
+
[[Файл:соединение.png|thumb|1100px|center|Соединение <tex>G_1</tex> и <tex>G_2</tex>]]
 
{{Определение
 
{{Определение
 
|id = proizvedenie
 
|id = proizvedenie
 
|definition =
 
|definition =
−
'''Произведением''' <tex>G_1 \times G_2</tex> называется граф с множеством вершин <tex>V</tex> равным декартовому произведению <tex>V_1 \times V_2</tex>. Множество ребер <tex>X</tex> определяется следующим образом:
+
'''Произведением''' (англ. ''cartesian product'') <tex>G_1 \times G_2</tex> называется граф с множеством вершин <tex>V</tex> равным декартовому произведению <tex>V_1 \times V_2</tex>. Множество ребер <tex>X</tex> определяется следующим образом:
−
Рассмотрим любые две вершины <tex>u=(u_1, u_2)</tex> и <tex>v=(v_1, v_2)</tex> из <tex>V=V_1 \times V_2</tex>.
+
* рассмотрим любые две вершины <tex>u=(u_1, u_2)</tex> и <tex>v=(v_1, v_2)</tex> из <tex>V=V_1 \times V_2</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> - смежные).
+
* вершины <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]]
+
[[Файл:произведение.png|thumb|1100px|center|Произведение <tex>G_1</tex> и <tex>G_2</tex>]]
 
{{Определение
 
{{Определение
 
|id = compozicia
 
|id = compozicia
 
|definition =
 
|definition =
−
'''Композицией''' <tex>G_1[G_2]</tex> называется граф с множеством вершин <tex>V</tex> равным декартовому произведению <tex>V_1 \times V_2</tex>. Множество ребер <tex>X</tex> определяется следующим образом:
+
'''Композицией''' (англ. ''lexicographical product'') <tex>G_1[G_2]</tex> называется граф с множеством вершин <tex>V</tex> равным декартовому произведению <tex>V_1 \times V_2</tex>. Множество ребер <tex>X</tex> определяется следующим образом:
−
Так же рассмотрим любые две вершины <tex>u=(u_1, u_2)</tex> и <tex>v=(v_1, v_2)</tex> из <tex>V=V_1 \times V_2</tex>.
+
* так же рассмотрим любые две вершины <tex>u=(u_1, u_2)</tex> и <tex>v=(v_1, v_2)</tex> из <tex>V=V_1 \times 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> - смежные).
+
* вершины <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]]
+
[[Файл:композиция.png|thumb|1100px|center|Композиция <tex>G_1</tex> и <tex>G_2</tex>]]
 +
 
 +
{{Лемма
 +
|about=
 +
о произведении регулярных графов
 +
|statement=
 +
<tex>G_1</tex> и <tex>G_2</tex> — [[Основные_определения_теории_графов|регулярные]] графы. Тогда <tex>G = G_1 \times G_2</tex> — регулярный граф.
 +
|proof=
 +
Пусть степень графов <tex>G_1</tex> и <tex>G_2</tex> будут <tex>k_1</tex> и <tex>k_2</tex> соответственно.
 +
Рассмотрим любую вершину графа <tex>G</tex>: у нее <tex>k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.
 +
}}
 +
 
 +
{{Лемма
 +
|about=
 +
о композиции регулярных графов
 +
|statement=
 +
<tex>G_1</tex> и <tex>G_2</tex> — регулярные графы. Тогда <tex>G = G_1[G_2]</tex> — регулярный граф.
 +
|proof=
 +
Пусть степень графов <tex>G_1</tex> и <tex>G_2</tex> будут <tex>k_1</tex> и <tex>k_2</tex> соответственно.
 +
Рассмотрим любую вершину графа <tex>G</tex>: у нее <tex>|V_2| \cdot k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.
 +
}}
 +
 
 +
{{Лемма
 +
|about=
 +
о произведении двудольных графов
 +
|statement=
 +
<tex>G_1</tex> и <tex>G_2</tex> — [[Основные_определения_теории_графов|двудольные]] графы. Тогда <tex>G = G_1 \times G_2</tex> — двудольный граф.
 +
|proof=
 +
Пусть цвет <tex>c</tex> левых долей <tex>G_1</tex> и <tex>G_2</tex> будет <tex>0</tex>, а правых <tex>1</tex>.
 +
А цвет каждой вершины <tex>v = (v_1, v_2)</tex> графа <tex>G</tex> будет равен <tex>c(v) = (c(v_1) + c(v_2)) \bmod 2</tex>.
 +
 
 +
Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</tex>, два случая:
 +
 
 +
# <tex>u_1 = v_1</tex>, <tex>u_2</tex> и <tex>v_2</tex> — смежные,  значит <tex>c(u_1) = c(v_1)</tex> и <tex>с(u_2) \ne c(v_2)</tex>, из этого следует <tex>c(u) \ne c(v)</tex>,
 +
# <tex>u_2 = v_2</tex>, <tex>u_1</tex> и <tex>v_1</tex> — смежные, аналогично следует <tex>c(u) \ne c(v)</tex>.
 +
Следовательно каждое ребро графа <tex>G</tex> соединяет вершины разного цвета, значит <tex>G</tex> двудольный.
 +
}}
 +
 
 +
==См. также==
 +
* [[Дополнительный, самодополнительный граф]]
 +
* [[Дерево, эквивалентные определения]]
 +
 
 +
== Источники информации ==
 +
* Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 19:23, 4 сентября 2022

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

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


Определение:
Соединением (англ. graph join) [math]G_1 + G_2[/math] называется граф, который состоит из [math]G_1 \cup G_2[/math] и всех ребер, соединяющих [math]V_1[/math] и [math]V_2[/math].
Соединение [math]G_1[/math] и [math]G_2[/math]
Определение:
Произведением (англ. cartesian product) [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[/math] и [math]G_2[/math]
Определение:
Композицией (англ. lexicographical product) [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] — смежные).
Композиция [math]G_1[/math] и [math]G_2[/math]
Лемма (о произведении регулярных графов):
[math]G_1[/math] и [math]G_2[/math] — регулярные графы. Тогда [math]G = G_1 \times G_2[/math] — регулярный граф.
Доказательство:
[math]\triangleright[/math]

Пусть степень графов [math]G_1[/math] и [math]G_2[/math] будут [math]k_1[/math] и [math]k_2[/math] соответственно.

Рассмотрим любую вершину графа [math]G[/math]: у нее [math]k_1 + k_2[/math] смежных вершин. Значит граф [math]G[/math] регулярный.
[math]\triangleleft[/math]
Лемма (о композиции регулярных графов):
[math]G_1[/math] и [math]G_2[/math] — регулярные графы. Тогда [math]G = G_1[G_2][/math] — регулярный граф.
Доказательство:
[math]\triangleright[/math]

Пусть степень графов [math]G_1[/math] и [math]G_2[/math] будут [math]k_1[/math] и [math]k_2[/math] соответственно.

Рассмотрим любую вершину графа [math]G[/math]: у нее [math]|V_2| \cdot k_1 + k_2[/math] смежных вершин. Значит граф [math]G[/math] регулярный.
[math]\triangleleft[/math]
Лемма (о произведении двудольных графов):
[math]G_1[/math] и [math]G_2[/math] — двудольные графы. Тогда [math]G = G_1 \times G_2[/math] — двудольный граф.
Доказательство:
[math]\triangleright[/math]

Пусть цвет [math]c[/math] левых долей [math]G_1[/math] и [math]G_2[/math] будет [math]0[/math], а правых [math]1[/math]. А цвет каждой вершины [math]v = (v_1, v_2)[/math] графа [math]G[/math] будет равен [math]c(v) = (c(v_1) + c(v_2)) \bmod 2[/math].

Рассмотрим любую пару смежных вершин [math]u = (u_1, u_2)[/math] и [math]v = (v_1, v_2)[/math] из графа [math]G[/math], два случая:

  1. [math]u_1 = v_1[/math], [math]u_2[/math] и [math]v_2[/math] — смежные, значит [math]c(u_1) = c(v_1)[/math] и [math]с(u_2) \ne c(v_2)[/math], из этого следует [math]c(u) \ne c(v)[/math],
  2. [math]u_2 = v_2[/math], [math]u_1[/math] и [math]v_1[/math] — смежные, аналогично следует [math]c(u) \ne c(v)[/math].
Следовательно каждое ребро графа [math]G[/math] соединяет вершины разного цвета, значит [math]G[/math] двудольный.
[math]\triangleleft[/math]

См. также

Источники информации

  • Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теоретико-множественные_операции_над_графами&oldid=85072»