Материал из Викиконспекты
|
|
| Строка 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 Майкл Наки].
| |
| − | |}
| |
| − |
| |
| − |
| |
| | | | |
| | | | |
Текущая версия на 19:07, 4 сентября 2022
Независимое множество
| Определение: |
| Независимым множеством вершин (англ. independent vertex set) графа [math]G=(V,E)[/math] называется такое подмножество [math]S[/math] множества вершин графа [math]V[/math], что
[math] \forall u, v \in S[/math] [math]uv \notin E[/math]. |
| Определение: |
| Максимальным независимым множеством (англ. maximum independent set) называется независимое множество вершин максимальной мощности. |
Множество вершин синего цвета — максимальное независимое множество.
Связь вершинного покрытия и независимого множества
| Теорема: |
Дополнение минимального вершинного покрытия является максимальным независимым множеством. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]M[/math] произвольное максимальное независимое множество вершин графа [math]G=(V,E)[/math], а [math]S[/math] его минимальное вершинное покрытие. Из определения следует, что любое ребро соединяет либо вершину из [math]M[/math] и [math]V \backslash M[/math], либо вершины множества [math]V \backslash M[/math]. Таким образом, каждое
ребро инцидентно некоторой вершине множества [math]V \backslash M[/math], то есть [math]V \backslash M[/math] является некоторым вершинным покрытием. Тогда [math]|S| \leqslant |V \backslash M|[/math] или [math]|S| + |M| \leqslant |V|[/math].
Рассмотрим произвольное минимальное вершинное покрытие графа [math]S[/math]. Так как каждое ребро инцидентно хотя бы одной вершине из [math]S[/math], то [math]V \backslash S[/math] является независимым множеством. Тогда [math]|V \backslash S| \leqslant |M|[/math] или [math]|V| \leqslant |S| + |M|[/math].
Значит, [math]|V| = |M| + |S|[/math], и [math]V \backslash S[/math] является максимальным независимым множеством, а [math]V \backslash M[/math] — минимальным вершинным покрытием. |
| [math]\triangleleft[/math] |
См. также
Источники информации
