Дополнительный, самодополнительный граф — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
  
 
[[Файл:ololo.png|200px|link=|временная картинка]]
 
[[Файл:ololo.png|200px|link=|временная картинка]]
 
+
<br>
 +
<br>
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 19: Строка 20:
 
$\overline{\overline{G<V, E>}} = \overline{G_1<V, \overline{E}>} = G_2<V, \overline{\overline{E}}> = G_2<V, E> = G$  
 
$\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>
  
 
{{Теорема
 
{{Теорема
Строка 46: Строка 58:
 
}}
 
}}
  
 +
== Самодополнительный граф ==
 +
 +
{{Определение
 +
|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>
 
</wikitex>
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Версия 21:12, 7 декабря 2012

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

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

<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$

}}



Теорема:
В дополнительном графе к $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]

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

Определение:
Самодополнительным графом называется граф, изоморфный своему дополнительному.



Теорема:
Любой самодополнительный граф имеет $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]

Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов.

Пусть $G$ - данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая.

  • $v$ и $u$ лежат в разных компонентах связности $G$.

Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.

временная картинка
[math]\triangleleft[/math]

</wikitex>