Изменения

Пусть дан граф $<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}$.

[[Файл:ololoдопграф3.png|100px500px|слева|временная картинка]]<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>

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

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

[[Файл:ololoдопграф4.png|100px500px|слева|временная картинка]]<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>

То есть $\forall u, v \in V $ $u$ и $v$ лежат в одной компоненте связности $\overline{G}$, то есть $\overline{G}$ связен.

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

Будем доказывать по индукции. Для графа с одной вершиной $k = 1$ утверждение очевидносправедливо. Докажем его для остальных графов [[Файл:допграф7.png|400px|link=]] Пусть у нас есть самодополнительный граф $G$ с $n$ вершинами, построим самодополнительный граф с $n + 4$ вершинами.Добавим к $G$ 4 вершины $v_1, v_2, v_3, v_4$ и ребра: *Добавим ребра $(v_1, v_2), (v_2, v_3), (v_3, v_4)$*Если $u$ была вершиной в $G$, добавим ребра $(u, v_1), (u, v_4)$

Пусть Назовем полученный граф $GA$ - данный граф. Рассмотрим произвольные вершины $vДокажем, что $ и A$u$ из $G$. Возможны два случаясамодополнителен.

*Рассмотрим биекцию на множестве вершин $vA$ и $u\overline{A}$ лежат в разных компонентах связности :*Среди всех вершин, принадлежавших $G$. Тогда ребро $(uбиекция будет такая же, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ как и у $vG$ лежат в одной компоненте связности с $\overline{G}$. ;<br> [[Файл:ololo*$v_1 \rightarrow v_2, v_2 \rightarrow v_4, v_3 \rightarrow v_1, v_4 \rightarrow v_3$.png|100px|слева|временная картинка]]