Обсуждение участника:SergeyBud — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|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>.
 
}}
 
}}
 +
 +
[[Файл:Line_graph_example.png|400px|thumb|center|Граф G и его реберный граф L(G)]]
 
==Свойства==
 
==Свойства==
−
[[Файл:Line_graph_example.png|400px|thumb|right|Граф G и его реберный граф L(G)]]
+
{{Утверждение
−
* Рёберный граф связного графа связен.
+
|statement=Рёберный граф [[Отношение_связности,_компоненты_связности|связного графа]] связен.
−
* Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.  
+
|proof= Если G связен, он содержит [[Основные_определения_теории_графов|путь]], соединяющий любые два его ребра, что переводится в путь графа L(G), содержащий любые две вершины графа L(G).
−
* Рёберное хроматическое число графа <tex>G</tex> равно вершинному хроматическому числу его рёберного графа <tex>L(G)</tex>.
+
}}
−
* Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
+
{{Утверждение
−
* Если граф <tex>G</tex> имеет Эйлеров цикл, то есть <tex>G</tex> связен и имеет чётное число рёбер в каждой вершине, то его рёберный граф является Гамильтоновым графом.
+
|statement=Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.  
−
*Ребра графа <tex>G</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
+
}}
 +
{{Утверждение
 +
|statement=Рёберное [[Раскраска_графа#chromatic_number_difinition|хроматическое число]] графа <tex>G</tex> равно вершинному хроматическому числу его рёберного графа <tex>L(G)</tex>.
 +
}}
 +
{{Утверждение
 +
|statement=Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
 +
}}
 +
{{Утверждение
 +
|statement=Если граф <tex>G</tex> [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров граф]], то его рёберный граф является [[Гамильтоновы_графы|Гамильтоновым графом]].
 +
|proof=Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф <tex>L(G)</tex> {{---}} Гамильтонов граф, а граф <tex>G</tex> не является Эйлеровым графом.
 +
[[Файл:Line_graph_gam_euler.PNG|300px]]
 +
}}
 +
{{Утверждение
 +
|statement=Ребра графа <tex>G</tex> можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
 +
}}
 +
{{Утверждение
 +
|statement=Реберный граф реберного графа <tex>L(G)</tex> '''не''' является исходным графом <tex>G</tex>.
 +
}}
  
  
 
{{Теорема
 
{{Теорема
 
|id=Теорема1
 
|id=Теорема1
−
|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex> - граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где
+
|statement=Если <tex>G</tex> {{---}} это <tex>(p,q)</tex>-граф с вершинами, имеющими степени <math>d_i</math>, то <tex>L(G)</tex> имеет <tex>q</tex> вершин и <math>q_L</math> ребер, где
−
<math>q_L = -q + \frac{1}{2}\sum{d_{i}^{2}}</math>
+
<math>q_L = -q + {\dfrac{1}{2}}\sum\limits_i{d_{i}^{2}}</math>
 
|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(G)</tex>, так что
 
|proof=По определению реберного графа граф <tex>L(G)</tex> имеет <tex>q</tex> вершин. Каждые <math>d_i</math> ребер, инцидентных вершине <math>v_i</math>, дают вклад <math>\begin{pmatrix} d_i \\ 2 \end{pmatrix}</math> в число ребер графа <tex>L(G)</tex>, так что
−
<math>q_L = \sum{\begin{pmatrix} d_i \\ 2 \end{pmatrix}} = \frac{1}{2}\sum{d_i(d_i-1)} = \frac{1}{2}\sum{d_i^2}-\frac{1}{2}\sum{d_i} = \frac{1}{2}\sum{d_i^2-q}</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>
 
}}
 
}}
  
 
==Построение==
 
==Построение==
−
[[Файл:line_graph_build_1.png|200px]][[Файл:line_graph_build_2.png|200px]][[Файл:line_graph_build_3.png|200px]][[Файл:line_graph_build_4.png|200px]]
+
{| cellpadding="0"
−
 
+
| [[Файл:line_graph_build_1.png|200px]] || [[Файл:line_graph_build_2.png|200px]] || [[Файл:line_graph_build_3.png|200px]] || [[Файл:line_graph_build_4.png|200px]]
−
Граф <tex>G \rightarrow </tex> Вершины <tex>L(G)</tex>, созданные из ребер графа <tex>G \rightarrow </tex> Добавлены рёбра в <tex>L(G) \rightarrow </tex> Рёберный граф <tex>L(G)</tex>
+
|-
 +
|Граф <tex>G</tex> || Новые вершины <tex>L(G)</tex> || Добавлены рёбра в <tex>L(G)</tex> || Рёберный граф <tex>L(G)</tex>
 +
|}
  
 
==Источники информации==
 
==Источники информации==
 
*[[wikipedia:ru:Рёберный_граф | Wikipedia {{---}} Реберные графы ]]
 
*[[wikipedia:ru:Рёберный_граф | Wikipedia {{---}} Реберные графы ]]
−
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.
+
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
 +
 
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения теории графов]]

Версия 02:08, 9 января 2015

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


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

Свойства

Утверждение:
Рёберный граф связного графа связен.
[math]\triangleright[/math]
Если G связен, он содержит путь, соединяющий любые два его ребра, что переводится в путь графа L(G), содержащий любые две вершины графа L(G).
[math]\triangleleft[/math]
Утверждение:
Задача о максимальном независимом множестве для рёберного графа соответствует задаче нахождения максимального паросочетания в исходном графе.
Утверждение:
Рёберное хроматическое число графа [math]G[/math] равно вершинному хроматическому числу его рёберного графа [math]L(G)[/math].
Утверждение:
Рёберный граф рёберно-транзитивного графа является вершинно-транзитивным графом.
Утверждение:
Если граф [math]G[/math] Эйлеров граф, то его рёберный граф является Гамильтоновым графом.
[math]\triangleright[/math]

Для доказательства приведем контрпример к обратному утверждению. На следующем рисунке граф [math]L(G)[/math] — Гамильтонов граф, а граф [math]G[/math] не является Эйлеровым графом.

Line graph gam euler.PNG
[math]\triangleleft[/math]
Утверждение:
Ребра графа [math]G[/math] можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам.
Утверждение:
Реберный граф реберного графа [math]L(G)[/math] не является исходным графом [math]G[/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]

Построение

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]

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

  • Wikipedia — Реберные графы
  • Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.(Глава 8: Реберные графы. стр. 91-104)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение_участника:SergeyBud&oldid=43690»