Изменения

Пусть дан граф $<tex>G<\langle V, E\rangle</tex>$. '''Дополнительным графом к''' (англ. ''complement graph'') к $G$ называется граф $G_1<tex>G \langle V, \overline{E}\rangle</tex>$, то есть граф с вершинами из $V$ и теми и только теми ребрами из $E$, которые не вошли в $G$.

Дополнительный [[Основные_определения_теории_графов|граф ]] к дополнительному графу $G$ есть граф $G$.

 $<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>

В дополнительном графе к $<tex>G<\langle V, E\rangle</tex>$ . количество ребер равняется <tex dpi=150>\frac{\left\vert V \right\vert \cdot \left ( \left\vert V \right\vert - 1 \right )}{2} - \left\vert E \right\vert</tex>.

Дополнительный граф к [[Отношение связности, компоненты связности|несвязному ]] графу связен.

Пусть $G$ {{- --}} данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая: $v$ и $u$ лежат в одной или в разных компонентах связности.

*Пусть $v$ и $u$ лежат в разных компонентах связности $G$. :Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.

*Пусть $v$ и $u$ лежат в разных компонентах одной компоненте связности $G$.

:Тогда по предыдущему пункту $(v, w) \in \overline{G}$ и $(u, w) \in \overline{G} \Rightarrow v$ и $u$ лежат в одной компоненте связности $\overline{G}$.

'''Самодополнительным графом''' (англ. ''self-complement'') называется граф, {{Acronym[[Основные определения теории графов|изоморфный|Два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.}} ]] своему дополнительному.

== См. также ==* [[Основные определения теории графов]]* [[Отношение связности, компоненты связности]] == Источники информации ==*''Харари Ф. Харари ''Теория графов'', . /пер. с англ. — изд. 2-е — М.:Мир 1973гЕдиториал УРСС, 29 стр2003. — 296 с. — ISBN 5-354-00301-6 * [https://ru.wikipedia.org/wiki/Дополнение_графа Википедия {{---}} дополнение графа]* [https://ru.wikipedia. org/wiki//Самодополнительный_граф Википедия {{---}} самодополнительный граф]