Дополнительный, самодополнительный граф
Версия от 19:35, 4 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
Дополнительный граф
<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$. Возможны два случая: $v$ и $u$ лежат в одной или в разных компонентах связности.
$G$ — несвязный $\Rightarrow \exists w \in G$, не лежащая в одной компоненте связности с $v$ и $u$.
|
Самодополнительный граф
Определение: |
Самодополнительным графом (англ. 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
- Википедия — дополнение графа
- Википедия — самодополнительный граф