|
|
Строка 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 Майкл Наки].
| |
− | |}
| |
− |
| |
| <br/> | | <br/> |
| {| class="standard" border=0 | | {| class="standard" border=0 |
Текущая версия на 19:14, 4 сентября 2022
Пример планарного графа. Синим контуром обозначены грани, за исключением внешней грани (всего 5 граней). Обратите внимание, что внутри грани могут содержаться другие ребра и вершины.
|
Определение: |
Граф обладает укладкой в пространстве [math]L[/math], если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами — жордановы кривые [1], соединяющие соответствующие вершины, причем
- Кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
- Две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
Соответствующий граф, составленный из точек пространства и жордановых кривых из [math]L[/math], называют укладкой исходного графа. |
Определение: |
Граф называется планарным (англ. planar graph), если он обладает укладкой на плоскости. Плоским (англ. plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости. |
|
Определение: |
Плоский граф разбивает плоскость на несколько областей, называемых гранями (англ. faces). Одна из граней не ограничена, ее называют внешней (англ. external) гранью, а остальные — внутренними (англ. unbounded) гранями. |
Для плоских графов есть простое соотношение, называемое формулой Эйлера: [math]V - E + F = 2[/math], где [math]V[/math] — вершины, [math]E[/math] — ребра, [math]F[/math] — грани.
Это свойство позволяет в некоторых случаях просто доказывать непланарность некоторых графов, например непланарность [math]K_5[/math] и [math]K_{3,3}[/math].
Понятно, что любой граф, содержащий подграф [math]K_5[/math] или [math]K_{3,3}[/math] непланарен. Оказывается, верно и обратное утверждение, но для его формулировки потребуется вспомогательное определение:
|
Полный двудольный граф [math]K_{3,3}[/math]. Этот граф непланарен, и его не получится изобразить на плоскости без пересечений ребер.
|
Определение: |
Введем отношение [math]R[/math] следующим образом: два графа находятся в отношении [math]R[/math], если один можно свести к другому заменой вершины степени 2 на ребро между вершинами смежными ей, или наоборот, добавлением вершины степени два на ребро (см. картинку).
Отношением гомеоморфизма (или топологической эквивалентности) назовем транзитивное замыкание отношения [math]R[/math]: [math]R[/math]*. |
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math]K_5[/math] и [math]K_{3,3}[/math]: теорема Понтрягина-Куратовского.
Теорема: |
В трехмерном евклидовом пространстве любой граф укладывается. |
Доказательство: |
[math]\triangleright[/math] |
Все вершины произвольного графа [math]G[/math] помещаем в различных точках координатной оси [math]OX[/math]. Рассмотрим пучок плоскостей, проходящих через ось [math]OX[/math], и зафиксируем [math]|E|[/math] различных таких плоскостей. Теперь каждое ребро [math](u, v)[/math] изобразим полуокружностью, проходящей в соответствующей плоскости через вершины [math]u, v[/math]. Ясно, что различные ребра не будут пересекаться кроме как в общих вершинах. |
[math]\triangleleft[/math] |
См. также
Примечания
- ↑ Жордановыми кривыми, неформально говоря, называют кривые без самопересечений, которые можно «нарисовать одним росчерком пера».
Источники информации
- Асанов М, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 126. — ISBN 978-5-397-00622-4.