1632
правки
Изменения
м
{{в разработке}}
{{nohate}}
ПРИМЕР: ТУТ БУДЕТ КАРТИНКА<br><br>{{Теорема|statement=Дополнительный [[Файл:ololoОсновные_определения_теории_графов|граф]] к дополнительному графу $G$ есть граф $G$.png|200px|linkproof=<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$ есть граф $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>.
То есть $\forall u, v \in V u$ и $v$ лежат в одной компоненте связности $\overline{G}$, то есть $\overline{G}$ связен.
rollbackEdits.php mass rollback
== Дополнительный граф ==
<wikitex>
{{Определение
|definition =
Пусть дан граф $<tex>G<\langle V, E\rangle</tex>$. '''Дополнительным графом к''' (англ. ''complement graph'') к $G$ называется граф $G_1<tex>G \langle V, \overline{E}\rangle</tex>$, то есть граф с вершинами из $V$ и всеми теми и только теми ребрами из $E$, которые не вошли в $G$.
}}
{|class="wikitable" border="1" style="border-collapse:collapse; border:noborder"
|+
|colspan="2"|Пример графа с 6-ю вершинами и его дополнение.
|-
| [[Файл:допграф1.png|200px|link=]]
| [[Файл:допграф2.png|200px|link=]]
|}
<br><br>
{{Теорема
|statement=
|proof=
Так как множества ребер в $G$ и $\overline{\overline{G<V}$ дизъюнктны, то $\left\vert E>}} = \overline{G_1<V, right\vert + \left\vert \overline{E}>} \right\vert = G_2$ <tex dpi=150>\frac{\left\vert V, \overline{right\vert \cdot \left ( \left\vert V \right\vert - 1 \overlineright )}{E}2}</tex> = G_2<V, E> = G$ из чего следует утверждение теоремы.
}}
<br><br>
{{Теорема
|statement=
Дополнительный граф к [[Отношение связности, компоненты связности|несвязному ]] графу связен.
|proof=
Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов.
Пусть $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>
[[Файл:ololoдопграф3.png|100px500px|слева|временная картинка]]<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}$.
<br>
[[Файл: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}$ связен.}} == Самодополнительный граф == {{Определение|definition ='''Самодополнительным графом''' (англ. ''self-complement'') называется граф, [[Основные определения теории графов|изоморфный]] своему дополнительному.}}<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=
Будем доказывать по индукции. Для $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)$
Назовем полученный граф $A$. Докажем, что $A$ самодополнителен.
Рассмотрим биекцию на множестве вершин $A$ и $\overline{A}$:
*Среди всех вершин, принадлежавших $G$ биекция будет такая же, как и у $G$ с $\overline{G}$;
*$v_1 \rightarrow v_2, v_2 \rightarrow v_4, v_3 \rightarrow v_1, v_4 \rightarrow v_3$.
Тогда между ребрами $A$ и $\overline{A}$ тоже будет биекция.
[[Файл:допграф9.png|400px|]]
}}
</wikitex>
== См. также ==
* [[Основные определения теории графов]]
* [[Отношение связности, компоненты связности]]
== Источники информации ==
* ''Харари Ф.'' Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [https://ru.wikipedia.org/wiki/Дополнение_графа Википедия {{---}} дополнение графа]
* [https://ru.wikipedia.org/wiki//Самодополнительный_граф Википедия {{---}} самодополнительный граф]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
