Дополнительный, самодополнительный граф — различия между версиями
(→Источники) |
(→Дополнительный граф) |
||
Строка 17: | Строка 17: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Дополнительный граф к дополнительному графу $G$ есть граф $G$. | + | Дополнительный [[Основные_определения_теории_графов|граф]] к дополнительному графу $G$ есть граф $G$. |
|proof= | |proof= | ||
<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>\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> | ||
Строка 35: | Строка 35: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Дополнительный граф к несвязному графу связен. | + | Дополнительный граф к [[Отношение связности, компоненты связности|несвязному]] графу связен. |
|proof= | |proof= | ||
Строка 63: | Строка 63: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Самодополнительным графом''' (англ. ''self-complement'') называется граф, изоморфный своему дополнительному. | + | '''Самодополнительным графом''' (англ. ''self-complement'') называется граф, [[Основные определения теории графов|изоморфный]] своему дополнительному. |
}} | }} | ||
<br> | <br> |
Версия 09:21, 11 ноября 2016
Дополнительный граф
<wikitex>
Определение: |
Пусть дан граф | . Дополнительным графом (англ. complement graph) к $G$ называется граф то есть граф с вершинами из $V$ и теми и только теми ребрами из $E$, которые не вошли в $G$.
Пример графа с 6-ю вершинами и его дополнение. | |
![]() |
![]() |
Теорема: |
Дополнительный граф к дополнительному графу $G$ есть граф $G$. |
Доказательство: |
Теорема: |
В дополнительном графе к . количество ребер равняется . |
Доказательство: |
Так как множества ребер в $G$ и $\overline{G}$ дизъюнктны, то $\left\vert E \right\vert + \left\vert \overline{E} \right\vert =$ | , из чего следует утверждение теоремы.
Теорема: |
Дополнительный граф к несвязному графу связен. |
Доказательство: |
Для графа с одной вершиной утверждение очевидно. Докажем его для остальных графов. Пусть $G$ - данный граф. Рассмотрим произвольные вершины $v$ и $u$ из $G$. Возможны два случая.
Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.
$G$ — несвязный $\Rightarrow \exists w \in G$, не лежащая в одной компоненте связности с $v$ и $u$.
Тогда по предыдущему пункту $(v, w) \in \overline{G}$ и $(u, w) \in \overline{G} \Rightarrow v$ и $u$ лежат в одной компоненте связности $\overline{G}$.
|
Самодополнительный граф
Определение: |
Самодополнительным графом (англ. self-complement) называется граф, изоморфный своему дополнительному. |
Теорема: |
Любой самодополнительный граф имеет $4k$ или $4k + 1$ вершину. |
Доказательство: |
Обозначим $\left\vert V \right\vert$ за $n$, $\left\vert E \right\vert$ за $a$. Граф самодополнителен $\Rightarrow$ количество его ребер равно количеству ребер в его дополнении. Но по одной из предыдущих теорем, $- a = \left\vert \overline{E} \right\vert = a \Rightarrow 4a = n \cdot \left ( n - 1 \right )$, из чего следует утверждение теоремы. |
</wikitex>
Источники
- Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — дополнение графа
- Википедия — самодополнительный граф