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

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

<wikitex>

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

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

Пример графа с 6-ю вершинами и его дополнение.

Теорема:

Дополнительный граф к дополнительному графу $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$

}}

Теорема:

В дополнительном графе к $G<V, E>$ количество ребер равняется [math]\frac{\left\vert V \right\vert \cdot \left ( \left\vert V \right\vert - 1 \right )}{2} - \left\vert E \right\vert[/math].

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

[math]\triangleright[/math]

Так как множества ребер в $G$ и $\overline{G}$ дизъюнктны, то $\left\vert E \right\vert + \left\vert \overline{E} \right\vert =$ [math]\frac{\left\vert V \right\vert \cdot \left ( \left\vert V \right\vert - 1 \right )}{2}[/math], из чего следует утверждение теоремы.

[math]\triangleleft[/math]

Теорема:

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

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

[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]

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

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

Самодополнительным графом (self-complement) называется граф, изоморфный своему дополнительному.

Теорема:

Любой самодополнительный граф имеет $4k$ или $4k + 1$ вершину.

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

[math]\triangleright[/math]

Обозначим $\left\vert V \right\vert$ за $n$, $\left\vert E \right\vert$ за $a$. Граф самодополнителен $\Rightarrow$ количество его ребер равно количеству ребер в его дополнении. Но по одной из предыдущих теорем, [math]\frac{n \cdot \left ( n - 1 \right )}{2}[/math] $- a = \left\vert \overline{E} \right\vert = a \Rightarrow 4a = n \cdot \left ( n - 1 \right )$, из чего следует утверждение теоремы.

[math]\triangleleft[/math]

Теорема:

Для любых $k > 0$ существует самодополнительный граф с $4k$ или $4k + 1$ вершиной.

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

[math]\triangleright[/math]

Будем доказывать по индукции. Для $k = 1$ утверждение справедливо. Пусть у нас есть самодополнительный граф $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}$ тоже будет биекция.

[math]\triangleleft[/math]

</wikitex>

Источники

• Ф. Харари Теория графов, М:Мир 1973г, 29 стр.