Изменения
Нет описания правки
{{nohate}}
== Дополнительный граф ==
<wikitex>
{{Определение
|definition =
}}
ПРИМЕР: ТУТ БУДЕТ КАРТИНКА
[[Файл:ololo.png|200px|link=|временная картинка]]
{{Теорема
|statement=
Дополнительный граф к дополнительному графу $G$ есть граф $G$.
|proof=
$\overline{\overline{G<V, E>}} = \overline{G_1<V, \overline{E}>} = G_2<V, \overline{\overline{E}}> = G_2<V, E> = G$
}}
{{Теорема
|statement=
Дополнительный граф к несвязному графу связен.
|proof=
Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов.
Пусть $G$ - данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая.
*$v$ и $u$ лежат в разных компонентах связности $G$.
Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.
<br>
[[Файл:ololo.png|100px|слева|временная картинка]]
<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>
[[Файл:ololo.png|100px|слева|временная картинка]]
<br><br><br><br><br><br>
То есть $\forall u, v \in V u$ и $v$ лежат в одной компоненте связности $\overline{G}$, то есть $\overline{G}$ связен.
}}
</wikitex>
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
