Рёберный граф — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Дмитрий Мурзин переименовал страницу Реберный граф в Рёберный граф: Ёфикация)
Строка 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 Майкл Наки].
 +
|}
 +
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть задан граф <tex>G</tex>, тогда его '''рёберным графом''' <tex>L(G)</tex> называется граф, для которого верны следующие утверждения
+
Пусть задан граф <tex>G</tex>, тогда его '''рёберным графом''' <tex>L(G)</tex> называется граф, для которого верны следующие утверждения
 
* любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>,
 
* любая вершина графа <tex>L(G)</tex> представляет ребро графа <tex>G</tex>,
 
* две вершины графа <tex>L(G)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в <tex>G</tex>.
 
* две вершины графа <tex>L(G)</tex> смежны тогда и только тогда, когда их соответствующие рёбра смежны в <tex>G</tex>.

Версия 08:28, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Пусть задан граф [math]G[/math], тогда его рёберным графом [math]L(G)[/math] называется граф, для которого верны следующие утверждения
  • любая вершина графа [math]L(G)[/math] представляет ребро графа [math]G[/math],
  • две вершины графа [math]L(G)[/math] смежны тогда и только тогда, когда их соответствующие рёбра смежны в [math]G[/math].


Граф [math]G[/math] и его реберный граф [math]L(G)[/math]

Построение

Line graph build 1.png Line graph build 2.png Line graph build 3.png Line graph build 4.png
Граф [math]G[/math] Новые вершины [math]L(G)[/math] Добавлены рёбра в [math]L(G)[/math] Рёберный граф [math]L(G)[/math]

Свойства

Утверждение:
Рёберный граф связного графа связен.
[math]\triangleright[/math]
Если [math]G[/math] связен, он содержит путь, соединяющий любые два его ребра, что переводится в путь графа [math]L(G)[/math], содержащий любые две вершины графа [math]L(G)[/math].
[math]\triangleleft[/math]
Утверждение:
Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
Утверждение:
Рёберное хроматическое число графа [math]G[/math] равно вершинному хроматическому числу его рёберного графа [math]L(G)[/math].
Утверждение:
Утверждение:
Если граф [math]G[/math]Эйлеров граф, то его рёберный граф является Гамильтоновым графом.
[math]\triangleright[/math]
Рассмотрим Эйлеров путь [math]e_{i_1},v_{k_1},e_{i_2},\dots,v_{k_{n-1}},e_{i_n}[/math] в исходном графе [math]G[/math]. Составим из вершин реберного графа [math]L(G)[/math] последовательность [math]v_{j_1},\dots,v_{j_n}[/math], поcтавив в соответсвие ребру [math]e_{i_k}[/math] вершину [math]v_{j_k}[/math]. Так как два подряд идущих ребра [math]e_{i_k},e_{i_{k+1}}[/math] из исходного пути смежны, то из определения реберного графа следует, что сответствующие подряд идущие вершины в получившейся последовательности [math]v_{j_k},v_{j_{k+1}}[/math] смежны. Следовательно мы получили Гамильтонов путь [math]v_{j_1},e_{t_1},\dots,e_{t_{n-1}},v_{j_n}[/math] в реберном графе [math]L(G)[/math]. Доказательство для циклов аналогично.
[math]\triangleleft[/math]
Утверждение:
Ребра графа [math]G[/math] можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
Утверждение:
Реберный граф реберного графа [math]L(G)[/math] не является исходным графом [math]G[/math].
[math]\triangleright[/math]
Контрпримером является граф из раздела построение. В реберном графе количество вершин равно количеству ребер в исходном. Таким образом, в реберном графе к графу [math]L(G)[/math] будет [math]9[/math] вершин, а в исходном графе [math]G[/math] их всего [math]5[/math].
[math]\triangleleft[/math]


Теорема:
Если [math]G[/math] — это [math](p,q)[/math]-граф с вершинами, имеющими степени [math]d_i[/math], то [math]L(G)[/math] имеет [math]q[/math] вершин и [math]q_L[/math] ребер, где [math]q_L = -q + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}[/math]
Доказательство:
[math]\triangleright[/math]

По определению реберного графа граф [math]L(G)[/math] имеет [math]q[/math] вершин. Каждые [math]d_i[/math] ребер, инцидентных вершине [math]v_i[/math], дают вклад [math]\begin{pmatrix} d_i \\ 2 \end{pmatrix}[/math] в число ребер графа [math]L(G)[/math], так что

[math]q_L = \sum\limits_i{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \dfrac{1}{2}\sum\limits_i{d_i(d_i-1)} = \dfrac{1}{2}\sum\limits_i{d_i^2}-\dfrac{1}{2}\sum\limits_i{d_i} = \dfrac{1}{2}\sum\limits_i{d_i^2-q}[/math]
[math]\triangleleft[/math]

Источники информации

  • Wikipedia — Реберные графы
  • Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)