1632
правки
Изменения
м
rollbackEdits.php mass rollback
Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов.
Пусть $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>
<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}$.
