Материал из Викиконспекты
|
|
Строка 1: |
Строка 1: |
− | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
− | |+
| |
− | |-align="center"
| |
− | |'''НЕТ ВОЙНЕ'''
| |
− | |-style="font-size: 16px;"
| |
− | |
| |
− | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
− |
| |
− | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
− |
| |
− | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
− |
| |
− | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
− |
| |
− | ''Антивоенный комитет России''
| |
− | |-style="font-size: 16px;"
| |
− | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
− | |-style="font-size: 16px;"
| |
− | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
− | |}
| |
− |
| |
| == Дополнительный граф == | | == Дополнительный граф == |
| <wikitex> | | <wikitex> |
Текущая версия на 19:35, 4 сентября 2022
Дополнительный граф
<wikitex>
Определение: |
Пусть дан граф [math]G \langle V, E \rangle[/math]. Дополнительным графом (англ. complement graph) к $G$ называется граф [math]G \langle V, \overline E \rangle[/math] то есть граф с вершинами из $V$ и теми и только теми ребрами из $E$, которые не вошли в $G$. |
Пример графа с 6-ю вершинами и его дополнение.
|
|
|
Теорема: |
Дополнительный граф к дополнительному графу $G$ есть граф $G$. |
Доказательство: |
[math]\triangleright[/math] |
[math]\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[/math] |
[math]\triangleleft[/math] |
Теорема: |
В дополнительном графе к [math]G \langle V, E \rangle[/math]. количество ребер равняется [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$ лежат в одной или в разных компонентах связности.
- Пусть $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>
См. также
Источники информации