3622
правки
Изменения
м
Нет описания правки
{{Теорема
|statement=
Дополнительный [[Основные_определения_теории_графов|граф ]] к дополнительному графу $G$ есть граф $G$.
|proof=
<tex>\overline{\overline {G \langle V, E \rangle}} = \overline{G_1 \langle V, \overline{E} \rangle} = G_2 \langle V, \overline{\overline{E}} = G_2 \langle V, E \rangle = G</tex>
{{Теорема
|statement=
Дополнительный граф к [[Отношение связности, компоненты связности|несвязному ]] графу связен.
|proof=
Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов.
Пусть $G$ {{- --}} данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая: $v$ и $u$ лежат в одной или в разных компонентах связности.
*Пусть $v$ и $u$ лежат в разных компонентах связности $G$. :Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.
<br>
[[Файл:допграф3.png|500px|слева]]
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
*Пусть $v$ и $u$ лежат в одной компоненте связности $G$.
$G$ {{---}} несвязный $\Rightarrow \exists w \in G$, не лежащая в одной компоненте связности с $v$ и $u$.
:Тогда по предыдущему пункту $(v, w) \in \overline{G}$ и $(u, w) \in \overline{G} \Rightarrow v$ и $u$ лежат в одной компоненте связности $\overline{G}$.
<br>
[[Файл:допграф4.png|500px|слева]]
{{Определение
|definition =
'''Самодополнительным графом''' (англ. ''self-complement'') называется граф, [[Основные определения теории графов|изоморфный ]] своему дополнительному.
}}
<br>
</wikitex>
== См. также ==* [[Основные определения теории графов]]* [[Отношение связности, компоненты связности]] == Источники информации ==
* ''Харари Ф.'' Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 Дополнение_графа Википедия {{---}} дополнение графа]* [https://ru.wikipedia.org/wiki//Самодополнительный_граф Википедия {{---}} самодополнительный граф]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
