Дополнительный, самодополнительный граф

Эта статья находится в разработке!

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Дополнительный граф

<wikitex>

Определение:

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

ПРИМЕР: ТУТ БУДЕТ КАРТИНКА

Теорема:

Дополнительный граф к дополнительному графу $G$ есть граф $G$.

Доказательство:

[math]\triangleright[/math]

$\overline{\overline{G<V, E>

[math]\triangleleft[/math]

= \overline{G_1<V, \overline{E}>} = G_2<V, \overline{\overline{E}}> = G_2<V, E> = G$

}}

Теорема:

Дополнительный граф к несвязному графу связен.

Доказательство:

[math]\triangleright[/math]

Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов. Пусть $G$ - данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая. $v$ и $u$ лежат в разных компонентах связности $G$. Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$. $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}$. То есть $\forall u, v \in V u$ и $v$ лежат в одной компоненте связности $\overline{G}$, то есть $\overline{G}$ связен.

[math]\triangleleft[/math]

</wikitex>