234
правки
Изменения
Нет описания правки
[[Файл:ololo.png|200px|link=|временная картинка]]
<br><br>
{{Теорема
|statement=
$\overline{\overline{G<V, E>}} = \overline{G_1<V, \overline{E}>} = G_2<V, \overline{\overline{E}}> = G_2<V, E> = G$
}}
<br><br>
{{Теорема
|statement=
В дополнительном графе к $G<V, E>$ количество ребер равняется <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>.
|proof=
Так как множества ребер в $G$ и $\overline{G}$ дизъюнктны, то $\left\vert E \right\vert + \left\vert \overline{E} \right\vert =$ <tex dpi=150>\frac{\left\vert V \right\vert \cdot \left ( \left\vert V \right\vert - 1 \right )}{2}</tex>, из чего следует утверждение теоремы.
}}
<br><br>
{{Теорема
}}
== Самодополнительный граф ==
{{Определение
|definition =
'''Самодополнительным графом''' называется граф, {{Acronym|изоморфный|Два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.}} своему дополнительному.
}}
<br>
<br>
{{Теорема
|statement=
Любой самодополнительный граф имеет $4k$ или $4k + 1$ вершину.
|proof=
Обозначим $\left\vert V \right\vert$ за $n$, $\left\vert E \right\vert$ за $a$.
Граф самодополнителен $\Rightarrow$ количество его ребер равно количеству ребер в его дополнении.
Но по одной из предыдущих теорем, <tex dpi=150>\frac{n \cdot \left ( n - 1 \right )}{2}</tex> $- a = \left\vert \overline{E} \right\vert = a \Rightarrow 4a = n \cdot \left ( n - 1 \right )$, из чего следует утверждение теоремы.
}}
<br><br>
{{Теорема
|statement=
Для любых $k > 0$ существует самодополнительный граф с $4k$ или $4k + 1$ вершиной.
|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|слева|временная картинка]]
}}
</wikitex>
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
